圖的定義和術(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í)要點(diǎn)學(xué)習(xí)要點(diǎn)1熟悉圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法，了解實(shí)際問題的求熟悉圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法，了解實(shí)際問題的求解效率與采用何種存儲結(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是頂點(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) )：用表示頂點(diǎn)

4、用表示頂點(diǎn)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起點(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 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語圖的應(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 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語三 圖的基本操作1 CreateGraph(&G, V, VR);1 CreateGraph(&G, V, VR);初始條件：初始條件：V V是圖的頂點(diǎn)

7、集，是圖的頂點(diǎn)集，VRVR是圖中弧的集合是圖中弧的集合操作結(jié)果：按操作結(jié)果：按V V和和VRVR的定義構(gòu)造圖的定義構(gòu)造圖G G2 DestroyGraph(&G);2 DestroyGraph(&G);初始條件：圖初始條件：圖G G存在存在操作結(jié)果：銷毀圖操作結(jié)果：銷毀圖G G3 LocateVex(G,u);3 LocateVex(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 GetVex(G,

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

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

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

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

12、：圖初始條件：圖G G存在，存在，v v是是G G中某個頂點(diǎn)，中某個頂點(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，對每個頂點(diǎn)調(diào)用函數(shù)對每個頂點(diǎn)調(diào)用函數(shù)VisitVisit一次一次且僅一次。一旦且僅一次。一旦visit( )visit( )失敗，則操作失敗失敗，則操作失敗13 BFSTraverse(G, v, Visit( );13 BFSTraverse(G, v, Visit( );初始條件：圖初始條件：圖G G存在，存在，v v是是G G中某個頂點(diǎn)，中某個頂點(diǎn)，VisitVisit是頂點(diǎn)的應(yīng)用函

13、數(shù)。是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：從頂點(diǎn)操作結(jié)果：從頂點(diǎn)v v起廣度優(yōu)先遍歷圖起廣度優(yōu)先遍歷圖G G，對每個頂點(diǎn)調(diào)用函數(shù)對每個頂點(diǎn)調(diào)用函數(shù)VisitVisit一次一次且一次。一旦且一次。一旦visit( )visit( )失敗，則操作失敗失敗，則操作失敗第 11 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語圖的基本術(shù)語圖的基本術(shù)語1 1 鄰接點(diǎn)及關(guān)聯(lián)邊鄰接點(diǎn)及關(guān)聯(lián)邊 鄰接點(diǎn)：鄰接點(diǎn)：邊的兩個頂點(diǎn)邊的兩個頂點(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,u)v,u)2 2 頂點(diǎn)的度、

14、入度、出度頂點(diǎn)的度、入度、出度 頂點(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 （每條邊對圖的所有頂點(diǎn)的度數(shù)和（每條邊對圖的所有頂點(diǎn)的度數(shù)和“貢獻(xiàn)貢獻(xiàn)”2”2度）度） e1e1 V1V1 V2V2 V

15、3V3 V4V4 V5V5 V1 V1 V2V2 V4V4 V3V3第 12 頁3 有向完全圖、有向完全圖、無向完全圖無向完全圖有向完全圖有向完全圖n個頂點(diǎn)的有向圖最大邊數(shù)是個頂點(diǎn)的有向圖最大邊數(shù)是n(n-1)無向完全圖無向完全圖n個頂點(diǎn)的無向圖最大邊數(shù)是個頂點(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ù)語定義和術(shù)語第 13 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語 路徑、回路路徑、回路 無向圖中的頂點(diǎn)序列無向圖中的頂點(diǎn)序列v1,v2, ,vk,v1,v2, ,vk,若若( (vi,vi

16、+1)vi,vi+1) E( i=1,2,k-1), E( i=1,2,k-1), v =v1, u =vk,v =v1, u =vk, 則稱該序列是從頂點(diǎn)則稱該序列是從頂點(diǎn)v v到頂點(diǎn)到頂點(diǎn)u u的的路徑路徑；若；若v=uv=u，則稱則稱該序列為該序列為回路回路； 有向圖有向圖D=(V，E）中的頂點(diǎn)序列中的頂點(diǎn)序列v1,v2, ,vk, v1,v2, ,vk, 若若 vi,vi+1 E E ( i=1,2,k-1), v =v1, u =vk, ( i=1,2,k-1), v =v1, u =vk, 則稱該序列是從頂點(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 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語連通圖、（強(qiáng)連通圖）連通圖、（強(qiáng)連通圖） 在

18、無（有）向圖在無（有）向圖G=G=中，若對任何兩個頂點(diǎn)中，若對任何兩個頂點(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 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語子圖子圖 設(shè)有兩個圖設(shè)有兩個圖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、圖、圖3 是是 圖圖

19、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ù)語連通分圖（強(qiáng)連通分量） 無向圖無向圖G的極大連通子圖稱為的極大連通子圖稱為G的連通分量的連通分量 極大連通子圖意思是：該子圖是極大連通子圖意思是：該子圖是G連通子圖，將連通子圖，將G的任何不在該子圖的任何不在該子圖中的頂點(diǎn)加入，子圖不再連通；中的頂點(diǎn)加入，子圖不再連通； 有向圖有向圖D的極大強(qiáng)連通子圖稱為的極大強(qiáng)連通子圖稱為D的強(qiáng)連通分量的強(qiáng)連通分量

20、 極大強(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 頁7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語 V5V5 V1 V1 V2V2 V4V4 V3V3 V5V5 V1 V1 V2V2 V4V4 V3V38 生成樹（ 包含無向圖包含無向圖G所有頂點(diǎn)的的極小連通子圖稱為所有頂點(diǎn)的的極小連通子圖稱為G生成樹生成樹 極小連通子圖意思是：該子圖是極小連通子圖意思是：該子圖是G的連

21、通子圖，在該子圖中刪除任的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通，何一條邊，子圖不再連通， 若若T是是G的生成樹當(dāng)且僅當(dāng)?shù)纳蓸洚?dāng)且僅當(dāng)T滿足如下條件滿足如下條件 T是是G的連通子圖的連通子圖 T包含包含G的所有頂點(diǎn)的所有頂點(diǎn) T中無回路中無回路 只有足以構(gòu)成一棵樹的只有足以構(gòu)成一棵樹的n-1條邊條邊第 18 頁例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第 19 頁例157

22、324G26例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強(qiáng)連通圖強(qiáng)連通圖356例非連通圖連通分量非連通圖連通分量例245136第 21 頁第七第七 章章 圖圖 7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)數(shù)組表示法1鄰接表第 22 頁7.2 7.2 圖

23、的存儲結(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)頂點(diǎn)的數(shù)據(jù)頂點(diǎn)的數(shù)據(jù) 2) 2)頂點(diǎn)間的關(guān)系頂點(diǎn)間的關(guān)系頂點(diǎn)的編號頂點(diǎn)的編號 為了使圖的存儲結(jié)構(gòu)與圖一一對應(yīng)，在討論圖的存儲結(jié)構(gòu)時，首先為了使圖的存儲結(jié)構(gòu)與圖一一對應(yīng)，在討論圖的存儲結(jié)構(gòu)時，首先要給圖的所有頂點(diǎn)編號。要給圖的所有頂點(diǎn)編號。 本課程介紹兩類圖的存儲結(jié)構(gòu)本課程介紹兩類圖的存儲結(jié)構(gòu)數(shù)組表示法數(shù)組表示法鄰接表（

24、鄰接表，逆鄰接表）鄰接表（鄰接表，逆鄰接表） 設(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)為它的編號 如何表示頂點(diǎn)間的關(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ù)組表示法中，用鄰接矩陣表示頂點(diǎn)間的關(guān)系在數(shù)組表示法中，用鄰接矩陣表示頂點(diǎn)間的關(guān)系A(chǔ)ij=Aij=1 1 若若( (vi,vi+1)vi,v

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

26、45 5m-1V1V1V2V2V3V3V4V4V5V5存儲頂點(diǎn)的一維數(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, AdjMatrixMAX_VE

27、RTEX_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個頂點(diǎn)，e條邊G的圖示如下：G.vexs G.arcs G.vexnumG.arcnu G.kind V1V10 0n ne eAGAG頂點(diǎn)數(shù)組存儲鄰接矩陣的二維數(shù)組第 27 頁7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)無向圖數(shù)組表示法特點(diǎn)

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

29、儲 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 頁7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(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)的在數(shù)組中的位置struct Arc

30、Node *nextarc; /指向下一條邊（弧）結(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)前頂點(diǎn)數(shù)和弧數(shù)int kind;

31、/圖的種類標(biāo)志圖的種類標(biāo)志ALGraph;第 30 頁7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)設(shè)G是ALGraph 類型的變量，用于存儲無向圖G1，該圖有n個頂點(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 firstarcadjvex nextarc第

32、 31 頁7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)無向圖的鄰接表的特點(diǎn) 1）在G鄰接表中，同一條邊對應(yīng)兩個結(jié)點(diǎn)； 2）頂點(diǎn)v的度：等于v對應(yīng)線性鏈表的長度； 3）判定兩頂點(diǎn)v ，u是否鄰接：要看v對應(yīng)線性鏈表中有無對應(yīng)的結(jié)點(diǎn) 4）在G中增減邊：要在兩個單鏈表插入、刪除結(jié)點(diǎn)； 第 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）有向圖的鄰接表頂點(diǎn)：用一維數(shù)組存儲（

33、按編號順序）以同一頂點(diǎn)為起點(diǎn)的弧：用線性鏈表存儲類似于無向圖的鄰接表，所不同的是：以同一頂點(diǎn)為起點(diǎn)的弧：用線性鏈表存儲第 33 頁7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)2）有向圖的逆鄰接表頂點(diǎn)：用一維數(shù)組存儲（按編號順序）以同一頂點(diǎn)為終點(diǎn)的?。河镁€性鏈表存儲表類似于無向圖的鄰接表，所不同的是：以同一頂點(diǎn)為終點(diǎn)的弧：用線性鏈表存儲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 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu) 在不同的存儲

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

35、一一 深度優(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ù)對圖進(jìn)行深度優(yōu)先遍歷；的未被訪問的鄰接點(diǎn)出發(fā)，繼續(xù)對圖進(jìn)行深度優(yōu)先遍歷；例例 圖圖G G中，以中，以V1V1起點(diǎn)的的深度優(yōu)先序列：起點(diǎn)的的深度優(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 V4V4 V3V3 V2V2 V1

36、V1由于沒為有規(guī)定由于沒為有規(guī)定訪問鄰接點(diǎn)的順序，訪問鄰接點(diǎn)的順序，深度優(yōu)先序列不是唯一的深度優(yōu)先序列不是唯一的這是序列（1）在遍歷過程中所經(jīng)過的路徑注：為簡單起見，只討論非空連通圖的遍歷第 38 頁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ù)對圖進(jìn)行深度優(yōu)先遍歷；繼續(xù)對圖進(jìn)行深度優(yōu)先遍歷； 先序遍歷（先序遍歷（D DL LR R） 若二叉樹非空若二叉樹非空 （1 1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （2 2）

37、先序遍歷左子樹；）先序遍歷左子樹； （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 頁7.3 7.3 圖的遍歷圖的遍歷深度優(yōu)先遍歷算法深度優(yōu)先遍歷算法void DFS(Graph G, int v, Status(*Visit(int v) / 從第從第v個頂點(diǎn)出發(fā)，遞歸地深度優(yōu)先遍歷圖個頂點(diǎn)出發(fā)，遞歸地深度優(yōu)先遍歷圖G。 / v是頂點(diǎn)在一維數(shù)組中的

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

39、se(0)/visitedv=TRUE/visitedv=TRUE表示頂點(diǎn)表示頂點(diǎn)v v已被訪問已被訪問visited01234m-100000第 40 頁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, Visit); PreOrde

40、rTraverse(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個頂點(diǎn)出發(fā)，遞歸地深度優(yōu)先遍歷圖個頂點(diǎn)出發(fā)，遞歸地深度優(yōu)先遍歷圖G。 / v是頂點(diǎn)在一維數(shù)組中的位置，是頂點(diǎn)在一維數(shù)組中的位置，假設(shè)假設(shè)G G是非空圖是非空圖visitedv =TRUE; Visit(v); /訪問第訪問第v個頂點(diǎn)個頂點(diǎn)for (w= FirstAdjVex(

41、G, v); w; w=NextAdjVex(G, v, w)if (!visitedw) DFS(G, w); /對對v的尚未訪問的鄰接頂點(diǎn)的尚未訪問的鄰接頂點(diǎn)w遞歸調(diào)用遞歸調(diào)用DFS第 41 頁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)的所有未被訪問的鄰接點(diǎn)w w1 1 ,w ,w2 2 , , wwk k ；3 3）依次依次從這些鄰接點(diǎn)出發(fā)，訪問它們的所有未被訪問的鄰接點(diǎn)從這些鄰接點(diǎn)出發(fā)，訪問它們的所有未被

42、訪問的鄰接點(diǎn); ; 依依此類推，直到圖中所有訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問；此類推，直到圖中所有訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問；例例 圖圖G G中，以中，以V1V1起點(diǎn)的的廣度優(yōu)先序列：起點(diǎn)的的廣度優(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)過的路徑由于沒為有規(guī)定由于沒為有規(guī)定

43、訪問鄰接點(diǎn)的順序，訪問鄰接點(diǎn)的順序，廣度優(yōu)先序列不是唯一的廣度優(yōu)先序列不是唯一的第 42 頁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 , , wwk k ； （容易實(shí)現(xiàn)）容易實(shí)現(xiàn)）3 3）依次從依次從這些鄰接點(diǎn)這些鄰接點(diǎn)（在步驟（在步驟 2 2）訪問的頂點(diǎn)）出發(fā)，訪問它們的所有）訪問的頂點(diǎn)）出發(fā)，訪問它們的所有未被訪問的鄰接點(diǎn)未被訪問的鄰接點(diǎn); ; 依此類推，直到圖中所有

44、訪問過的頂點(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 頁7.3 7.3 圖的遍歷圖的遍歷void BFSTraverse(Graph G,int v,Status (void BFS

45、Traverse(Graph G,int v,Status (* * Visit)(int v) Visit)(int 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 G.vexnum; +u) visitedu=FALSE; for (u=0; ulchild=p; first=FALSE; else /*w是是v的其它未被訪問的鄰接頂點(diǎn)，作為上一鄰接頂點(diǎn)的右兄弟的其它未被訪問的鄰接頂點(diǎn)，作為上一鄰

46、接頂點(diǎn)的右兄弟*/ q-nextsibling=p; q=p; DFSTree(G,w,&q); /*從第從第w個頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖個頂點(diǎn)出發(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)

47、是一個連通網(wǎng),U是頂點(diǎn)集是頂點(diǎn)集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中找中找一條

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

49、ost=Mincost(u,vi)|u屬于屬于U vex域存儲該邊依附的在域存儲該邊依附的在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個頂點(diǎn)出發(fā)構(gòu)造網(wǎng)個頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹的最小生成樹T， /輸出輸出T的各條邊。的各條邊。 /記錄從頂點(diǎn)集記錄從頂點(diǎn)集U到到V-U的代價最小的邊的輔

50、助數(shù)組定義：的代價最小的邊的輔助數(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）；）； /輸出生

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

52、魯斯卡爾算法的做法就是：先構(gòu)造一個只含算法的做法就是：先構(gòu)造一個只含n個頂點(diǎn)的子個頂點(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 圖的連通性圖的連通性一般來講，一般來講， 由于由于普里姆算法的時間復(fù)雜度為普里姆算法的時間復(fù)雜度為O(n2)，則適于稠密圖

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

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

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

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

57、點(diǎn)的路徑長到該頂點(diǎn)的路徑長度度l(5)(5)不斷重復(fù)不斷重復(fù)(3)(3)和和(4),(4),直到直到S S包含全部頂點(diǎn)包含全部頂點(diǎn); ;第 64 頁V1V5V2V4V0V35501001060201030迪杰斯特拉(Dijkstra)算法舉例帶權(quán)鄰接矩陣為: 10 30 100 5 50 10 20 60 第 65 頁最短路徑的求解過程最短路徑的求解過程 終點(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,v

58、4,v3) (v0,v4,v5)步驟4 60 v5 (v0,v4,v3,v5)步驟5 無第 66 頁7.6 7.6 最短路徑最短路徑7.6.2 7.6.2 每一對頂點(diǎn)間的最短路徑每一對頂點(diǎn)間的最短路徑l給定帶權(quán)有向圖給定帶權(quán)有向圖G,G,求求G G中每個頂點(diǎn)到其余各頂點(diǎn)的最中每個頂點(diǎn)到其余各頂點(diǎn)的最短路徑短路徑l例例: :求有向網(wǎng)求有向網(wǎng)G G的每一對頂點(diǎn)的最短路徑的每一對頂點(diǎn)的最短路徑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

59、,.A,.An n 其中其中A Ak ki,ji,j表示從頂點(diǎn)表示從頂點(diǎn)v vi i到到v vj j的路徑上所經(jīng)過的的路徑上所經(jīng)過的頂點(diǎn)序號不大于頂點(diǎn)序號不大于k k的最短路徑長度的最短路徑長度l(2)(2)初始時初始時, A, A0 0為鄰接矩陣為鄰接矩陣. .l(3)A(3)Ak+1k+1i,j=minAi,j=minAk ki,j, Ai,j, 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初始：路徑：