圖的定義和術(shù)語(yǔ)

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

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

3、集合構(gòu)成，記作G=G= 其中其中V V是頂點(diǎn)的非空有限集合，是頂點(diǎn)的非空有限集合，E E是邊的有限集合，其中邊是頂點(diǎn)的無序?qū)蛴行驅(qū)?。是邊的有限集合，其中邊是頂點(diǎn)的無序?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、點(diǎn)用表示頂點(diǎn)v vi i、v vj j的線段的線段，稱為無向邊；，稱為無向邊； V5V5 V1 V1 V2V2 V4V4 V3V3第 6 頁(yè)7.1 7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ)例例 G2=G2=V2=vV2=v1 1,v,v2 2, ,v v3 3, ,v v4 4 E2=vE2=, , , , , , G2圖示有序?qū)τ行驅(qū)?：用以表示以用以表示以v vi i起點(diǎn)、以起點(diǎn)、以v vj j為終點(diǎn)的有向線段，為終點(diǎn)的有向線段，稱為有向邊或?。环Q為有向邊或??；無向圖：無向圖：在圖在圖G G中，若中，若所有邊是無向邊，則稱所有邊是無向邊，則稱G G為無向圖；為無向圖；有有向圖：向圖：在圖在圖G

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

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

7、點(diǎn)集，是圖的頂點(diǎn)集，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中頂點(diǎn)有相同特征中頂點(diǎn)有相同特征操作結(jié)果：若操作結(jié)果：若G G中存在頂點(diǎn)中存在頂點(diǎn)u u，則返回該頂點(diǎn)在圖中位置；否則返回其它則返回該頂點(diǎn)在圖中位置；否則返回其它信息。信息。4 4 GetVex

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

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

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

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

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

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

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

15、4 V5V5 V1 V1 V2V2 V4V4 V3V3第 12 頁(yè)3 有向完全圖、有向完全圖、無向完全圖無向完全圖有向完全圖有向完全圖n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1)無向完全圖無向完全圖n個(gè)頂點(diǎn)的無向圖最大邊數(shù)是個(gè)頂點(diǎn)的無向圖最大邊數(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ù)語(yǔ)定義和術(shù)語(yǔ)第 13 頁(yè)7.1 7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ) 4 4路徑、回路路徑、回路 無向圖中的頂點(diǎn)序列無向圖中的頂點(diǎn)序列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, , 則稱該序列是從頂點(diǎn)則稱該序列是從頂點(diǎn)v v到頂點(diǎn)到頂點(diǎn)u u的的路徑路徑；若；若v=uv=u，則稱則稱該序列為該序列為回路回路； 有向圖有向圖D=(V，E）中的頂點(diǎn)序列中的頂點(diǎn)序列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, , 則稱該序列是從頂點(diǎn)則稱該序列是從頂點(diǎn)v v到頂點(diǎn)到頂點(diǎn)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 頁(yè)7.1 7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ)5 5連通圖、（強(qiáng)連通圖）連通圖、（強(qiáng)連通圖）

18、在無（有）向圖在無（有）向圖G=G= V, E 中，若對(duì)任何兩個(gè)頂點(diǎn)中，若對(duì)任何兩個(gè)頂點(diǎn)v v、u u都存在從都存在從v v到到u u的路徑，則稱的路徑，則稱G G是連通圖（強(qiáng)連通圖）是連通圖（強(qiáng)連通圖） V5V5 V6V6 V3V3 V1V1 V2V2 V4V4連通圖連通圖非連通圖非連通圖 V5V5 V1 V1 V2V2 V4V4 V3V3第 15 頁(yè)7.1 7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ)6子圖子圖 設(shè)有兩個(gè)圖設(shè)有兩個(gè)圖G=（V，E）、）、G1=（V1，E1），），若若V1 V，E1 E，E1關(guān)聯(lián)的頂點(diǎn)都在關(guān)聯(lián)的頂點(diǎ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 頁(yè)7.1 7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ)7連通分圖（強(qiáng)連通分量） 無向圖無向圖G的極大連通子圖稱為的極大連通子圖稱為G的連通分量的連通分量 極大連通子圖意思是：該子圖是極大連通子圖意思是：該子圖是G連通子圖，將連通子圖，將G的任何不在該子圖的任何不在該子圖中的頂點(diǎn)加入，子圖不再連通；中的頂點(diǎn)加入，子圖不再連通； 有向圖有向圖D的極大強(qiáng)連通子圖稱為的極大強(qiáng)連通子圖稱為D的強(qiáng)連

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

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

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

