1、解決圖的編程問題,數(shù)據(jù)結(jié)構(gòu)(C#語言版),目標,在本章中,你將學(xué)到: 在圖中存儲數(shù)據(jù) 圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法 最小生成樹 圖的最短路徑,學(xué)習(xí)情境用圖高速公路交通網(wǎng)的編程,問題描述 一個地區(qū)由許多城市組成，為實現(xiàn)城市間的高速運輸，需要在這些城市間鋪設(shè)高速公路，以達到任意兩個城市間高速運輸?shù)哪康?。?jīng)過考察和預(yù)算，鋪設(shè)的高速公路交通網(wǎng)如圖9.1所示。其中每個頂點代表一個城市，頂點間的連線代表兩個城市間鋪設(shè)的高速公路，而線上的數(shù)字表示兩個城市間的距離（單位：公理）。如圖所示。,請根據(jù)上面的描述，解決下面的問題： 用C#編寫一程序來存儲該高速公路交通網(wǎng)的信息 。 從任何一個城市出發(fā)，訪問所有

2、的城市，給出訪問城市的順序。 如果想從一個城市到另一個城市旅行，給出最短的旅行路線。,圖是一系列頂點（結(jié)點）和描述頂點之間的關(guān)系邊（弧）組成。圖是數(shù)據(jù)元素的集合，這些數(shù)據(jù)元素被相互連接以形成網(wǎng)絡(luò)。其形式化定義為： G=（V，E） V=Vi | Vi某個數(shù)據(jù)元素集合 E=(Vi,Vj) | Vi,VjVP(Vi,Vj),認識圖圖的定義和術(shù)語,1. 圖的定義,其中，G表示圖，V是頂點的集合，E是邊或弧的集合。在集合E中，P(Vi,Vj)表示頂點Vi和頂點Vj之間有邊或弧相連。,認識圖圖的定義和術(shù)語,2. 圖的術(shù)語,頂點集：圖中具有相同特性的數(shù)據(jù)元素的集合稱為頂點集 邊（?。哼吺且粚旤c間的路徑，

3、通常帶箭頭的邊稱為弧 弧頭：每條箭頭線的頭頂點表示構(gòu)成弧的有序?qū)χ械暮笠粋€ 弧尾：每條箭頭線的尾頂點表示構(gòu)成弧的有序?qū)χ械那耙粋€頂點，稱為弧尾或始點。 度：在無向圖中的頂點的度是指連那個頂點的邊的數(shù)量。在有向圖中，每個頂點有兩種類的的度：出度和入度。 入度：頂點的入度是指向那個頂點的邊的數(shù)量。 出度：頂點的出度是由那個頂點出發(fā)的邊的數(shù)量。 權(quán)：有些圖的邊（或?。└綆в幸恍?shù)據(jù)信息，這些數(shù)據(jù)信息稱為邊（或?。┑臋?quán)（weigh）.,認識圖圖的定義和術(shù)語,3. 圖的分類,有向圖：在一個圖中，如果任意兩頂點構(gòu)成的偶對（Vi,Vj）是有序的，那么稱該圖為有向圖。這里Vi是弧尾，Vj是弧頭。這表示有一個從

4、頂點Vi到頂點 Vj的路徑。但是從Vj到Vi是不可能的 無向圖：在一個圖中，如果有任意兩頂點構(gòu)成的邊（Vi,Vj），（Vi,Vj）和（Vj ，Vi）是相同的 在一個無向圖中，如果任意兩個頂點之間都有邊相連，則稱該圖為無向完全圖。無向完全圖又稱完全圖 在一個有向圖，如果任意兩個頂點之間都是弧相連，則稱該圖為有向完全圖。 有很少條邊或弧的圖稱為稀疏圖，反之稱為稠密圖。,SetNode()：在圖中增加一個新的頂點 GetNode()：獲取圖中指定頂點 SetEdge()：在兩個頂點之間添加指定權(quán)值的邊或弧 GetEdge()：獲取兩個頂點之間的邊 DelEdge()：刪除兩個頂點之間的邊或弧 Get

