圖的定義和術(shù)語

1、第 1 頁第 2 頁 第七章第七章 圖圖7.1 圖的定義和術(shù)語7.2 圖的存儲結(jié)構(gòu)7.3 圖的遍歷7.4 圖的連通性問題7.5 有向無環(huán)圖及應(yīng)用7.6 最短路徑 第 3 頁第七第七 章章 圖圖本章介紹另一種非線性數(shù)據(jù)結(jié)構(gòu)本章介紹另一種非線性數(shù)據(jù)結(jié)構(gòu) 圖圖 圖：是一種多對多的結(jié)構(gòu)關(guān)系，每個元素可以有圖：是一種多對多的結(jié)構(gòu)關(guān)系，每個元素可以有零個或多個直接前趨；零個或多個直接后繼；零個或多個直接前趨；零個或多個直接后繼；第 4 頁第七第七 章章 圖圖 學(xué)習(xí)要點學(xué)習(xí)要點1熟悉圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法，了解實際問題的求熟悉圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法，了解實際問題的求解效率與采用何種存儲結(jié)構(gòu)和算法

2、有密切聯(lián)系；解效率與采用何種存儲結(jié)構(gòu)和算法有密切聯(lián)系；2熟練掌握圖的兩種遍歷：深度優(yōu)先遍歷和廣度優(yōu)先遍歷的熟練掌握圖的兩種遍歷：深度優(yōu)先遍歷和廣度優(yōu)先遍歷的算法。在學(xué)習(xí)中應(yīng)注意圖的遍歷算法與樹的遍歷算法之間的類算法。在學(xué)習(xí)中應(yīng)注意圖的遍歷算法與樹的遍歷算法之間的類似和差異。樹的先根遍歷是一種深度優(yōu)先搜索策略，樹的層次似和差異。樹的先根遍歷是一種深度優(yōu)先搜索策略，樹的層次遍歷是一種廣度優(yōu)先搜索策略遍歷是一種廣度優(yōu)先搜索策略3理解課件中討論的各種圖的算法；理解課件中討論的各種圖的算法；第 5 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語一一 圖的概念圖的概念 圖圖G G由兩個集合構(gòu)成，記作由兩個

3、集合構(gòu)成，記作G=G= 其中其中V V是頂點的非空有限集合，是頂點的非空有限集合，E E是邊的有限集合，其中邊是頂點的無序?qū)蛴行驅(qū)稀Ｊ沁叺挠邢藜?，其中邊是頂點的無序?qū)蛴行驅(qū)?。例?G1=G1=V1=vV1=v1 1,v,v2 2, ,v v3 3, ,v v4 4 ,v,v5 5 E1=(vE1=(v1 1,v,v2 2),),(v(v1 1,v,v3 3),),(v(v2 2,v,v3 3),),(v(v2 2,v,v5 5),),(v(v3 3,v,v4 4),),(v(v3 3,v,v5 5) ) G1G1圖示圖示無序?qū)o序?qū)? (v vi i,v,vj j) )：用表示頂

4、點用表示頂點v vi i、v vj j的線段的線段，稱為無向邊；，稱為無向邊； V5V5 V1 V1 V2V2 V4V4 V3V3第 6 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語例例 G2=G2=V2=vV2=v1 1,v,v2 2, ,v v3 3, ,v v4 4 E2=vE2=, , , , , , G2圖示有序?qū)τ行驅(qū)?：用以表示以用以表示以v vi i起點、以起點、以v vj j為終點的有向線段，為終點的有向線段，稱為有向邊或??；稱為有向邊或?。粺o向圖：無向圖：在圖在圖G G中，若中，若所有邊是無向邊，則稱所有邊是無向邊，則稱G G為無向圖；為無向圖；有有向圖：向圖：在圖在圖G

5、 G中，若所有邊是有向邊，則稱中，若所有邊是有向邊，則稱G G為有向圖；為有向圖；混和圖：混和圖：在圖在圖G G中，即有無向邊也有有向邊，則稱中，即有無向邊也有有向邊，則稱G G為混合圖；為混合圖； V1V1 V2V2 V3V3 V4V4V1V1稱為弧尾稱為弧尾( (初始點初始點) )V3V3稱為弧頭稱為弧頭( (終端點終端點) )第 7 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語2圖的應(yīng)用舉例例例1 1 交通圖（公路、鐵路）交通圖（公路、鐵路） 頂點：地點頂點：地點 邊：連接地點的公路邊：連接地點的公路 交通圖中的有單行道雙行道，分別用有向邊、無向邊表示交通圖中的有單行道雙行道，分別用有

6、向邊、無向邊表示；例例2 2 電路圖電路圖 頂點：元件頂點：元件 邊：連接元件之間的線路邊：連接元件之間的線路例例3 3 通訊線路圖通訊線路圖 頂點：地點頂點：地點 邊：地點間的連線邊：地點間的連線例例4 4 各種流程圖各種流程圖 如如產(chǎn)品的生產(chǎn)流程圖產(chǎn)品的生產(chǎn)流程圖 頂點：工序頂點：工序 邊：各道工序之間的順序關(guān)系邊：各道工序之間的順序關(guān)系 V5V5 V1 V1 V2V2 V4V4 V3V3第 8 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語三 圖的基本操作1 1 CreateGraph(&GCreateGraph(&G, V, VR);, V, VR);初始條件：初始條件：V V是圖的頂

7、點集，是圖的頂點集，VRVR是圖中弧的集合是圖中弧的集合操作結(jié)果：按操作結(jié)果：按V V和和VRVR的定義構(gòu)造圖的定義構(gòu)造圖G G2 2 DestroyGraph(&GDestroyGraph(&G););初始條件：圖初始條件：圖G G存在存在操作結(jié)果：銷毀圖操作結(jié)果：銷毀圖G G3 3 LocateVex(G,uLocateVex(G,u););初始條件：圖初始條件：圖G G存在，存在，u u和和G G中頂點有相同特征中頂點有相同特征操作結(jié)果：若操作結(jié)果：若G G中存在頂點中存在頂點u u，則返回該頂點在圖中位置；否則返回其它則返回該頂點在圖中位置；否則返回其它信息。信息。4 4 GetVex