23、頁(yè)7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu) 圖是多對(duì)多的結(jié)構(gòu)，比線性結(jié)構(gòu)、樹結(jié)構(gòu)復(fù)雜，所以其存儲(chǔ)結(jié)構(gòu)也圖是多對(duì)多的結(jié)構(gòu)，比線性結(jié)構(gòu)、樹結(jié)構(gòu)復(fù)雜，所以其存儲(chǔ)結(jié)構(gòu)也要復(fù)雜些。與線性結(jié)構(gòu)、樹結(jié)構(gòu)一樣，圖的存儲(chǔ)結(jié)構(gòu)至少要保存兩類信要復(fù)雜些。與線性結(jié)構(gòu)、樹結(jié)構(gòu)一樣，圖的存儲(chǔ)結(jié)構(gòu)至少要保存兩類信息：息：1)1)頂點(diǎn)的數(shù)據(jù)頂點(diǎn)的數(shù)據(jù) 2) 2)頂點(diǎn)間的關(guān)系頂點(diǎn)間的關(guān)系頂點(diǎn)的編號(hào)頂點(diǎn)的編號(hào) 為了使圖的存儲(chǔ)結(jié)構(gòu)與圖一一對(duì)應(yīng)，在討論圖的存儲(chǔ)結(jié)構(gòu)時(shí)，首先為了使圖的存儲(chǔ)結(jié)構(gòu)與圖一一對(duì)應(yīng)，在討論圖的存儲(chǔ)結(jié)構(gòu)時(shí)，首先要給圖的所有頂點(diǎn)編號(hào)。要給圖的所有頂點(diǎn)編號(hào)。 本課程介紹兩類圖的存儲(chǔ)結(jié)構(gòu)本課程介紹兩類圖的存儲(chǔ)結(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è)頂點(diǎn)的設(shè)頂點(diǎn)的的的角標(biāo)為它的編號(hào) 如何表示頂點(diǎn)間的關(guān)系？第 23 頁(yè)7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu) 鄰接矩陣鄰接矩陣：G G的鄰接矩陣是滿足如下條件的的鄰接矩陣是滿足如下條件的n n階階矩陣：矩陣： 一一 數(shù)組表示法數(shù)組表示法數(shù)組表示法是圖的一種順序存儲(chǔ)結(jié)構(gòu)數(shù)組表示法是圖的一種順序存儲(chǔ)結(jié)構(gòu)在數(shù)組表示法中，用鄰接矩陣表示頂點(diǎn)間的關(guān)系在數(shù)組表示法中，用鄰接矩陣表示頂點(diǎn)間的關(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 頁(yè)7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)數(shù)組表示法頂點(diǎn)的存儲(chǔ)：用一維數(shù)組存儲(chǔ)（按編號(hào)順序）頂點(diǎn)間關(guān)系：用二維數(shù)組存儲(chǔ)圖的鄰接矩

26、陣；0 01 12 23 34 45 5m-1V1V1V2V2V3V3V4V4V5V5存儲(chǔ)頂點(diǎn)的一維數(shù)組存儲(chǔ)鄰接矩陣的二維數(shù)組0 01 10 01 10 01 10 01 10 01 10 01 12 23 34 4mm+1m+2m+3m+4第 25 頁(yè)7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(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 頁(yè)7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)設(shè)G是Mgraph 類型的變量，用于存儲(chǔ)無向圖，該圖有n個(gè)頂點(diǎn)，e條邊G的圖示如下：G.vexs G.arcs G.vexnumG.arcnu G.kind V1V10 0n ne eAGAG頂點(diǎn)數(shù)組存儲(chǔ)鄰接矩陣的二維數(shù)組第 27 頁(yè)7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)

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

29、中；關(guān)聯(lián)同一頂點(diǎn)的邊：用線性鏈表存儲(chǔ) 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é)點(diǎn)表示邊（V1 V2）,其中的1是V2在一維數(shù)組中的位置第 29 頁(yè)7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表類型定義#define MAX_VERTEX_NUM 20typedef struct ArcNode /邊（?。┙Y(jié)點(diǎn)的類型定義邊（弧）結(jié)點(diǎn)的類型定義int adjvex; /邊（?。┑牧硪豁旤c(diǎn)的在數(shù)組中的位置邊（?。┑牧硪豁旤c(diǎn)的

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