5、NumOfVertex()：獲取鄰接矩陣頂點數(shù) GetNumOfEdge()：獲取鄰接矩陣邊或弧的數(shù)目 GetIndex()：獲取指定頂點在數(shù)組中的索引 IsEdge()：判斷兩個頂點之間是否存在邊或弧 IsNode()：判斷指定結(jié)點是否是圖的頂點,認識圖識別圖的基本操作,圖的基本操作有以下幾種：,鄰接矩陣(Adjacentcy Matrix)是用兩個數(shù)組來表示圖，一個數(shù)組是一維數(shù)組，存儲圖中的頂點信息，一個數(shù)組是二維數(shù)組，即矩陣，存儲頂點之間相鄰的信息，也就是邊（或?。┑男畔?。如果圖中有n個頂點，你需要大小為nn的二維數(shù)組來表示圖。 用C#語言表示鄰接矩陣的代碼 參見P190頁,用鄰接矩陣解

6、決圖的編程問題 用鄰接矩陣表示圖,對鄰接矩陣進行操作參見P191頁代碼。,鄰接表的存儲方法是一種順序存儲與鏈式存儲相結(jié)合的存儲方法，順序存儲部分用來保存圖中頂點的信息，鏈式存儲部分用來保存圖中邊（或?。┑男畔?。具體的做法是：使用一個一維數(shù)組，其中每個數(shù)組元素包含兩個域，其結(jié)構(gòu)如右圖所示。 其中 頂點域（data）：存放與頂點有關(guān)的信息； 頭指針域（firstadj）：存放與該頂點相鄰接的所有頂點組成的單鏈表的頭指針,用鄰接表解決圖的編程問題 用鄰接表表示圖,鄰接單鏈表中每個結(jié)點表示依附于該頂點的一條邊，稱作邊結(jié)點，邊結(jié)點的結(jié)構(gòu)如右圖所示。 其中 鄰接點域(adjvex)：指示與頂點鄰接點在圖中

7、的位置，對應(yīng)著一維 數(shù)組中的序號，對于有向圖，存放的是該邊結(jié)點所表示的弧的弧頭 頂點在一維數(shù)組中的序號； 數(shù)據(jù)域(info)：存儲邊或弧相關(guān)的信息，如權(quán)值等，當圖中邊（或?。?不含有信息時，該域可以省略。 鏈域(nextadj)：指向依附于該頂點的下一個邊結(jié)點的指針。,無向圖鄰接表的鄰接表結(jié)點類的代碼參見P197頁 。,用鄰接表解決圖的編程問題 用鄰接表表示圖 （舉例）,對鄰接表進行操作的代碼參見P199頁 。,9.4解決圖的遍歷問題深度優(yōu)先搜索,1.理解深度優(yōu)先搜索算法,從圖的某一頂點x出發(fā)，訪問x，然后遍歷任何一個與x相鄰的未被訪問的頂點y，再遍歷任何一個與y相鄰的未被訪問的頂點z，如此下

8、去，直到到達一個所有鄰接點都被訪問的頂點為止。然后依次回退到尚有鄰接點未被訪問過的頂點，重復(fù)上述過程，直到圖中的全部頂點都被訪問過為止。,對圖進行深度優(yōu)先遍歷。深度優(yōu)先遍歷背后基于堆棧，有2種形式: 第一種是程序中顯示構(gòu)造堆棧，利用壓棧出棧操作實現(xiàn);第二種是利用遞歸函數(shù)調(diào)用，基于遞歸程序棧實現(xiàn)。本章介紹壓棧和出棧的操作。,v1,將起始頂點v1壓入棧。,9.4解決圖的遍歷問題深度優(yōu)先搜索,v1,將頂點v1彈出棧 訪問 v1 在棧中壓入所有與v1相鄰接的未訪問頂點,v1,Visited:,9.4解決圖的遍歷問題深度優(yōu)先搜索,v4,從棧中彈出頂點 v1 訪問 v1 在棧中壓入所有與v1相鄰接的未訪問

