解決圖的編程問題

《解決圖的編程問題》由會員分享，可在線閱讀，更多相關(guān)《解決圖的編程問題（48頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,解決圖的編程問題,數(shù)據(jù)結(jié)構(gòu),(C#,語言版,),解決圖的編程問題,數(shù)據(jù)結(jié)構(gòu),(C#,語言版,),目標(biāo),在本章中,你將學(xué)到,:,在圖中存儲數(shù)據(jù),圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法,最小生成樹,圖的最短路徑,學(xué)習(xí)情境,用圖高速公路交通網(wǎng)的編程,問題描述,一個(gè)地區(qū)由許多城市組成，為實(shí)現(xiàn)城市間的高速運(yùn)輸，需要在這些城市間鋪設(shè)高速公路，以達(dá)到任意兩個(gè)城市間高速運(yùn)輸?shù)哪康?。?jīng)過考察和預(yù)算，鋪設(shè)的高速公路交通網(wǎng)如圖,9.1,所示。其中每個(gè)頂點(diǎn)代表一個(gè)城市，頂點(diǎn)間的連線代表兩個(gè)城市間鋪設(shè)的高速公路，而線上的數(shù)字表示兩個(gè)城市

2、間的距離（單位：公理）。如圖所示。,請根據(jù)上面的描述，解決下面的問題：,用,C#,編寫一程序來存儲該高速公路交通網(wǎng)的信息。,從任何一個(gè)城市出發(fā)，訪問所有的城市，給出訪問城市的順序。,如果想從一個(gè)城市到另一個(gè)城市旅行，給出最短的旅行路線。,圖是一系列頂點(diǎn)（結(jié)點(diǎn)）和描述頂點(diǎn)之間的關(guān)系邊（弧）組成。圖是數(shù)據(jù)元素的集合，這些數(shù)據(jù)元素被相互連接以形成網(wǎng)絡(luò)。其形式化定義為：,G=,（,V,，,E,）,V=V,i,|V,i,某個(gè)數(shù)據(jù)元素集合,E=(,V,i,V,j,)|,V,i,V,j,VP(V,i,V,j,),認(rèn)識圖,圖的定義和術(shù)語,1.,圖的定義,其中，,G,表示圖，,V,是頂點(diǎn)的集合，,E,是邊或弧的

3、集合。在集合,E,中，,P(V,i,V,j,),表示頂點(diǎn),V,i,和頂點(diǎn),V,j,之間有邊或弧相連。,認(rèn)識圖,圖的定義和術(shù)語,2.,圖的術(shù)語,頂點(diǎn)集：圖中具有相同特性的數(shù)據(jù)元素的集合稱為頂點(diǎn)集,邊（?。哼吺且粚旤c(diǎn)間的路徑，通常帶箭頭的邊稱為弧,弧頭：每條箭頭線的頭頂點(diǎn)表示構(gòu)成弧的有序?qū)χ械暮笠粋€(gè),弧尾：每條箭頭線的尾頂點(diǎn)表示構(gòu)成弧的有序?qū)χ械那耙粋€(gè)頂點(diǎn)，稱為弧尾或始點(diǎn)。,度：在無向圖中的頂點(diǎn)的度是指連那個(gè)頂點(diǎn)的邊的數(shù)量。在有向圖中，每個(gè)頂點(diǎn)有兩種類的的度：出度和入度。,入度：頂點(diǎn)的入度是指向那個(gè)頂點(diǎn)的邊的數(shù)量。,出度：頂點(diǎn)的出度是由那個(gè)頂點(diǎn)出發(fā)的邊的數(shù)量。,權(quán)：有些圖的邊（或弧）附帶有一些