8、(GGetVex(G, v);, v);初始條件：圖初始條件：圖G G存在，存在，v v是是G G中某個頂點中某個頂點操作結(jié)果：返回操作結(jié)果：返回v v的值的值5 5 PutVex(&GPutVex(&G, v, value);, v, value);初始條件：圖初始條件：圖G G存在，存在，v v是是G G中某個頂點中某個頂點操作結(jié)果：對操作結(jié)果：對v v賦值賦值valuevalue第 9 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語6 6 FirstAdjVex(GFirstAdjVex(G, v);, v);初始條件：圖初始條件：圖G G存在，存在，v v是是G G中某個頂點中某個頂點

9、操作結(jié)果：返回操作結(jié)果：返回v v的第一個鄰接頂點。若頂點在的第一個鄰接頂點。若頂點在G G中沒有鄰接頂點，則返中沒有鄰接頂點，則返回回“空空”。7 7 NextAdjVex(GNextAdjVex(G, v, w);, v, w);初始條件：圖初始條件：圖G G存在，存在，v v是是G G中某個頂點，中某個頂點，w w是是v v的鄰接頂點。的鄰接頂點。操作結(jié)果：返回操作結(jié)果：返回v v的（相對于的（相對于w w的）下一個鄰接頂點。若的）下一個鄰接頂點。若w w是是v v的最后一個的最后一個鄰接點，則返回鄰接點，則返回“空空”。8 8 InsertVex(&GInsertVex(&G, v);

10、, v);初始條件：圖初始條件：圖G G存在，存在，v v和圖中頂點有相同特征。和圖中頂點有相同特征。操作結(jié)果：在圖操作結(jié)果：在圖G G中增添新頂點中增添新頂點v v9 9 DeleteVex(&GDeleteVex(&G, v);, v);初始條件：圖初始條件：圖G G存在，存在，v v和圖中頂點有相同特征和圖中頂點有相同特征操作結(jié)果：刪除操作結(jié)果：刪除G G中頂點中頂點v v及相關(guān)的弧及相關(guān)的弧第 10 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語10 10 InsertArc(&GInsertArc(&G, v, w); , v, w); 初始條件：圖初始條件：圖G G存在，存在，v