9、頂點,v1,Visited:,v2,9.4解決圖的遍歷問題深度優(yōu)先搜索,Visited:,從棧中彈出頂點 v2 訪問 v2 在棧中壓入所有與v2相鄰接的未訪問頂點,v1,v2,v4,v2,9.4解決圖的遍歷問題深度優(yōu)先搜索,Visited:,從棧中彈出頂點 v2 訪問 v2 在棧中壓入所有與v2相鄰接的未訪問頂點,v1,v2,v3,v6,v4,9.4解決圖的遍歷問題深度優(yōu)先搜索,Visited:,從棧中彈出頂點 v3 訪問v3 在棧中壓入所有與v3相鄰接的未訪問頂點,v1,v2,v3,有與v3相鄰接的未訪問頂點,v6,v3,v4,9.4解決圖的遍歷問題深度優(yōu)先搜索,Visited:,從棧中彈出

10、頂點 v3 訪問v3 在棧中壓入所有與v3相鄰接的未訪問頂點,v1,v2,v3,有與v3相鄰接的未訪問頂點,v6,v5,v4,9.4解決圖的遍歷問題深度優(yōu)先搜索,Visited:,從棧中彈出頂點 v5 訪問v5 在棧中壓入所有與v5相鄰接的未訪問頂點,v1,v2,v3,v5,v6,v4,9.4解決圖的遍歷問題深度優(yōu)先搜索,v5,Visited:,從棧中彈出頂點 v6 訪問v6 在棧中壓入所有與v6相鄰接的未訪問頂點,v1,v2,v3,v5,v6,v6,v4,9.4解決圖的遍歷問題深度優(yōu)先搜索,Visited:,從棧中彈出頂點 v4 訪問v4 在棧中壓入所有與v4相鄰接的未訪問頂點,v1,v2,

11、v3,v5,v6,v4,v4,9.4解決圖的遍歷問題深度優(yōu)先搜索,Visited:,?，F(xiàn)在是空的 因此，遍歷完成,v1,v2,v3,v5,v6,v4,9.4解決圖的遍歷問題深度優(yōu)先搜索,盡管上述算法提供了一個簡單和常用的方法來遍歷圖，但是，如果圖不是連接的，算法將不能正確工作。 在這樣的情況下，你將不能夠從單個起始頂點開始遍歷所有頂點。,9.4解決圖的遍歷問題深度優(yōu)先搜索,為了解決這個問題，你需要對圖中所有未訪問頂點重復(fù)執(zhí)行上述算法。,對圖中每個頂點v重復(fù)步驟2 如果v未被訪問： a. 調(diào)用 DFS(v),9.4解決圖的遍歷問題深度優(yōu)先搜索,9.4解決圖的遍歷問題廣度優(yōu)先搜索,2.理解廣度優(yōu)先

12、搜索算法,圖的廣度優(yōu)先搜索是從圖的某個頂點x出發(fā)，訪問x。然后訪問與x相鄰接的所有未被訪問的頂點x1,x2,.,xn；接著再依次訪問與x1,x2,.,xn相鄰接的未被訪問過的所有頂點。依此類推，直至圖的每個頂點都被訪問。,訪問 v1 將v1 插入隊列,v1,v1,9.4解決圖的遍歷問題廣度優(yōu)先搜索,從隊列中刪除頂點 v1 訪問與v1相鄰接的所有未訪問頂點并將它們插入隊列,v1,v1,Visited:,9.4解決圖的遍歷問題廣度優(yōu)先搜索,從隊列中刪除頂點 v1 訪問與v1相鄰接的所有未訪問頂點并將它們插入隊列,v2,v1,v2,v4,v4,9.4解決圖的遍歷問題廣度優(yōu)先搜索,從隊列中刪除頂點 v

13、2 訪問與v2相鄰接的所有未訪問頂點并將它們插入隊列,v2,v1,v2,v4,v4,9.4解決圖的遍歷問題廣度優(yōu)先搜索,從隊列中刪除頂點 v4 訪問與v4相鄰接的所有未訪問頂點并將它們插入隊列,v1,v2,v4,v4,v3,v3,v6,v6,v5,v5,9.4解決圖的遍歷問題廣度優(yōu)先搜索,從隊列中刪除頂點 v3 訪問與v3相鄰接的所有未訪問頂點并將它們插入隊列,v1,v2,v4,v3,v3,v6,v6,v5,v5,v3沒有任何未訪問的鄰接頂點,9.4解決圖的遍歷問題廣度優(yōu)先搜索,從隊列中刪除頂點 v6 訪問與v6相鄰接的所有未訪問頂點并將它們插入隊列,v1,v2,v4,v3,v6,v6,v5,