4、數(shù)據(jù)信息，這些數(shù)據(jù)信息稱為邊（或弧）的權(quán)（,weigh,）,.,認(rèn)識圖,圖的定義和術(shù)語,3.,圖的分類,有向圖：在一個(gè)圖中，如果任意兩頂點(diǎn)構(gòu)成的偶對（,Vi,Vj,）是有序的，那么稱該圖為有向圖。這里,Vi,是弧尾，,Vj,是弧頭。這表示有一個(gè)從頂點(diǎn),Vi,到頂點(diǎn),Vj,的路徑。但是從,Vj,到,Vi,是不可能的,無向圖：在一個(gè)圖中，如果有任意兩頂點(diǎn)構(gòu)成的邊（,Vi,Vj,），（,Vi,Vj,）和（,Vj,，,Vi,）是相同的,在一個(gè)無向圖中，如果任意兩個(gè)頂點(diǎn)之間都有邊相連，則稱該圖為無向完全圖。無向完全圖又稱完全圖,在一個(gè)有向圖，如果任意兩個(gè)頂點(diǎn)之間都是弧相連，則稱該圖為有向完全圖。,有很少

5、條邊或弧的圖稱為稀疏圖，反之稱為稠密圖。,SetNode,(),：在圖中增加一個(gè)新的頂點(diǎn),GetNode,(),：獲取圖中指定頂點(diǎn),SetEdge,(),：在兩個(gè)頂點(diǎn)之間添加指定權(quán)值的邊或弧,GetEdge,(),：獲取兩個(gè)頂點(diǎn)之間的邊,DelEdge,(),：刪除兩個(gè)頂點(diǎn)之間的邊或弧,GetNumOfVertex,(),：獲取鄰接矩陣頂點(diǎn)數(shù),GetNumOfEdge,(),：獲取鄰接矩陣邊或弧的數(shù)目,GetIndex,(),：獲取指定頂點(diǎn)在數(shù)組中的索引,IsEdge,(),：判斷兩個(gè)頂點(diǎn)之間是否存在邊或弧,IsNode,(),：判斷指定結(jié)點(diǎn)是否是圖的頂點(diǎn),認(rèn)識圖,識別圖的基本操作,圖的基本操

6、作有以下幾種：,鄰接矩陣,(,Adjacentcy,Matrix),是用兩個(gè)數(shù)組來表示圖，一個(gè)數(shù)組是一維數(shù)組，存儲圖中的頂點(diǎn)信息，一個(gè)數(shù)組是二維數(shù)組，即矩陣，存儲頂點(diǎn)之間相鄰的信息，也就是邊（或?。┑男畔?。如果圖中有,n,個(gè)頂點(diǎn)，你需要大小為,nn,的二維數(shù)組來表示圖。,用,C#,語言表示鄰接矩陣的代碼 參見,P190,頁,用鄰接矩陣解決圖的編程問題,用鄰接矩陣表示圖,對鄰接矩陣進(jìn)行操作參見,P191,頁代碼。,鄰接表的存儲方法是一種順序存儲與鏈?zhǔn)酱鎯ο嘟Y(jié)合的存儲方法，順序存儲部分用來保存圖中頂點(diǎn)的信息，鏈?zhǔn)酱鎯Σ糠钟脕肀４鎴D中邊（或?。┑男畔?。具體的做法是：使用一個(gè)一維數(shù)組，其中每個(gè)數(shù)組元素

7、包含兩個(gè)域，其結(jié)構(gòu)如右圖所示。,其中,頂點(diǎn)域（,data,）：存放與頂點(diǎn)有關(guān)的信息；,頭指針域（,firstadj,）：存放與該頂點(diǎn)相鄰接的所有頂點(diǎn)組成的單鏈表的頭指針,用鄰接表解決圖的編程問題,用鄰接表表示圖,鄰接單鏈表中每個(gè)結(jié)點(diǎn)表示依附于該頂點(diǎn)的一條邊，稱作邊結(jié)點(diǎn)，邊結(jié)點(diǎn)的結(jié)構(gòu)如右圖所示。,其中,鄰接點(diǎn)域,(,adjvex,),：指示與頂點(diǎn)鄰接點(diǎn)在圖中的位置，對應(yīng)著一維,數(shù)組中的序號，對于有向圖，存放的是該邊結(jié)點(diǎn)所表示的弧的弧頭,頂點(diǎn)在一維數(shù)組中的序號；,數(shù)據(jù)域,(info),：存儲邊或弧相關(guān)的信息，如權(quán)值等，當(dāng)圖中邊（或弧）,不含有信息時(shí)，該域可以省略。,鏈域,(,nextadj,),：