11、v和和w w是是G G中兩個頂點。中兩個頂點。操作結(jié)果：在操作結(jié)果：在G G中增添弧中增添弧 ，若若G G是無向的，則還增添對稱弧是無向的，則還增添對稱弧 11 11 DeleteArc(&GDeleteArc(&G, v, w);, v, w);初始條件：圖初始條件：圖G G存在，存在，v v和和w w是是G G中兩個頂點。中兩個頂點。操作結(jié)果：在操作結(jié)果：在G G中刪除弧中刪除弧 ，若若G G是無向的，則還刪除對稱弧是無向的，則還刪除對稱弧 12 12 DFSTraverse(GDFSTraverse(G, v, Visit( );, v, Visit( );初始條件：圖初始條件：圖G G

12、存在，存在，v v是是G G中某個頂點，中某個頂點，VisitVisit是頂點的應(yīng)用函數(shù)。是頂點的應(yīng)用函數(shù)。操作結(jié)果：從頂點操作結(jié)果：從頂點v v起深度優(yōu)先遍歷圖起深度優(yōu)先遍歷圖G G，對每個頂點調(diào)用函數(shù)對每個頂點調(diào)用函數(shù)VisitVisit一次一次且僅一次。一旦且僅一次。一旦visit( )visit( )失敗，則操作失敗失敗，則操作失敗13 13 BFSTraverse(GBFSTraverse(G, v, Visit( );, v, Visit( );初始條件：圖初始條件：圖G G存在，存在，v v是是G G中某個頂點，中某個頂點，VisitVisit是頂點的應(yīng)用函數(shù)。是頂點的應(yīng)用函數(shù)。

13、操作結(jié)果：從頂點操作結(jié)果：從頂點v v起廣度優(yōu)先遍歷圖起廣度優(yōu)先遍歷圖G G，對每個頂點調(diào)用函數(shù)對每個頂點調(diào)用函數(shù)VisitVisit一次一次且一次。一旦且一次。一旦visit( )visit( )失敗，則操作失敗失敗，則操作失敗第 11 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語3 3圖的基本術(shù)語圖的基本術(shù)語1 1 鄰接點及關(guān)聯(lián)邊鄰接點及關(guān)聯(lián)邊 鄰接點：鄰接點：邊的兩個頂點邊的兩個頂點 關(guān)聯(lián)邊：關(guān)聯(lián)邊：若邊若邊e= (v, ue= (v, u), ), 則稱頂點則稱頂點v v、u u 關(guān)聯(lián)邊關(guān)聯(lián)邊e e （邊邊e e 依附于頂點依附于頂點v,uv,u) )2 2 頂點的度、入度、出度頂點

14、的度、入度、出度 頂點頂點V V的度的度= =與與V V相關(guān)聯(lián)的邊的數(shù)目相關(guān)聯(lián)的邊的數(shù)目 在有向圖中：在有向圖中： 頂點頂點V V的出度的出度= =以以V V為起點有向邊數(shù)為起點有向邊數(shù) 頂點頂點V V的入度的入度= =以以V V為終點有向邊數(shù)為終點有向邊數(shù) 頂點頂點V V的度的度= = V V的出度的出度+ +V V的入度的入度 設(shè)圖設(shè)圖G G的頂點數(shù)為的頂點數(shù)為n n，邊數(shù)為邊數(shù)為e e 圖的所有頂點的度數(shù)和圖的所有頂點的度數(shù)和 = 2 = 2* *e e （每條邊對圖的所有頂點的度數(shù)和（每條邊對圖的所有頂點的度數(shù)和“貢獻貢獻”2”2度）度） e1e1 V1V1 V2V2 V3V3 V4V

15、4 V5V5 V1 V1 V2V2 V4V4 V3V3第 12 頁3 有向完全圖、有向完全圖、無向完全圖無向完全圖有向完全圖有向完全圖n個頂點的有向圖最大邊數(shù)是個頂點的有向圖最大邊數(shù)是n(n-1)無向完全圖無向完全圖n個頂點的無向圖最大邊數(shù)是個頂點的無向圖最大邊數(shù)是n(n-1)/2權(quán)權(quán)(weight)與圖的邊或弧相關(guān)的數(shù)叫與圖的邊或弧相關(guān)的數(shù)叫網(wǎng)網(wǎng)帶權(quán)的圖叫帶權(quán)的圖叫7.1 圖的圖的定義和術(shù)語定義和術(shù)語第 13 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語 4 4路徑、回路路徑、回路 無向圖中的頂點序列無向圖中的頂點序列v1,v2,v1,v2, , ,vkvk, ,若若( (vi,vi+1)

16、vi,vi+1) E( i=1,2,E( i=1,2,k-1), k-1), v =v1, u =v =v1, u =vkvk, , 則稱該序列是從頂點則稱該序列是從頂點v v到頂點到頂點u u的的路徑路徑；若；若v=uv=u，則稱則稱該序列為該序列為回路回路； 有向圖有向圖D=(V，E）中的頂點序列中的頂點序列v1,v2,v1,v2, , ,vkvk, , 若若 vi,vi+1 E E ( i=1,2,( i=1,2,k-1), v =v1, u =k-1), v =v1, u =vkvk, , 則稱該序列是從頂點則稱該序列是從頂點v v到頂點到頂點u u的路的路徑；若徑；若v=uv=u，則

17、稱該序列為回路；則稱該序列為回路； 例例 在圖在圖1 1中，中，V1,V2V1,V2, ,V3,V4 V3,V4 是是V1V1到到V4V4的路徑；的路徑； V1,V2 V1,V2, ,V3,V4,V1V3,V4,V1是回路；是回路；在圖在圖2 2中，中，V1,V3V1,V3, ,V4 V4 是是V1V1到到V4V4的路徑；的路徑； V1,V3,V4,V1 V1,V3,V4,V1是回路；是回路； V5V5 V1 V1 V2V2 V4V4 V3V3 V1V1 V2V2 V3V3 V4V4圖1圖2第 14 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語5 5連通圖、（強連通圖）連通圖、（強連通圖）

18、在無（有）向圖在無（有）向圖G=G= V, E 中，若對任何兩個頂點中，若對任何兩個頂點v v、u u都存在從都存在從v v到到u u的路徑，則稱的路徑，則稱G G是連通圖（強連通圖）是連通圖（強連通圖） V5V5 V6V6 V3V3 V1V1 V2V2 V4V4連通圖連通圖非連通圖非連通圖 V5V5 V1 V1 V2V2 V4V4 V3V3第 15 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語6子圖子圖 設(shè)有兩個圖設(shè)有兩個圖G=（V，E）、）、G1=（V1，E1），），若若V1 V，E1 E，E1關(guān)聯(lián)的頂點都在關(guān)聯(lián)的頂點都在V1中，則稱中，則稱 G1是是G的子圖；的子圖；例例 圖圖2、圖、

19、圖3 是是 圖圖1 的子圖的子圖 V5V5 V1 V1 V2V2 V4V4 V3V3 V5V5 V1 V1 V2V2 V3V3 V5V5 V1 V1 V2V2 V4V4 V3V3圖圖1 1圖圖2 2圖圖3 3第 16 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語7連通分圖（強連通分量） 無向圖無向圖G的極大連通子圖稱為的極大連通子圖稱為G的連通分量的連通分量 極大連通子圖意思是：該子圖是極大連通子圖意思是：該子圖是G連通子圖，將連通子圖，將G的任何不在該子圖的任何不在該子圖中的頂點加入，子圖不再連通；中的頂點加入，子圖不再連通； 有向圖有向圖D的極大強連通子圖稱為的極大強連通子圖稱為D的強連

20、通分量的強連通分量 極大強連通子圖意思是：該子圖是極大強連通子圖意思是：該子圖是D強連通子圖，將強連通子圖，將D的任何不在該的任何不在該子圖中的頂點加入，子圖不再是強連通的；子圖中的頂點加入，子圖不再是強連通的； V5V5 V6V6 V3V3 V1V1 V2V2 V4V4連通分圖連通分圖第 17 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語 V5V5 V1 V1 V2V2 V4V4 V3V3 V5V5 V1 V1 V2V2 V4V4 V3V38 生成樹（ 包含無向圖包含無向圖G所有頂點的的極小連通子圖稱為所有頂點的的極小連通子圖稱為G生成樹生成樹 極小連通子圖意思是：該子圖是極小連通子圖意思

21、是：該子圖是G的連通子圖，在該子圖中刪除任的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通，何一條邊，子圖不再連通， 若若T是是G的生成樹的生成樹當且僅當當且僅當T滿足如下條件滿足如下條件 T是是G的連通子圖的連通子圖 T包含包含G的所有頂點的所有頂點 T中無回路中無回路 只有足以構(gòu)成一棵樹的只有足以構(gòu)成一棵樹的n-1條邊條邊第 18 頁例213213有向完全圖有向完全圖無向完全圖無向完全圖356例245136圖與子圖圖與子圖例245136G1頂點頂點2入度：入度：1 出度：出度：3頂點頂點4入度：入度：1 出度：出度：0例157324G26頂點頂點5的度：的度：3頂點頂點2的度：的度：4第

22、 19 頁例157324G26例245136G1路徑：路徑：1，2，3，5，6，3路徑長度：路徑長度：5簡單路徑：簡單路徑：1，2，3，5回路：回路：1，2，3，5，6，3，1簡單回路：簡單回路：3，5，6，3路徑：路徑：1，2，5，7，6，5，2，3路徑長度：路徑長度：7簡單路徑：簡單路徑：1，2，5，7，6回路：回路：1，2，5，7，6，5，2，1簡單回路：簡單回路：1，2，3，1第 20 頁連通圖連通圖例245136強連通圖強連通圖356例非連通圖連通分量非連通圖連通分量例245136第 21 頁第七第七 章章 圖圖 7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)1數(shù)組表示法2鄰接表第 22

23、頁7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu) 圖是多對多的結(jié)構(gòu)，比線性結(jié)構(gòu)、樹結(jié)構(gòu)復(fù)雜，所以其存儲結(jié)構(gòu)也圖是多對多的結(jié)構(gòu)，比線性結(jié)構(gòu)、樹結(jié)構(gòu)復(fù)雜，所以其存儲結(jié)構(gòu)也要復(fù)雜些。與線性結(jié)構(gòu)、樹結(jié)構(gòu)一樣，圖的存儲結(jié)構(gòu)至少要保存兩類信要復(fù)雜些。與線性結(jié)構(gòu)、樹結(jié)構(gòu)一樣，圖的存儲結(jié)構(gòu)至少要保存兩類信息：息：1)1)頂點的數(shù)據(jù)頂點的數(shù)據(jù) 2) 2)頂點間的關(guān)系頂點間的關(guān)系頂點的編號頂點的編號 為了使圖的存儲結(jié)構(gòu)與圖一一對應(yīng)，在討論圖的存儲結(jié)構(gòu)時，首先為了使圖的存儲結(jié)構(gòu)與圖一一對應(yīng)，在討論圖的存儲結(jié)構(gòu)時，首先要給圖的所有頂點編號。要給圖的所有頂點編號。 本課程介紹兩類圖的存儲結(jié)構(gòu)本課程介紹兩類圖的存儲結(jié)構(gòu)數(shù)組表示