31、前頂點(diǎn)數(shù)和弧數(shù)int kind; /圖的種類標(biāo)志圖的種類標(biāo)志ALGraph;第 30 頁(yè)7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)設(shè)G是ALGraph 類型的變量，用于存儲(chǔ)無向圖G1，該圖有n個(gè)頂點(diǎn)，e條邊G的圖示如下： V5V5 V1 V1 V2V2 V4V4 V3V3無向圖G1該結(jié)點(diǎn)表示邊（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 頁(yè)7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)無向圖的鄰接表的特點(diǎn) 1）在G鄰接表中，同一條邊對(duì)應(yīng)兩個(gè)結(jié)點(diǎn)； 2）頂點(diǎn)v的度：等于v對(duì)應(yīng)線性鏈表的長(zhǎng)度； 3）判定兩頂點(diǎn)v ，u是否鄰接：要看v對(duì)應(yīng)線性鏈表中有無對(duì)應(yīng)的結(jié)點(diǎn) 4）在G中增減邊：要在兩個(gè)單鏈表插入、刪除結(jié)點(diǎn)； 第 32 頁(yè)7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(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、向圖的鄰接表頂點(diǎn)：用一維數(shù)組存儲(chǔ)（按編號(hào)順序）以同一頂點(diǎn)為起點(diǎn)的?。河镁€性鏈表存儲(chǔ)類似于無向圖的鄰接表，所不同的是：以同一頂點(diǎn)為起點(diǎn)的?。河镁€性鏈表存儲(chǔ)第 33 頁(yè)7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)2）有向圖的逆鄰接表頂點(diǎn)：用一維數(shù)組存儲(chǔ)（按編號(hào)順序）以同一頂點(diǎn)為終點(diǎn)的?。河镁€性鏈表存儲(chǔ)表類似于無向圖的鄰接表，所不同的是：以同一頂點(diǎn)為終點(diǎn)的弧：用線性鏈表存儲(chǔ)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 頁(yè)7.2 7.2 圖的

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