14、v5,v3沒有任何未訪問的鄰接頂點,9.4解決圖的遍歷問題廣度優(yōu)先搜索,從隊列中刪除頂點 v5 訪問與v5相鄰接的所有未訪問頂點并將它們插入隊列,v1,v2,v4,v3,v6,v5,v5,v6沒有任何未訪問的鄰接頂點,9.4解決圖的遍歷問題廣度優(yōu)先搜索,隊列現(xiàn)在是空的 因此，遍歷完成,v1,v2,v4,v3,v6,v5,v5沒有任何未訪問的鄰接頂點,9.4解決圖的遍歷問題廣度優(yōu)先搜索,盡管上述算法提供了一個簡單和方便的遍歷圖的方法，但是，如果圖不是連接的，算法將不能正確工作。 在這樣的情況中，你將不能從單個開始頂點遍歷所有頂點。,9.4解決圖的遍歷問題廣度優(yōu)先搜索,為了解決這個問題，你需要對圖

15、中的未訪問頂點重復(fù)執(zhí)行這個算法。,為圖中每個頂點V重復(fù)步驟2。 如果 v 未被訪問： a. 調(diào)用BFS(v),9.4解決圖的遍歷問題廣度優(yōu)先搜索,圖的最短路徑問題 Dijkstra算法的引入,Dijkstra算法的基本思想是： 設(shè)置兩個頂點集合T和S，集合S中存放己經(jīng)找到最短路徑的頂點，集合T中存放當前還未找到最短路徑的頂點。初始狀態(tài)時，集合S中只包含源點v0，然后不斷從集合T中選取到源點v0路徑長度最短的頂點w加入集合S，集合S中每加入一個新的頂點w，都要修改頂點v0到集合T中剩余頂點的最短路徑長度值，集合T中各頂點新的最短路徑長度值為原來最短路徑長度值與頂點w的最短路徑長度加上w到該頂點的

16、路徑長度值中的較小值。此過程不斷重復(fù)，直到集合T的頂點全部加入集合S為止。,圖的最短路徑問題 分析高速公路交通網(wǎng)的最短路徑,下面用Dijkstra算法解決高速公路最短路徑的問題?，F(xiàn)在假設(shè)高速公路交通網(wǎng)采用鄰接矩陣作為存儲結(jié)構(gòu)。若鄰接矩陣為matrix，并規(guī)定：,用Dijkstra算法來確定從城市A到其他城市的最短踐離。Dijkstra算法的步驟 參見教材P212頁,final,distance,1,1,0,0,0,0,0,90,150,180,圖的最短路徑問題 分析高速公路交通網(wǎng)的最短路徑,A,B,C,D,E,F,0,1,2,3,4,5,final,distance,1,1,0,0,0,0,0

17、,90,150,140,180,圖的最短路徑問題 分析高速公路交通網(wǎng)的最短路徑,A,B,C,D,E,F,0,1,2,3,4,5,final,distance,1,1,0,1,0,0,0,90,150,140,180,圖的最短路徑問題 分析高速公路交通網(wǎng)的最短路徑,A,B,C,D,E,F,0,1,2,3,4,5,final,distance,1,1,0,1,0,0,0,90,150,140,250,180,圖的最短路徑問題 分析高速公路交通網(wǎng)的最短路徑,A,B,C,D,E,F,0,1,2,3,4,5,final,distance,1,1,1,1,0,0,0,90,150,140,250,180,

18、圖的最短路徑問題 分析高速公路交通網(wǎng)的最短路徑,A,B,C,D,E,F,0,1,2,3,4,5,final,distance,1,1,1,1,0,0,0,90,150,140,250,180,圖的最短路徑問題 分析高速公路交通網(wǎng)的最短路徑,A,B,C,D,E,F,0,1,2,3,4,5,final,distance,1,1,1,1,0,1,0,90,150,140,250,180,圖的最短路徑問題 分析高速公路交通網(wǎng)的最短路徑,A,B,C,D,E,F,0,1,2,3,4,5,final,distance,1,1,1,1,0,1,0,90,150,140,210,180,圖的最短路徑問題 分析高速公路交通網(wǎng)的最短路徑,A,B,C,D,E,F,0,1,2,3,