24、法數(shù)組表示法鄰接表（鄰接表，逆鄰接表）鄰接表（鄰接表，逆鄰接表） 設(shè)設(shè) G=G=是圖是圖, , V= V=v v1 1,v,v2 2, ,v v3 3, , v vn n , ,設(shè)頂點的設(shè)頂點的的的角標為它的編號 如何表示頂點間的關(guān)系？第 23 頁7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu) 鄰接矩陣鄰接矩陣：G G的鄰接矩陣是滿足如下條件的的鄰接矩陣是滿足如下條件的n n階階矩陣：矩陣： 一一 數(shù)組表示法數(shù)組表示法數(shù)組表示法是圖的一種順序存儲結(jié)構(gòu)數(shù)組表示法是圖的一種順序存儲結(jié)構(gòu)在數(shù)組表示法中，用鄰接矩陣表示頂點間的關(guān)系在數(shù)組表示法中，用鄰接矩陣表示頂點間的關(guān)系A(chǔ)ijAij=1 1 若若( (vi

25、,vi+1)vi,vi+1) E E 或或 vi,vi+1 E E0 0 否則否則 V5V5 V1 V1 V2V2 V4V4 V3V30 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 12 20 1 0 00 1 0 00 1 1 0 00 1 1 0 00 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 11 1 0 0 00 0 0 V1V1 V2V2 V3V3 V4V4第 24 頁7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)數(shù)組表示法頂點的存儲：用一維數(shù)組存儲（按編號順序）頂點間關(guān)系：用二維數(shù)組存儲圖的鄰接矩

26、陣；0 01 12 23 34 45 5m-1V1V1V2V2V3V3V4V4V5V5存儲頂點的一維數(shù)組存儲鄰接矩陣的二維數(shù)組0 01 10 01 10 01 10 01 10 01 10 01 12 23 34 4mm+1m+2m+3m+4第 25 頁7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)數(shù)組表示法類型定義#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20typedef enumDG, DN, AG, AN GraphKind;typedef struct ArcCell VRType adj; InfoType *info;ArcCell,

27、 AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM typedef struct VetexType vexsMAX_VERTEX_NUM ; AdjMatrix arc; int vexnum, arcnum; GraphKind kind;MGraph;第 26 頁7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)設(shè)G是Mgraph 類型的變量，用于存儲無向圖，該圖有n個頂點，e條邊G的圖示如下：G.vexs G.arcs G.vexnumG.arcnu G.kind V1V10 0n ne eAGAG頂點數(shù)組存儲鄰接矩陣的二維數(shù)組第 27 頁7.2 7.2 圖的存儲結(jié)構(gòu)

28、圖的存儲結(jié)構(gòu)無向圖數(shù)組表示法特點：1）無向圖鄰接矩陣是對稱矩陣，同一條邊表示了兩次；2）頂點v的度：等于二維數(shù)組對應(yīng)行（或列）中1的個數(shù)；3）判斷兩頂點v、u是否為鄰接點：只需判二維數(shù)組對應(yīng)分量是否為1；4）頂點不變，在圖中增加、刪除邊：只需對二維數(shù)組對應(yīng)分量賦值1或清0；5）設(shè)存儲頂點的一維數(shù)組大小為m(m圖的頂點數(shù)n), G占用存儲空間：m+m2；G占用存儲空間只與它的頂點數(shù)有關(guān)，與邊數(shù)無關(guān)；適用于邊稠密的圖；對有向圖的數(shù)組表示法可做類似的討論第 28 頁7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)2鄰接表 鄰接表是圖的鏈式存儲結(jié)構(gòu)1 無向圖的鄰接表頂點：通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組

29、中；關(guān)聯(lián)同一頂點的邊：用線性鏈表存儲 V5V5 V1 V1 V2V2 V4V4 V3V3例 0 0 1 1 2 2 3 3 4 4m-1m-1V1V1V2V2V3V3V4V4V5V51 13 34 42 22 21 11 10 00 04 43 3該結(jié)點表示邊（V1 V2）,其中的1是V2在一維數(shù)組中的位置第 29 頁7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)圖的鄰接表類型定義#define MAX_VERTEX_NUM 20typedef struct ArcNode /邊（弧）結(jié)點的類型定義邊（?。┙Y(jié)點的類型定義int adjvex; /邊（?。┑牧硪豁旤c的在數(shù)組中的位置邊（弧）的另一頂點的

30、在數(shù)組中的位置struct ArcNode *nextarc; /指向下一條邊（?。┙Y(jié)點的指針指向下一條邊（?。┙Y(jié)點的指針I(yè)nfoType *info;ArcNode;typedef struct VNode /頂點結(jié)點和數(shù)組的類型定義頂點結(jié)點和數(shù)組的類型定義VertexType data; /頂點信息頂點信息ArcNode * finrstarc; /指向關(guān)聯(lián)該頂點的邊（弧）鏈表指向關(guān)聯(lián)該頂點的邊（?。╂湵鞻Node, AjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum, arcnum; /圖的當前頂點數(shù)和弧數(shù)圖的當