35、頁(yè)7.3 7.3 圖的遍歷圖的遍歷一一 深度優(yōu)先遍歷深度優(yōu)先遍歷從圖中某頂點(diǎn)從圖中某頂點(diǎn)v v出發(fā)：出發(fā)： 1 1）訪問頂點(diǎn)）訪問頂點(diǎn)v v；2 2）從從v v的未被訪問的鄰接點(diǎn)出發(fā)，繼續(xù)對(duì)圖進(jìn)行深度優(yōu)先遍歷；的未被訪問的鄰接點(diǎn)出發(fā)，繼續(xù)對(duì)圖進(jìn)行深度優(yōu)先遍歷；例例 圖圖G G中，以中，以V1V1起點(diǎn)的起點(diǎn)的的的深度優(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ī)定訪問鄰接點(diǎn)的順序，訪問鄰接點(diǎn)的順序，深度優(yōu)先序列不是唯一的深度優(yōu)先序列不是唯一的這是序列（1）在遍歷過程中所經(jīng)過的路徑注：為簡(jiǎn)單起見，只討論非空連通圖的遍歷第 38 頁(yè)7.3 7.3 圖的遍歷圖的遍歷深度優(yōu)先遍歷( (設(shè)圖為非空連通圖）設(shè)圖為非空連通圖）從圖中某頂點(diǎn)從圖中某頂點(diǎn)v v出發(fā)：出發(fā)： 1 1）訪問頂點(diǎn)）訪問頂點(diǎn)v v；2 2）從從v v的未被訪問的鄰接點(diǎn)出發(fā)，的未被訪問的鄰接點(diǎn)出發(fā)，繼續(xù)對(duì)圖進(jìn)行深度優(yōu)先遍歷；繼續(xù)對(duì)圖進(jìn)行深度優(yōu)先遍歷； 先序遍歷（先序遍歷（D DL LR R） 若二叉樹非空若二叉樹非空 （1 1）訪問

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

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

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

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

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

42、從這些鄰接點(diǎn)出發(fā)，訪問它們的所有未被訪問的鄰接點(diǎn); ; 依此類依此類推，直到圖中所有訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問；推，直到圖中所有訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問；例例 圖圖G G中，以中，以V1V1起點(diǎn)的起點(diǎn)的的廣的廣度優(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ī)定訪問鄰接點(diǎn)的順序，訪問鄰接點(diǎn)的順序，廣度優(yōu)先序列不是唯一的廣度優(yōu)先序列不是唯一的第 42 頁(yè)7.3 7.3 圖的遍歷圖的遍歷廣義優(yōu)先遍歷算法廣義優(yōu)先遍歷算法從圖中某頂點(diǎn)從圖中某頂點(diǎn)v v出發(fā)：出發(fā)：1 1）訪問頂點(diǎn)訪問頂點(diǎn)v v ；（；（容易實(shí)現(xiàn)）容易實(shí)現(xiàn)）2 2）訪問訪問v v的所有未被訪問的鄰接點(diǎn)的所有未被訪問的鄰接點(diǎn)w w1 1 ,w ,w2 2 , , w wk k ； （容易實(shí)現(xiàn)）容易實(shí)現(xiàn)）3 3）依次從依次從這些鄰接點(diǎn)這些鄰接點(diǎn)（在步驟（在步驟 2 2）訪問的頂點(diǎn)）出發(fā)，訪問它們的所有）訪問的頂點(diǎn)）出發(fā)，訪問它們的所有未被訪問的鄰接點(diǎn)未被訪問的鄰

44、接點(diǎn); ; 依此類推，直到圖中所有訪問過的頂點(diǎn)的鄰接點(diǎn)都依此類推，直到圖中所有訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問；被訪問；為實(shí)現(xiàn)為實(shí)現(xiàn) 3 3），），需要保存在步驟需要保存在步驟(2(2）中訪問的頂點(diǎn)，而且）中訪問的頂點(diǎn)，而且訪問這些頂點(diǎn)訪問這些頂點(diǎn)鄰鄰接點(diǎn)接點(diǎn)的順序?yàn)椋合缺４娴捻旤c(diǎn)，其鄰接點(diǎn)先被訪問。的順序?yàn)椋合缺４娴捻旤c(diǎn)，其鄰接點(diǎn)先被訪問。在在廣度優(yōu)先遍歷算法中，需設(shè)置一隊(duì)列廣度優(yōu)先遍歷算法中，需設(shè)置一隊(duì)列Q Q，保存已訪問的頂點(diǎn)，并控制遍歷頂點(diǎn)的順序。保存已訪問的頂點(diǎn)，并控制遍歷頂點(diǎn)的順序。第 43 頁(yè)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是頂點(diǎn)在一維數(shù)組中的位置，是頂點(diǎn)在一維數(shù)組中的位置，使使用輔助隊(duì)列用輔助隊(duì)列Q Q和訪問標(biāo)志數(shù)組和訪問標(biāo)志數(shù)組visitedvisited。 for (u=0; u for (u=0; ulchild=p; first=FALSE; else /*w是是v的其它未被訪問的鄰接頂點(diǎn)，作為上一鄰接頂點(diǎn)的右兄弟的其它未被訪問的鄰接頂點(diǎn)，作為上一鄰接頂點(diǎn)的右兄弟*/ q-next

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

47、V的一個(gè)非空子集的一個(gè)非空子集.若若(u,v)是一條具有最小權(quán)是一條具有最小權(quán)值值(代價(jià)代價(jià))的邊的邊,其中其中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中找中找一條代價(jià)最小的邊一條代價(jià)最小的邊(u

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

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

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頂點(diǎn)并入頂點(diǎn)并入U(xiǎn)集集 for（j=0；jG.vexnum；+j） if（G.arcskj.adjclosedgej.lowcost） /新頂點(diǎn)并入新頂點(diǎn)并入U(xiǎn)后重新選擇最小邊后重新選擇最小邊 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è)只含算法的做法就是：先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子個(gè)頂點(diǎ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 圖的連通性圖的連通性一般來講，一般來講， 由于由于普里姆算法的時(shí)間復(fù)雜度為普里姆算法的時(shí)間復(fù)雜度為O(n2)，則適于稠密圖；而克魯斯卡爾算法需對(duì)則適于稠密

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

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

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

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

57、路徑長(zhǎng)度度l (5)(5)不斷重復(fù)不斷重復(fù)(3)(3)和和(4),(4),直到直到S S包含全部頂點(diǎn)包含全部頂點(diǎn); ;第 64 頁(yè)V1V5V2V4V0V35501001060201030迪杰斯特拉(Dijkstra)算法舉例帶權(quán)鄰接矩陣為: 10 30 100 5 50 10 20 60 第 65 頁(yè)最短路徑的求解過程最短路徑的求解過程 終點(diǎn) 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 頁(yè)7.6 7.6 最短路徑最短路徑7.6.2 7.6.2 每一對(duì)頂點(diǎn)間的最短路徑每一對(duì)頂點(diǎn)間的最短路徑l給定帶權(quán)有向圖給定帶權(quán)有向圖G,G,求求G G中每個(gè)頂點(diǎn)到其余各頂點(diǎn)的最中每個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑短路徑l例例: :求有向網(wǎng)求有向網(wǎng)G G的每一對(duì)頂點(diǎn)的最短路徑的每一對(duì)頂點(diǎn)的最短路徑V0V2V1624113有向網(wǎng)G0 4 116 0 23 0鄰接矩陣第 67 頁(yè)FloydFloyd算法算法l(1)(1)遞推產(chǎn)生一個(gè)矩陣序列遞推產(chǎn)生一個(gè)矩陣序列A A0 0,A,A1 1,.,.,A Ak k,.A,.An n

59、 其中其中A Ak ki,ji,j 表示從頂點(diǎn)表示從頂點(diǎn)v vi i到到v vj j的路徑上所經(jīng)過的的路徑上所經(jīng)過的頂點(diǎn)序號(hào)不大于頂點(diǎn)序號(hào)不大于k k的最短路徑長(zhǎng)度的最短路徑長(zhǎng)度l(2)(2)初始時(shí)初始時(shí), 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 頁(yè)例ACB2643110 4 116 0 23 0初始：路徑：AB