8、指向依附于該頂點(diǎn)的下一個(gè)邊結(jié)點(diǎn)的指針。,無向圖鄰接表的鄰接表結(jié)點(diǎn)類的代碼參見,P197,頁。,用鄰接表解決圖的編程問題,用鄰接表表示圖（舉例）,對鄰接表進(jìn)行操作的代碼參見,P199,頁。,9.4,解決圖的遍歷問題,深度優(yōu)先搜索,1.,理解深度優(yōu)先搜索算法,從圖的某一頂點(diǎn),x,出發(fā)，訪問,x,，然后遍歷任何一個(gè)與,x,相鄰的未被訪問的頂點(diǎn),y,，再遍歷任何一個(gè)與,y,相鄰的未被訪問的頂點(diǎn),z,，如此下去，直到到達(dá)一個(gè)所有鄰接點(diǎn)都被訪問的頂點(diǎn)為止。然后依次回退到尚有鄰接點(diǎn)未被訪問過的頂點(diǎn)，重復(fù)上述過程，直到圖中的全部頂點(diǎn)都被訪問過為止。,對圖進(jìn)行深度優(yōu)先遍歷。深度優(yōu)先遍歷背后基于堆棧，有,2,種形

9、式,:,第一種是程序中顯示構(gòu)造堆棧，利用壓棧出棧操作實(shí)現(xiàn),;,第二種是利用遞歸函數(shù)調(diào)用，基于遞歸程序棧實(shí)現(xiàn)。本章介紹壓棧和出棧的操作,。,v1,將起始頂點(diǎn),v1,壓入棧。,9.4,解決圖的遍歷問題,深度優(yōu)先搜索,v1,將頂點(diǎn),v1,彈出棧,訪問,v1,在棧中壓入所有與,v1,相鄰接的未訪問頂點(diǎn),v1,Visited:,9.4,解決圖的遍歷問題,深度優(yōu)先搜索,v4,從棧中彈出頂點(diǎn),v1,訪問,v1,在棧中壓入所有與,v1,相鄰接的未訪問頂點(diǎn),v1,Visited:,v2,9.4,解決圖的遍歷問題,深度優(yōu)先搜索,Visited:,從棧中彈出頂點(diǎn),v2,訪問,v2,在棧中壓入所有與,v2,相鄰接的未

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

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

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

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

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

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

16、廣度優(yōu)先搜索,為了解決這個(gè)問題，你需要對圖中的未訪問頂點(diǎn)重復(fù)執(zhí)行這個(gè)算法。,為圖中每個(gè)頂點(diǎn),V,重復(fù)步驟,2,。,如果,v,未被訪問：,a.,調(diào)用,BFS(v,),9.4,解決圖的遍歷問題,廣度優(yōu)先搜索,圖的最短路徑問題,Dijkstra,算法的引入,Dijkstra,算法的基本思想是：,設(shè)置兩個(gè)頂點(diǎn)集合,T,和,S,，集合,S,中存放己經(jīng)找到最短路徑的頂點(diǎn)，集合,T,中存放當(dāng)前還未找到最短路徑的頂點(diǎn)。初始狀態(tài)時(shí)，集合,S,中只包含源點(diǎn),v,0,，然后不斷從集合,T,中選取到源點(diǎn),v,0,路徑長度最短的頂點(diǎn),w,加入集合,S,，集合,S,中每加入一個(gè)新的頂點(diǎn),w,，都要修改頂點(diǎn),v,0,到集合,T,中剩余頂點(diǎn)的最短路徑長度值，集合,T,中各頂點(diǎn)新的最短路徑長度值為原來最短路徑長度值與頂點(diǎn),w,的最短路徑長度加上,w,到該頂點(diǎn)的路徑長度值中的較小值。此過程不斷重復(fù)，直到集合,T,的頂點(diǎn)全部加入集合,S,為止。,圖的最短路徑問題,分析高速公路交通網(wǎng)的最短路徑,下面用,Dijkstra,算法解決高速公路最短路徑的問題?，F(xiàn)在假設(shè)高速公路交通網(wǎng)采用鄰接矩陣作為存儲結(jié)構(gòu)。若鄰接矩陣為,matrix