31、前頂點數(shù)和弧數(shù)int kind; /圖的種類標志圖的種類標志ALGraph;第 30 頁7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)設(shè)G是ALGraph 類型的變量，用于存儲無向圖G1，該圖有n個頂點，e條邊G的圖示如下： V5V5 V1 V1 V2V2 V4V4 V3V3無向圖G1該結(jié)點表示邊（V5,V2）,其中的1是V2在一維數(shù)組中的位置G.vertices G.vexnum G.arcnu G.kind 0 0 1 1 2 2 4 4m-1m-1V1V1V2V2V3V3V4V4V5V5n ne eAGAG1 13 34 42 22 21 11 10 00 04 43 3data firsta

32、rcadjvex nextarc第 31 頁7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)無向圖的鄰接表的特點 1）在G鄰接表中，同一條邊對應(yīng)兩個結(jié)點； 2）頂點v的度：等于v對應(yīng)線性鏈表的長度； 3）判定兩頂點v ，u是否鄰接：要看v對應(yīng)線性鏈表中有無對應(yīng)的結(jié)點 4）在G中增減邊：要在兩個單鏈表插入、刪除結(jié)點； 第 32 頁7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)D.vertices D.vexnum D.arcnu D.kind V V1 1V V2 2V V3 3V V4 4n ne eDGDG1 12 23 30 0 V1V1 V2V2 V3V3 V4V4例2 有向圖的鄰接表和逆鄰接表1）有

33、向圖的鄰接表頂點：用一維數(shù)組存儲（按編號順序）以同一頂點為起點的弧：用線性鏈表存儲類似于無向圖的鄰接表，所不同的是：以同一頂點為起點的?。河镁€性鏈表存儲第 33 頁7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)2）有向圖的逆鄰接表頂點：用一維數(shù)組存儲（按編號順序）以同一頂點為終點的?。河镁€性鏈表存儲表類似于無向圖的鄰接表，所不同的是：以同一頂點為終點的?。河镁€性鏈表存儲D.vertices D.vexnum D.arcnu D.kind V V1 1V V2 2V V3 3V V4 4n ne eDGDG0 00 02 23 3 V1V1 V2V2 V3V3 V4V4第 34 頁7.2 7.2 圖的

34、存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu) 在不同的存儲結(jié)構(gòu)下，實現(xiàn)各種操作的效率可能是不同的。所以在求解實際問題時，要根據(jù)求解問題所需操作，選擇合適的存儲結(jié)構(gòu)。第 35 頁第七第七 章章 圖圖 7.3 7.3 圖的遍歷圖的遍歷一 深度優(yōu)先遍歷二 廣度優(yōu)先遍歷第 36 頁7.3 7.3 圖的遍歷圖的遍歷 圖的遍歷：從圖的某頂點出發(fā)，訪問圖中所有頂點，并且每個頂點僅訪問一次。 圖中可能有回路，遍歷可能沿回路又回到已遍歷過的結(jié)點。為避免同一頂點被多次訪問，必須為每個被訪問的頂點作一標志。為此引入一輔助數(shù)組， 記錄每個頂點是否被訪問過。 有兩種遍歷方法（它們對無向圖，有向圖都適用）： 深度優(yōu)先遍歷 廣度優(yōu)先遍歷第 37

35、頁7.3 7.3 圖的遍歷圖的遍歷一一 深度優(yōu)先遍歷深度優(yōu)先遍歷從圖中某頂點從圖中某頂點v v出發(fā)：出發(fā)： 1 1）訪問頂點）訪問頂點v v；2 2）從從v v的未被訪問的鄰接點出發(fā)，繼續(xù)對圖進行深度優(yōu)先遍歷；的未被訪問的鄰接點出發(fā)，繼續(xù)對圖進行深度優(yōu)先遍歷；例例 圖圖G G中，以中，以V1V1起點的起點的的的深度優(yōu)先序列：深度優(yōu)先序列： （1 1） V1,V2,V4,V5,V8,V3,V6,V7,V1,V2,V4,V5,V8,V3,V6,V7, （2 2） V1,V2,V5,V8,V4,V3,V6,V7 V1,V2,V5,V8,V4,V3,V6,V7 V8V8 V7V7 V6V6 V5V5

36、V4V4 V3V3 V2V2 V1V1由于沒為有規(guī)定由于沒為有規(guī)定訪問鄰接點的順序，訪問鄰接點的順序，深度優(yōu)先序列不是唯一的深度優(yōu)先序列不是唯一的這是序列（1）在遍歷過程中所經(jīng)過的路徑注：為簡單起見，只討論非空連通圖的遍歷第 38 頁7.3 7.3 圖的遍歷圖的遍歷深度優(yōu)先遍歷( (設(shè)圖為非空連通圖）設(shè)圖為非空連通圖）從圖中某頂點從圖中某頂點v v出發(fā)：出發(fā)： 1 1）訪問頂點）訪問頂點v v；2 2）從從v v的未被訪問的鄰接點出發(fā)，的未被訪問的鄰接點出發(fā)，繼續(xù)對圖進行深度優(yōu)先遍歷；繼續(xù)對圖進行深度優(yōu)先遍歷； 先序遍歷（先序遍歷（D DL LR R） 若二叉樹非空若二叉樹非空 （1 1）訪問

37、根結(jié)點；）訪問根結(jié)點； （2 2）先序遍歷左子樹；）先序遍歷左子樹； （3 3）先序遍歷右子樹）先序遍歷右子樹；如果將圖頂點的鄰接點如果將圖頂點的鄰接點看作二叉樹結(jié)點的左、右孩子看作二叉樹結(jié)點的左、右孩子深度優(yōu)先遍歷與深度優(yōu)先遍歷與先序遍歷先序遍歷是不是很類似？是不是很類似？ V8V8 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1第 39 頁7.3 7.3 圖的遍歷圖的遍歷深度優(yōu)先遍歷算法深度優(yōu)先遍歷算法void DFS(Graph G, int v, Status(*Visit(int v) / 從第從第v個頂點出發(fā)，遞歸地深度優(yōu)先遍歷圖個頂點出發(fā)，遞歸地深度優(yōu)先遍歷

38、圖G。 / v是頂點在一維數(shù)組中的位置，是頂點在一維數(shù)組中的位置，假設(shè)假設(shè)G G是非空圖是非空圖visitedv =TRUE; Visit(v); /訪問第訪問第v個頂點個頂點for (w= FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w)if (!visitedw) DFS(G, w); /對對v的尚未訪問的鄰接頂點的尚未訪問的鄰接頂點w遞歸調(diào)用遞歸調(diào)用DFSBoolean Boolean visitedMAX_VERTEX_NUMvisitedMAX_VERTEX_NUM /訪問標志數(shù)組訪問標志數(shù)組, ,全局變量，初始值：所有分量全為全局變量，初始值：

39、所有分量全為False(0)False(0)/visitedvvisitedv=TRUE=TRUE表示頂點表示頂點v v已被訪問已被訪問visited01234m-100000第 40 頁7.3 7.3 圖的遍歷圖的遍歷先序遍歷遞歸算法先序遍歷遞歸算法 void PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /本算法先序遍歷以本算法先序遍歷以T為根結(jié)點指針的二叉樹。為根結(jié)點指針的二叉樹。 if (T) /若二叉樹為空，結(jié)束返回若二叉樹為空，結(jié)束返回 Visit(T-data)； PreOrderTraverse(T-lchild,

40、 Visit); PreOrderTraverse(T-rchild, Visit); /PreOrderTraverse如果將圖頂點的鄰接點看作二叉樹結(jié)點的左、右孩子深度優(yōu)先遍歷算法與先序遍歷算法的結(jié)構(gòu)是不是很像？深度優(yōu)先遍歷算法深度優(yōu)先遍歷算法void DFS(Graph G, int v, Status(*Visit(int v) / 從第從第v個頂點出發(fā)，遞歸地深度優(yōu)先遍歷圖個頂點出發(fā)，遞歸地深度優(yōu)先遍歷圖G。 / v是頂點在一維數(shù)組中的位置，是頂點在一維數(shù)組中的位置，假設(shè)假設(shè)G G是非空圖是非空圖visitedv =TRUE; Visit(v); /訪問第訪問第v個頂點個頂點for

41、(w= FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w)if (!visitedw) DFS(G, w); /對對v的尚未訪問的鄰接頂點的尚未訪問的鄰接頂點w遞歸調(diào)用遞歸調(diào)用DFS第 41 頁7.3 7.3 圖的遍歷圖的遍歷2 2廣度優(yōu)先遍歷（類似于樹的按層遍歷）廣度優(yōu)先遍歷（類似于樹的按層遍歷） 從圖中某頂點從圖中某頂點v v出發(fā)：出發(fā)：1 1）訪問頂點訪問頂點v v ；2 2）訪問訪問v v的所有未被訪問的鄰接點的所有未被訪問的鄰接點w w1 1 ,w ,w2 2 , , w wk k ；3 3）依次依次從這些鄰接點出發(fā)，訪問它們的所有未被訪問的鄰接點

42、從這些鄰接點出發(fā)，訪問它們的所有未被訪問的鄰接點; ; 依此類依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；推，直到圖中所有訪問過的頂點的鄰接點都被訪問；例例 圖圖G G中，以中，以V1V1起點的起點的的廣的廣度優(yōu)先序列：度優(yōu)先序列： （1 1）V1,V1,V2,V3V2,V3, ,V4,V5,V6,V7,V8V4,V5,V6,V7,V8 （2 2）V1,V1,V3,V2V3,V2, ,V6,V7,V4,V5,V8V6,V7,V4,V5,V8 V8V8 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1這是序列（這是序列（1 1）在遍歷過程中在遍歷過程中所經(jīng)過的路徑所經(jīng)

43、過的路徑由于沒為有規(guī)定由于沒為有規(guī)定訪問鄰接點的順序，訪問鄰接點的順序，廣度優(yōu)先序列不是唯一的廣度優(yōu)先序列不是唯一的第 42 頁7.3 7.3 圖的遍歷圖的遍歷廣義優(yōu)先遍歷算法廣義優(yōu)先遍歷算法從圖中某頂點從圖中某頂點v v出發(fā)：出發(fā)：1 1）訪問頂點訪問頂點v v ；（；（容易實現(xiàn)）容易實現(xiàn)）2 2）訪問訪問v v的所有未被訪問的鄰接點的所有未被訪問的鄰接點w w1 1 ,w ,w2 2 , , w wk k ； （容易實現(xiàn)）容易實現(xiàn)）3 3）依次從依次從這些鄰接點這些鄰接點（在步驟（在步驟 2 2）訪問的頂點）出發(fā)，訪問它們的所有）訪問的頂點）出發(fā)，訪問它們的所有未被訪問的鄰接點未被訪問的鄰

44、接點; ; 依此類推，直到圖中所有訪問過的頂點的鄰接點都依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；被訪問；為實現(xiàn)為實現(xiàn) 3 3），），需要保存在步驟需要保存在步驟(2(2）中訪問的頂點，而且）中訪問的頂點，而且訪問這些頂點訪問這些頂點鄰鄰接點接點的順序為：先保存的頂點，其鄰接點先被訪問。的順序為：先保存的頂點，其鄰接點先被訪問。在在廣度優(yōu)先遍歷算法中，需設(shè)置一隊列廣度優(yōu)先遍歷算法中，需設(shè)置一隊列Q Q，保存已訪問的頂點，并控制遍歷頂點的順序。保存已訪問的頂點，并控制遍歷頂點的順序。第 43 頁7.3 7.3 圖的遍歷圖的遍歷void void BFSTraverse(GraphBFS

45、Traverse(Graph G,intG,int v,Statusv,Status ( (* * Visit)(intVisit)(int v) v) /從從v v出發(fā)，廣度優(yōu)先遍歷連通圖出發(fā)，廣度優(yōu)先遍歷連通圖G G。 v是頂點在一維數(shù)組中的位置，是頂點在一維數(shù)組中的位置，使使用輔助隊列用輔助隊列Q Q和訪問標志數(shù)組和訪問標志數(shù)組visitedvisited。 for (u=0; u for (u=0; ulchild=p; first=FALSE; else /*w是是v的其它未被訪問的鄰接頂點，作為上一鄰接頂點的右兄弟的其它未被訪問的鄰接頂點，作為上一鄰接頂點的右兄弟*/ q-next

46、sibling=p; q=p; DFSTree(G,w,&q); /*從第從第w個頂點出發(fā)深度優(yōu)先遍歷圖個頂點出發(fā)深度優(yōu)先遍歷圖G，建立生成子樹，建立生成子樹*q*/ 7.4 7.4 圖的連通性圖的連通性7.4.3 最小生成樹最小生成樹n個城市之間個城市之間,最多可能設(shè)置最多可能設(shè)置n(n-1)/2條線路條線路,而連通而連通n個城市只需個城市只需要要n-1條線路條線路. 最小最小(代價代價)生成樹的定義生成樹的定義. 一棵生成樹的代價一棵生成樹的代價.7.4 7.4 圖的連通性圖的連通性最小生成樹最小生成樹MST的性質(zhì)的性質(zhì): 假設(shè)假設(shè)N=(V,E)是一個連通網(wǎng)是一個連通網(wǎng),U是頂點集是頂點集

47、V的一個非空子集的一個非空子集.若若(u,v)是一條具有最小權(quán)是一條具有最小權(quán)值值(代價代價)的邊的邊,其中其中u屬于屬于U,v屬于屬于V-U,則必存則必存在一棵包含邊在一棵包含邊(u,v)的最小生成樹的最小生成樹.7.4 7.4 圖的連通性圖的連通性算法一：（普里姆算法）算法一：（普里姆算法） 假設(shè)假設(shè)N=(V,E)是連通網(wǎng)是連通網(wǎng),TE是是N上最小生成樹上最小生成樹中邊的集合中邊的集合.算法從算法從U=u0(u0屬于屬于V),TE=開始開始,重復(fù)執(zhí)行下述操作重復(fù)執(zhí)行下述操作: 在所有在所有u屬于屬于U,v屬于屬于V-U的邊的邊(u,v)屬于屬于E中找中找一條代價最小的邊一條代價最小的邊(u

48、0,v0)并入集合并入集合TE,同時同時v0并入并入U,直至直至U=V為止為止. 此時此時TE中必有中必有n-1條邊條邊,則則T=(V,TE)為為N的最的最小生成樹小生成樹. 為實現(xiàn)這個算法需要附設(shè)一個輔助數(shù)組為實現(xiàn)這個算法需要附設(shè)一個輔助數(shù)組closedge,以記錄從以記錄從U到到V-U具有最小代價的邊具有最小代價的邊. 對每個頂點對每個頂點vi屬于屬于V-U,在輔助數(shù)組中存在一個在輔助數(shù)組中存在一個相應(yīng)分量相應(yīng)分量closedgei-1,它包括兩個域它包括兩個域, 其中其中l(wèi)owcost存儲該邊上的權(quán)存儲該邊上的權(quán).顯然顯然:closedgei-1.lowcost=Mincost(u,vi

49、)|u屬于屬于U vex域存儲該邊依附的在域存儲該邊依附的在U中的頂點中的頂點.7.4 7.4 圖的連通性圖的連通性普里姆算法構(gòu)造最小生成樹的過程v2v4v6v3v1v5v1v4v6v5v2v3651534626(a)1425357.4 7.4 圖的連通性圖的連通性普里姆算法普里姆算法void MiniSpanTree_PRIM（MGraph G，VertexType u） /用普里姆算法從第用普里姆算法從第u個頂點出發(fā)構(gòu)造網(wǎng)個頂點出發(fā)構(gòu)造網(wǎng)G的最小生成樹的最小生成樹T， /輸出輸出T的各條邊。的各條邊。 /記錄從頂點集記錄從頂點集U到到V-U的代價最小的邊的輔助數(shù)組定義：的代價最小的邊的輔助

50、數(shù)組定義：struct VertexType adjvex； VRType lowcost； closedgeMAX_VERTEX_NUM;7.4 7.4 圖的連通性圖的連通性k=LocateVex（G，u）；）；for（j=0；jG.vexnum；+j） /輔助數(shù)組初始化輔助數(shù)組初始化 if（j！=k）closedgej=u，G.arcskj.adj； /adjvex，lowcostclosedgek.lowcost=0； / 初始，初始，U=ufor（i=1；i0，vi V-U printf（closedgek.adjvex，G.vexsk）；）； /輸出生成樹的邊輸出生成樹的邊 clos

51、edgek.lowcost=0； /第第k頂點并入頂點并入U集集 for（j=0；jG.vexnum；+j） if（G.arcskj.adjclosedgej.lowcost） /新頂點并入新頂點并入U后重新選擇最小邊后重新選擇最小邊 closedgej=G.vexsk，G.arcskj.adj； /MiniSpanTree7.4 7.4 圖的連通性圖的連通性算法二：（克魯斯卡爾算法）算法二：（克魯斯卡爾算法） 為使生成樹上邊的權(quán)值之和最小，顯然，其為使生成樹上邊的權(quán)值之和最小，顯然，其中每一條邊的權(quán)值應(yīng)該盡可能地小?？唆斔箍栔忻恳粭l邊的權(quán)值應(yīng)該盡可能地小?？唆斔箍査惴ǖ淖龇ň褪牵合葮?gòu)造一

52、個只含算法的做法就是：先構(gòu)造一個只含n個頂點的子個頂點的子圖圖SG，然后從權(quán)值最小的邊開始，若它的添加不，然后從權(quán)值最小的邊開始，若它的添加不使使SG中產(chǎn)生回路，則在中產(chǎn)生回路，則在SG上加上這條邊，如此上加上這條邊，如此重復(fù)，直至加上重復(fù)，直至加上n-1條邊為止。條邊為止。7.4 7.4 圖的連通性圖的連通性克魯斯卡爾算法構(gòu)造最小生成樹的過程v2v4v6v3v1v5v1v4v6v5v2v3651534626(a)1425357.4 7.4 圖的連通性圖的連通性一般來講，一般來講， 由于由于普里姆算法的時間復(fù)雜度為普里姆算法的時間復(fù)雜度為O(n2)，則適于稠密圖；而克魯斯卡爾算法需對則適于稠密

53、圖；而克魯斯卡爾算法需對e條邊條邊按權(quán)值進行排序，其時間復(fù)雜度為按權(quán)值進行排序，其時間復(fù)雜度為O(eloge)，則適于稀疏圖。則適于稀疏圖。7.4 7.4 圖的連通性圖的連通性7.4 7.4 圖的連通性圖的連通性 “最小生成樹最小生成樹”主要是針對主要是針對“無向圖無向圖”而言的，請思考它主而言的，請思考它主要能解決哪些實際生活中遇到的要能解決哪些實際生活中遇到的問題？問題？第 61 頁7.6 7.6 最短路徑最短路徑7.6.1 7.6.1 從某個源點到其余各頂點的最短路徑從某個源點到其余各頂點的最短路徑問題提出用帶權(quán)的有向圖表示一個交通運輸網(wǎng)，圖中：用帶權(quán)的有向圖表示一個交通運輸網(wǎng)，圖中：頂

54、點頂點表示城市表示城市邊邊表示城市間的交通聯(lián)系表示城市間的交通聯(lián)系權(quán)權(quán)表示此線路的長度或沿此線路運輸所花的時間或費表示此線路的長度或沿此線路運輸所花的時間或費用等用等問題：從某頂點出發(fā)，沿圖的邊到達另一頂點所經(jīng)過的路問題：從某頂點出發(fā)，沿圖的邊到達另一頂點所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑徑中，各邊上權(quán)值之和最小的一條路徑最短路徑最短路徑 第 62 頁7.6 7.6 最短路徑最短路徑7.6.1 7.6.1 從某個源點到其余各頂點的最短路徑從某個源點到其余各頂點的最短路徑l給定帶權(quán)有向圖給定帶權(quán)有向圖G G和源點和源點v,v,求從求從v v到到G G中其余各頂點的中其余各頂點的最短路徑

55、最短路徑l例例: :求求v v0 0到其余頂點的最短路徑到其余頂點的最短路徑V1V5V2V4V0V35501001060201030始點 終點 最短路徑 路徑長度 v0 v1 無 v2 (v0,v2) 10 v3 (v0,v4,v3) 50 v4 (v0,v4) 30 v5 (v0,v4,v3,v5) 60第 63 頁迪杰斯特拉迪杰斯特拉( (DijkstraDijkstra) )算法算法l (1)(1)設(shè)置兩個頂點的集合設(shè)置兩個頂點的集合T T和和S;S;集合集合S S存放已找到最短路徑的頂點存放已找到最短路徑的頂點集合集合T T存放當前還未找到最短路徑的頂點存放當前還未找到最短路徑的頂點l

56、 (2)(2)初始狀態(tài)時初始狀態(tài)時,S,S只包含源點只包含源點v v0 0 ; ;l (3)(3)從從T T中選取某個頂點中選取某個頂點v vi i( (要求要求v vi i 到到v v0 0的的路徑長度最短路徑長度最短) ) 加入到加入到S S中中,;,;l (4)S(4)S中每加入一個頂點中每加入一個頂點v vi i, ,都要修改頂點都要修改頂點v v0 0到到T T中剩余頂點中剩余頂點的的最短最短路徑長度值路徑長度值; ;它們的值為原來值與新值的較小者它們的值為原來值與新值的較小者; ;新值是新值是v vi i的的最短路徑長度值加上最短路徑長度值加上v vi i到該頂點的路徑長到該頂點的

57、路徑長度度l (5)(5)不斷重復(fù)不斷重復(fù)(3)(3)和和(4),(4),直到直到S S包含全部頂點包含全部頂點; ;第 64 頁V1V5V2V4V0V35501001060201030迪杰斯特拉(Dijkstra)算法舉例帶權(quán)鄰接矩陣為: 10 30 100 5 50 10 20 60 第 65 頁最短路徑的求解過程最短路徑的求解過程 終點 v1 v2 v3 v4 v5 vi步驟1 10 30 100 v2 (v0,v2) (v0,v4) (v0,v5)步驟2 60 30 100 v4 (v0,v2,v3) (v0,v4) (v0,v5)步驟3 50 90 v3 (v0,v4,v3) (v0

58、,v4,v5)步驟4 60 v5 (v0,v4,v3,v5)步驟5 無第 66 頁7.6 7.6 最短路徑最短路徑7.6.2 7.6.2 每一對頂點間的最短路徑每一對頂點間的最短路徑l給定帶權(quán)有向圖給定帶權(quán)有向圖G,G,求求G G中每個頂點到其余各頂點的最中每個頂點到其余各頂點的最短路徑短路徑l例例: :求有向網(wǎng)求有向網(wǎng)G G的每一對頂點的最短路徑的每一對頂點的最短路徑V0V2V1624113有向網(wǎng)G0 4 116 0 23 0鄰接矩陣第 67 頁FloydFloyd算法算法l(1)(1)遞推產(chǎn)生一個矩陣序列遞推產(chǎn)生一個矩陣序列A A0 0,A,A1 1,.,.,A Ak k,.A,.An n

59、 其中其中A Ak ki,ji,j 表示從頂點表示從頂點v vi i到到v vj j的路徑上所經(jīng)過的的路徑上所經(jīng)過的頂點序號不大于頂點序號不大于k k的最短路徑長度的最短路徑長度l(2)(2)初始時初始時, A, A0 0為為鄰接矩陣鄰接矩陣. .l(3)A(3)Ak+1k+1i,j=i,j=minAminAk ki,ji,j, A, Ak ki,k+1+Ai,k+1+Ak kk+1,jk+1,j (0=k=n-1) (0=k=n-1)0 4 116 0 23 0A0=0 4 65 0 23 7 0A2=0 4 66 0 23 0A1=第 68 頁例ACB2643110 4 116 0 23 0初始：路徑：AB