專業(yè)課數(shù)據(jù)結(jié)構(gòu)第7

1、機(jī)電工程學(xué)院機(jī)電工程學(xué)院程藝苑程藝苑數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)教學(xué)內(nèi)容教學(xué)內(nèi)容 緒論緒論第第1 1章章 線性表線性表第第2 2章章 棧和隊(duì)列棧和隊(duì)列第第3 3章章 串串第第4 4章章 數(shù)組和廣義表數(shù)組和廣義表第第5 5章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)第第6 6章章 圖圖第第7 7章章 查找查找第第8 8章章 排序排序第第9 9章章第第7 7章章 圖圖u圖圖(Graph)(Graph)是一種比線性表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。是一種比線性表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。u線性結(jié)構(gòu)：線性結(jié)構(gòu)：是研究數(shù)據(jù)元素之間的是研究數(shù)據(jù)元素之間的一對(duì)一關(guān)系一對(duì)一關(guān)系。在這種。在這種結(jié)構(gòu)中，除第一個(gè)和最后一個(gè)元素外，任何一個(gè)元素都有結(jié)構(gòu)中

2、，除第一個(gè)和最后一個(gè)元素外，任何一個(gè)元素都有唯一的一個(gè)直接前驅(qū)和直接后繼。唯一的一個(gè)直接前驅(qū)和直接后繼。u樹(shù)結(jié)構(gòu)：樹(shù)結(jié)構(gòu)：是研究數(shù)據(jù)元素之間的是研究數(shù)據(jù)元素之間的一對(duì)多的關(guān)系一對(duì)多的關(guān)系。在這種。在這種結(jié)構(gòu)中，每個(gè)元素對(duì)下結(jié)構(gòu)中，每個(gè)元素對(duì)下( (層層) )可以有可以有0 0個(gè)或多個(gè)元素相聯(lián)系，個(gè)或多個(gè)元素相聯(lián)系，對(duì)上對(duì)上( (層層) )只有唯一的一個(gè)元素相關(guān)，數(shù)據(jù)元素之間有明顯只有唯一的一個(gè)元素相關(guān)，數(shù)據(jù)元素之間有明顯的層次關(guān)系。的層次關(guān)系。u圖結(jié)構(gòu)：圖結(jié)構(gòu)：是研究數(shù)據(jù)元素之間的是研究數(shù)據(jù)元素之間的多對(duì)多的關(guān)系多對(duì)多的關(guān)系。在這種。在這種結(jié)構(gòu)中，任意兩個(gè)元素之間可能存在關(guān)系。即結(jié)點(diǎn)之間的結(jié)構(gòu)

3、中，任意兩個(gè)元素之間可能存在關(guān)系。即結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意元素之間都可能相關(guān)。關(guān)系可以是任意的，圖中任意元素之間都可能相關(guān)。u圖的應(yīng)用極為廣泛，已滲入到諸如語(yǔ)言學(xué)、邏輯學(xué)、物圖的應(yīng)用極為廣泛，已滲入到諸如語(yǔ)言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支。理、化學(xué)、電訊、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支。第第7 7章章 圖圖7 7.1 .1 圖的基本概念圖的基本概念7 7.2 .2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)7 7.3 .3 圖的遍歷圖的遍歷7.4 7.4 圖的連通性問(wèn)題圖的連通性問(wèn)題7.5 7.5 有向無(wú)環(huán)圖及其應(yīng)用有向無(wú)環(huán)圖及其應(yīng)用7.6 7.6 最短路徑最短路徑7.1

4、 7.1 圖的基本概念圖的基本概念7.1.1 7.1.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ)定義：定義：圖是由圖是由頂點(diǎn)集合頂點(diǎn)集合(vertex)(vertex)及及頂點(diǎn)間的關(guān)系頂點(diǎn)間的關(guān)系集合組成集合組成的一種數(shù)據(jù)結(jié)構(gòu)：的一種數(shù)據(jù)結(jié)構(gòu)： GraphGraph( V, E ) ( V, E ) 其中其中: : V= V=x|xx|x 某個(gè)數(shù)據(jù)對(duì)象某個(gè)數(shù)據(jù)對(duì)象 是頂點(diǎn)的非空有窮集合；是頂點(diǎn)的非空有窮集合； E1=(x, y)| E1=(x, y)|x,yx,y V V 或或 E2=E2=|x,yx,y VVuE1E1是頂點(diǎn)間關(guān)系的有窮集合，也叫做是頂點(diǎn)間關(guān)系的有窮集合，也叫做邊邊(edge)(edg

5、e)集合，此時(shí)的圖集合，此時(shí)的圖稱為稱為無(wú)向圖無(wú)向圖(Digraph)(Digraph)。uE2E2表示從表示從x x到到y(tǒng) y的一條的一條弧弧(Arc)(Arc), ,且稱且稱x x為弧尾為弧尾,y,y為弧頭，這樣的圖為弧頭，這樣的圖稱為稱為有向圖有向圖( (UndigraphUndigraph) )。例例1：設(shè)有有向圖：設(shè)有有向圖G1和無(wú)向圖和無(wú)向圖G2，形式化定義分別是：，形式化定義分別是：G1=(V1 ，E1)V1=a,b,c,d,eE1=, , ,G2=(V2 ，E2)V2=a,b,c,dE2=(a,b), (a,c), (a,d), (b,d), (b,c), (c,d)它們所對(duì)應(yīng)

6、的圖如下圖所示。它們所對(duì)應(yīng)的圖如下圖所示。abcd(b) (b) 無(wú)向圖無(wú)向圖G2 G2 (a) (a) 有向圖有向圖G1 G1 acbde我們用我們用n表示圖中頂點(diǎn)數(shù)目，用表示圖中頂點(diǎn)數(shù)目，用e表示邊或弧的數(shù)目。下面的討論中，表示邊或弧的數(shù)目。下面的討論中，不考慮頂點(diǎn)到其自身的弧或邊，即若不考慮頂點(diǎn)到其自身的弧或邊，即若 VR,則則 vi vj。u對(duì)于無(wú)向圖，對(duì)于無(wú)向圖，e的取值范圍是的取值范圍是0，n(n-1)/2 ，那么具有，那么具有n(n-1)/2條邊的條邊的無(wú)向圖稱為無(wú)向圖稱為完全無(wú)向圖完全無(wú)向圖，即圖中任意兩個(gè)不同的頂點(diǎn)間都有一條無(wú)向，即圖中任意兩個(gè)不同的頂點(diǎn)間都有一條無(wú)向邊。邊。

7、u對(duì)于有向圖，對(duì)于有向圖，e的取值范圍是的取值范圍是0，n(n-1) ，那么具有，那么具有n(n-1)條邊的有向條邊的有向圖稱為圖稱為完全有向圖完全有向圖，即圖中任意兩個(gè)不同的頂點(diǎn)間都有兩條弧。，即圖中任意兩個(gè)不同的頂點(diǎn)間都有兩條弧。u 有很少邊或弧的圖有很少邊或弧的圖(enn)的圖稱為的圖稱為稀疏圖稀疏圖(Sparse graph)，反之稱，反之稱為為稠密圖稠密圖(Dense graph)。u有時(shí)圖的邊或弧具有與它相關(guān)的數(shù)，這種與圖的邊或弧相關(guān)的數(shù)叫做有時(shí)圖的邊或弧具有與它相關(guān)的數(shù)，這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)權(quán)(Weight)。這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。這些權(quán)可以

8、表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。這種帶權(quán)的圖通常稱為這種帶權(quán)的圖通常稱為網(wǎng)網(wǎng)(Network)。abcd(b) (b) 無(wú)向圖無(wú)向圖G2 G2 (a) (a) 有向圖有向圖G1 G1 acbdeu子圖：子圖：設(shè)有圖設(shè)有圖G=(VG=(V，E)E)和和G=(VG=(V，E)E)，若，若VV V V且且EE E E，則稱圖，則稱圖GG是是G G的的子圖。子圖。ABCD無(wú)向圖無(wú)向圖 G2AACDACABCD有向圖有向圖G1的子圖的子圖ABCDEABDEAABCDABCDE無(wú)向圖無(wú)向圖G2的子圖的子圖有向圖有向圖 G1u頂點(diǎn)的鄰接頂點(diǎn)的鄰接(Adjacent)(Adjacent)：對(duì)于無(wú)向圖：

9、對(duì)于無(wú)向圖G=(VG=(V，E)E)，若邊，若邊( (v,wv,w) ) E E，則稱頂點(diǎn)，則稱頂點(diǎn)v v和和w w互為互為鄰接點(diǎn)鄰接點(diǎn)，即，即v v和和w w相鄰接。邊相鄰接。邊( (v,wv,w) )依附依附(incident)(incident)與頂點(diǎn)與頂點(diǎn)v v和和w w 。u對(duì)于有向圖對(duì)于有向圖G=(VG=(V，E)E)，若有向弧，若有向弧 E E，則稱頂點(diǎn)，則稱頂點(diǎn)v v“鄰接到鄰接到”頂點(diǎn)頂點(diǎn)w w，頂點(diǎn)，頂點(diǎn)w w“鄰接自鄰接自”頂點(diǎn)頂點(diǎn)v v，弧，弧 與頂與頂點(diǎn)點(diǎn)v v和和w w“相關(guān)聯(lián)相關(guān)聯(lián)”。u頂點(diǎn)的度、入度、出度：頂點(diǎn)的度、入度、出度：以頂點(diǎn)以頂點(diǎn)v v為頭的弧的數(shù)目稱

10、為為頭的弧的數(shù)目稱為v v的的入度入度( (I InDnDegreeegree) )，記為，記為I ID(v);D(v);以以v v為尾的弧的數(shù)目稱為為尾的弧的數(shù)目稱為v v的的出 度出 度 ( ( O u t D e g r e eO u t D e g r e e ) ) ， 記 為， 記 為 O D ( v ) ;O D ( v ) ; 頂 點(diǎn)頂 點(diǎn) v v 的 度 為的 度 為T(mén)D(v)=ID(v)+OD(v)TD(v)=ID(v)+OD(v)。 V0 V1 V2 V3u一般地，如果頂點(diǎn)一般地，如果頂點(diǎn)v vi i的度記為的度記為T(mén)D(v),TD(v),那么一那么一個(gè)有個(gè)有n n個(gè)頂點(diǎn)

11、，個(gè)頂點(diǎn)，e e條邊或弧的圖滿足如下關(guān)系：條邊或弧的圖滿足如下關(guān)系：11()2niieTD v路徑、回路路徑、回路( (環(huán)環(huán)) )u無(wú)向圖無(wú)向圖G G1 1= =（V V1 1，E E1 1）中從頂點(diǎn)）中從頂點(diǎn)v v到頂點(diǎn)到頂點(diǎn)vv的路徑的路徑(Path)(Path)是一個(gè)頂點(diǎn)序列是一個(gè)頂點(diǎn)序列(v=v(v=vi 0i 0，v vi 1i 1，,v,vi mi m=v),=v),其中其中(v(vi i,v,vi+1i+1) ) E E1 1 ( ( i i=1,2,k-1)=1,2,k-1)。第一個(gè)頂點(diǎn)和最后一個(gè)頂。第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路或環(huán)。點(diǎn)相同的路徑稱為回路或環(huán)。在在

12、G G1 1中，中，v v0 0,v,v1 1,v,v2 2,v,v3 3 是是v v0 0到到v v3 3的路徑；的路徑； v v0 0,v,v1 1,v,v2 2,v,v3 3 , , v v0 0是回路。是回路。u 如果是有向圖如果是有向圖G G2 2= =（V V2 2，E E2 2），則路徑也是有向的。），則路徑也是有向的。在在G G2 2中，中，v v0 0, v, v2 2, v, v3 3是是v v0 0到到v v3 3的路徑；的路徑； v v0 0,v,v2 2,v,v3 3,v,v0 0是回路。是回路。無(wú)向圖無(wú)向圖G1有向圖有向圖G2 V0 V4 V3 V1 V2 V0 V

13、1 V2 V3u序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為為簡(jiǎn)單路徑簡(jiǎn)單路徑。除了第一個(gè)頂點(diǎn)和最。除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路，稱出現(xiàn)的回路，稱簡(jiǎn)單回路或環(huán)簡(jiǎn)單回路或環(huán)。連通、連通分量和連通圖、生成樹(shù)連通、連通分量和連通圖、生成樹(shù)在無(wú)向圖在無(wú)向圖G G中：中：u如果從頂點(diǎn)如果從頂點(diǎn)V Vi i 到頂點(diǎn)到頂點(diǎn)V Vj j有路徑，則稱有路徑，則稱V Vi i與與V Vj j是是連通的連通的。u如果圖中任意兩個(gè)頂點(diǎn)都連通，則稱如果圖中任意兩個(gè)頂點(diǎn)都連通，則稱G G為為連通圖連通圖，否則稱，否則稱為為非連通圖非連通圖。u在非連

14、通圖在非連通圖G G中，任何一個(gè)極大連通子圖稱為中，任何一個(gè)極大連通子圖稱為G G的的連通分量連通分量。u任何連通圖的連通分量只有一個(gè)，即其自身，而非連通圖任何連通圖的連通分量只有一個(gè)，即其自身，而非連通圖有多個(gè)連通分量。有多個(gè)連通分量。u在一個(gè)連通圖中，含有全部頂點(diǎn)的極小在一個(gè)連通圖中，含有全部頂點(diǎn)的極小( (邊數(shù)最少邊數(shù)最少) )連通子連通子圖，稱為該連通圖的圖，稱為該連通圖的生成樹(shù)生成樹(shù)。( (包含圖的所有包含圖的所有 n n 個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，但只含圖的但只含圖的 n-1 n-1 條邊。在生成樹(shù)中添加一條邊之后，必定條邊。在生成樹(shù)中添加一條邊之后，必定會(huì)形成回路或環(huán)會(huì)形成回路或環(huán)) )非

15、連通圖非連通圖G4G4A AB BC CD DE EF FG GI IJ JK KA AB BC CD DE EI IJ JK KF FG G非連通圖非連通圖G4G4的三個(gè)連通分量的三個(gè)連通分量連通圖連通圖G5G5A AB BC CD D連通圖連通圖G5G5的兩棵生成樹(shù)的兩棵生成樹(shù)A AB BC CD DA AB BC CD D強(qiáng)連通、強(qiáng)連通分量和強(qiáng)連通圖強(qiáng)連通、強(qiáng)連通分量和強(qiáng)連通圖在有向圖在有向圖G G中：中：u存在從頂點(diǎn)存在從頂點(diǎn)V Vi i 到頂點(diǎn)到頂點(diǎn)V Vj j的路徑，也存在從頂點(diǎn)的路徑，也存在從頂點(diǎn)V Vj j 到頂點(diǎn)到頂點(diǎn)V Vi i的路徑，則稱的路徑，則稱V Vi i與與V V

16、j j是是強(qiáng)連通強(qiáng)連通的。的。u如果圖中任意兩個(gè)頂點(diǎn)都是強(qiáng)連通，則稱如果圖中任意兩個(gè)頂點(diǎn)都是強(qiáng)連通，則稱G G為為強(qiáng)連通圖強(qiáng)連通圖，否則稱為否則稱為非強(qiáng)連通圖非強(qiáng)連通圖。u在非強(qiáng)連通圖在非強(qiáng)連通圖G G中，任何一個(gè)極大強(qiáng)連通子圖稱為中，任何一個(gè)極大強(qiáng)連通子圖稱為G G的的強(qiáng)強(qiáng)連通分量連通分量。u任何強(qiáng)連通圖的強(qiáng)連通分量只有一個(gè)，即其自身，而非任何強(qiáng)連通圖的強(qiáng)連通分量只有一個(gè)，即其自身，而非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。有向圖有向圖G G和強(qiáng)連通分量示例：和強(qiáng)連通分量示例：A AB BC CD DE EF FA AB BC CD DE EF F(a)有向圖有向圖G(c)強(qiáng)連

17、通分量強(qiáng)連通分量2(b)強(qiáng)連通分量強(qiáng)連通分量1(d)強(qiáng)連通分量強(qiáng)連通分量37.1.2 7.1.2 圖的抽象數(shù)據(jù)類型定義圖的抽象數(shù)據(jù)類型定義ADT Graph數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象V：具有相同特性的數(shù)據(jù)元素的集合，稱為頂：具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集點(diǎn)集。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：R=VRVR=| v,w Vp(v,w) ，表示表示 從從v到到w的弧，的弧，P(v,w)定義了弧定義了弧的信息的信息 基本操作基本操作P： ADT Graph 基本操作基本操作P:結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀: :CreateGraphCreateGraph(&G,V,VR); / (&G,V,V

18、R); / 按按V V和和VRVR的定義構(gòu)造圖的定義構(gòu)造圖G G。DestroyGraphDestroyGraph(&G); / (&G); / 銷毀圖銷毀圖G G。對(duì)頂點(diǎn)的訪問(wèn)操作對(duì)頂點(diǎn)的訪問(wèn)操作: :LocateVexLocateVex(G, u); / (G, u); / 若若G G中存在頂點(diǎn)中存在頂點(diǎn)u u，則返回該頂點(diǎn)在，則返回該頂點(diǎn)在圖中位置；否則返回其它信息。圖中位置；否則返回其它信息。GetVexGetVex(G, v); / (G, v); / 返回返回v v的值。的值。PutVexPutVex(&G, v, value); / (&G, v,

19、 value); / 對(duì)對(duì)v v賦值賦值valuevalue。對(duì)鄰接點(diǎn)的操作對(duì)鄰接點(diǎn)的操作: :FirstAdjVexFirstAdjVex(G, v); / (G, v); / 返回返回v v的第一個(gè)鄰接點(diǎn)。若該頂點(diǎn)的第一個(gè)鄰接點(diǎn)。若該頂點(diǎn)/在在G G中沒(méi)有鄰接點(diǎn)，則返回中沒(méi)有鄰接點(diǎn)，則返回“空空”。NextAdjVexNextAdjVex(G, v, w); /(G, v, w); /返回返回v v的（相對(duì)于的（相對(duì)于w w的）下一個(gè)的）下一個(gè) 鄰接點(diǎn)。若鄰接點(diǎn)。若w w是是v v的最后一個(gè)鄰接點(diǎn)，則返回的最后一個(gè)鄰接點(diǎn)，則返回“空空”。 插入或刪除頂點(diǎn)插入或刪除頂點(diǎn)InsertVexIn

20、sertVex(&G, v); / (&G, v); / 在圖在圖G G中增添新頂點(diǎn)中增添新頂點(diǎn)v v。DeleteVexDeleteVex(&G, v); / (&G, v); / 刪除刪除G G中頂點(diǎn)中頂點(diǎn)v v及其相關(guān)的弧。及其相關(guān)的弧。插入和刪除弧插入和刪除弧InsertArcInsertArc(&G, v, w); / (&G, v, w); / 在在G G中增添弧中增添弧 ，若，若G G是無(wú)是無(wú)向的，則還增添對(duì)稱弧向的，則還增添對(duì)稱弧 。DeleteArcDeleteArc(&G, v, w); /(&G, v, w)

21、; /在在G G中刪除弧中刪除弧 ，若，若G G是無(wú)是無(wú) 向的，則還刪除對(duì)稱弧向的，則還刪除對(duì)稱弧 。遍歷遍歷DFSTraverseDFSTraverse(G, v, Visit(); / (G, v, Visit(); / 從頂點(diǎn)從頂點(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一次且僅一次。一次且僅一次。BFSTraverseBFSTraverse(G, v, Visit(); / (G, v, Visit(); / 從頂點(diǎn)從頂點(diǎn)v v起廣度優(yōu)先遍起廣度優(yōu)先遍歷圖歷圖G G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit

22、Visit一次且僅一次。一次且僅一次。7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu) 圖的存儲(chǔ)結(jié)構(gòu)比較復(fù)雜，其圖的存儲(chǔ)結(jié)構(gòu)比較復(fù)雜，其復(fù)雜性復(fù)雜性主要表現(xiàn)在：主要表現(xiàn)在：u任意頂點(diǎn)之間可能存在聯(lián)系，無(wú)法以數(shù)據(jù)元素在任意頂點(diǎn)之間可能存在聯(lián)系，無(wú)法以數(shù)據(jù)元素在存儲(chǔ)區(qū)中的物理位置來(lái)表示元素之間的關(guān)系。存儲(chǔ)區(qū)中的物理位置來(lái)表示元素之間的關(guān)系。u圖中頂點(diǎn)的度不一樣，有的可能相差很大，若按圖中頂點(diǎn)的度不一樣，有的可能相差很大，若按度數(shù)最大的頂點(diǎn)設(shè)計(jì)結(jié)構(gòu)，則會(huì)浪費(fèi)很多存儲(chǔ)單度數(shù)最大的頂點(diǎn)設(shè)計(jì)結(jié)構(gòu)，則會(huì)浪費(fèi)很多存儲(chǔ)單元，反之按每個(gè)頂點(diǎn)自己的度設(shè)計(jì)不同的結(jié)構(gòu)，元，反之按每個(gè)頂點(diǎn)自己的度設(shè)計(jì)不同的結(jié)構(gòu)，又會(huì)影響操作。又

23、會(huì)影響操作。 圖的存儲(chǔ)結(jié)構(gòu)至少要保存兩類信息：圖的存儲(chǔ)結(jié)構(gòu)至少要保存兩類信息： (1)頂點(diǎn)的數(shù)據(jù)；頂點(diǎn)的數(shù)據(jù)； (2)頂點(diǎn)間的關(guān)系。頂點(diǎn)間的關(guān)系。 如何表示頂點(diǎn)間的關(guān)系？如何表示頂點(diǎn)間的關(guān)系？ V0 V4 V3 V1 V2 V0 V1 V2 V3常用圖的存儲(chǔ)表示常用圖的存儲(chǔ)表示圖的數(shù)組圖的數(shù)組( (鄰接矩陣鄰接矩陣) )存儲(chǔ)表示存儲(chǔ)表示圖的鄰接表存儲(chǔ)表示圖的鄰接表存儲(chǔ)表示有向圖的十字鏈表存儲(chǔ)表示有向圖的十字鏈表存儲(chǔ)表示無(wú)向圖的鄰接多重表存儲(chǔ)表示無(wú)向圖的鄰接多重表存儲(chǔ)表示 7.2.1 7.2.1 鄰接矩陣鄰接矩陣( (數(shù)組數(shù)組) )表示法表示法 基本思想：基本思想：對(duì)于有對(duì)于有n n個(gè)頂點(diǎn)的圖，

24、用個(gè)頂點(diǎn)的圖，用一維數(shù)組一維數(shù)組vexsvexsnn存儲(chǔ)頂點(diǎn)信息存儲(chǔ)頂點(diǎn)信息，用，用二維數(shù)組二維數(shù)組AnnAnn存儲(chǔ)存儲(chǔ)頂點(diǎn)之間關(guān)系的信息頂點(diǎn)之間關(guān)系的信息。該二維數(shù)組稱為鄰接矩陣。該二維數(shù)組稱為鄰接矩陣。在鄰接矩陣中，以頂點(diǎn)在在鄰接矩陣中，以頂點(diǎn)在vexsvexs數(shù)組中的下標(biāo)代表數(shù)組中的下標(biāo)代表頂點(diǎn)，鄰接矩陣中的頂點(diǎn)，鄰接矩陣中的元素元素AAi ijj存放的是頂點(diǎn)存放的是頂點(diǎn)i i到頂點(diǎn)到頂點(diǎn)j j之間關(guān)系的信息之間關(guān)系的信息。1 無(wú)向圖的數(shù)組表示無(wú)向圖的數(shù)組表示(1) (1) 無(wú)權(quán)圖的鄰接矩陣無(wú)權(quán)圖的鄰接矩陣 無(wú)向無(wú)權(quán)圖無(wú)向無(wú)權(quán)圖G=(V，E)有有n(n1)個(gè)頂點(diǎn)，其鄰接矩陣是個(gè)頂點(diǎn)，其鄰

25、接矩陣是n階對(duì)稱方陣，如圖下圖所示。其元素的定義如下：階對(duì)稱方陣，如圖下圖所示。其元素的定義如下：1 若若(vi , vj) E，即，即vi , vj鄰接鄰接0 若若(vi , vj) E，即，即vi , vj不鄰接不鄰接Aij=(a) 無(wú)向圖無(wú)向圖 abcd無(wú)向無(wú)權(quán)圖的數(shù)組存儲(chǔ)無(wú)向無(wú)權(quán)圖的數(shù)組存儲(chǔ)(b) 頂點(diǎn)矩陣頂點(diǎn)矩陣vexsabcd0 1 1 11 0 1 11 1 0 11 1 1 0(c) 鄰接矩陣鄰接矩陣(2) 帶權(quán)圖的鄰接矩陣帶權(quán)圖的鄰接矩陣 無(wú)向帶權(quán)圖無(wú)向帶權(quán)圖G=(VG=(V，E) E) 的鄰接矩陣如下圖所示。其元素的鄰接矩陣如下圖所示。其元素的定義如下：的定義如下：(a)

26、帶權(quán)無(wú)向圖帶權(quán)無(wú)向圖 (b) 頂點(diǎn)矩陣頂點(diǎn)矩陣無(wú)向帶權(quán)圖的數(shù)組存儲(chǔ)無(wú)向帶權(quán)圖的數(shù)組存儲(chǔ)(c) 鄰接矩陣鄰接矩陣354126abcde3vexsabcde 6 2 6 3 4 32 3 1 4 3 5 3 5 Wij 若若(vi , vj) E，即，即vi , vj鄰接，權(quán)值為鄰接，權(quán)值為wij 若若(vi , vj) E，即，即vi , vj不鄰接時(shí)不鄰接時(shí)Aij=(3) (3) 無(wú)向圖鄰接矩陣的特性無(wú)向圖鄰接矩陣的特性 鄰接矩陣是鄰接矩陣是對(duì)稱方陣對(duì)稱方陣； 對(duì)于頂點(diǎn)對(duì)于頂點(diǎn)vi，其度數(shù)是第，其度數(shù)是第i行的非行的非0元素的個(gè)數(shù)；元素的個(gè)數(shù)； 無(wú)向圖的邊數(shù)是上無(wú)向圖的邊數(shù)是上(或下或下)三角

27、形矩陣中非三角形矩陣中非0元素個(gè)數(shù)。元素個(gè)數(shù)。0 1 1 11 0 1 11 1 0 11 1 1 0 6 2 6 3 4 32 3 1 4 3 5 3 5 2 2 有向圖的數(shù)組表示有向圖的數(shù)組表示(1) (1) 無(wú)權(quán)圖的鄰接矩陣無(wú)權(quán)圖的鄰接矩陣 若有向無(wú)權(quán)圖若有向無(wú)權(quán)圖G=(VG=(V，E)E)有有n(n1)n(n1)個(gè)頂點(diǎn)，則其鄰接矩個(gè)頂點(diǎn)，則其鄰接矩陣是陣是n n階方陣，如下圖所示。元素定義如下：階方陣，如下圖所示。元素定義如下：1 若若 E，從，從vi到到vj有弧有弧Aij=0 若若 E 從從vi到到vj 沒(méi)有弧沒(méi)有弧(a) 有向圖有向圖acbde 有向無(wú)權(quán)圖的數(shù)組存儲(chǔ)有向無(wú)權(quán)圖的數(shù)組

28、存儲(chǔ)(b) 頂點(diǎn)矩陣頂點(diǎn)矩陣vexsabcde(c) 鄰接矩陣鄰接矩陣0 0 1 1 0 10 10 0 0 0 00 0 0 1 1 11 1 1 0 0 00 0 0 0 0 1 0(2) (2) 帶權(quán)圖的鄰接矩陣帶權(quán)圖的鄰接矩陣 有向帶權(quán)圖有向帶權(quán)圖G=(VG=(V，E)E)的鄰接矩陣如下圖所示。其元素的的鄰接矩陣如下圖所示。其元素的定義如下：定義如下：wij 若若 E，即，即vi , vj鄰接，權(quán)值為鄰接，權(quán)值為wij 若若 E，即，即vi , vj不鄰接時(shí)不鄰接時(shí)Aij= 帶權(quán)有向圖的數(shù)組存儲(chǔ)帶權(quán)有向圖的數(shù)組存儲(chǔ)(b) 頂點(diǎn)矩陣頂點(diǎn)矩陣vexsabcde(c) 鄰接矩陣鄰接矩陣 6

29、2 3 3 1 4 4 5 (a) 帶權(quán)有向圖帶權(quán)有向圖 354126abcde3 有向圖鄰接矩陣的特性有向圖鄰接矩陣的特性 對(duì)于頂點(diǎn)對(duì)于頂點(diǎn)v vi i，第，第i i行的非行的非0 0元素的個(gè)數(shù)是其出度元素的個(gè)數(shù)是其出度OD(vOD(vi i) )；第第i i列的非列的非0 0元素的個(gè)數(shù)是其入度元素的個(gè)數(shù)是其入度ID(vID(vi i) ) 。 鄰接矩陣中非鄰接矩陣中非0 0元素的個(gè)數(shù)就是圖的弧的數(shù)目。元素的個(gè)數(shù)就是圖的弧的數(shù)目。0 0 1 1 0 10 10 0 0 0 00 0 0 1 1 11 1 1 0 0 00 0 0 0 0 1 0 6 2 3 3 1 4 4 5 7.2.2 7

30、.2.2 鄰接鏈表法鄰接鏈表法 基本思想：基本思想：對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表單鏈表，存儲(chǔ)該存儲(chǔ)該頂點(diǎn)所有鄰接頂點(diǎn)及其相關(guān)信息頂點(diǎn)所有鄰接頂點(diǎn)及其相關(guān)信息。每一個(gè)。每一個(gè)單鏈表設(shè)一個(gè)單鏈表設(shè)一個(gè)表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)。 第第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊的邊(對(duì)有向圖是以頂點(diǎn)對(duì)有向圖是以頂點(diǎn)Vi為尾的弧為尾的弧)。1 1 結(jié)點(diǎn)結(jié)構(gòu)與鄰接鏈表示例結(jié)點(diǎn)結(jié)構(gòu)與鄰接鏈表示例 鏈表中的結(jié)點(diǎn)稱為鏈表中的結(jié)點(diǎn)稱為表結(jié)點(diǎn)表結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)由三個(gè)域組成，如，每個(gè)結(jié)點(diǎn)由三個(gè)域組成，如下圖所示。下圖所示。鄰接點(diǎn)域鄰接點(diǎn)域(adjvex)指示與頂點(diǎn)指示與頂點(diǎn)Vi

31、鄰接的頂點(diǎn)在圖中的位置鄰接的頂點(diǎn)在圖中的位置(頂點(diǎn)編號(hào)頂點(diǎn)編號(hào))；鏈域鏈域(nextarc)指向下一個(gè)與頂點(diǎn)指向下一個(gè)與頂點(diǎn)Vi鄰接的表結(jié)點(diǎn)；鄰接的表結(jié)點(diǎn)；數(shù)據(jù)域數(shù)據(jù)域(info)存儲(chǔ)和邊或弧相關(guān)的信息，如權(quán)值等。存儲(chǔ)和邊或弧相關(guān)的信息，如權(quán)值等。對(duì)于無(wú)權(quán)圖，如果沒(méi)有與邊相關(guān)的其他信息，可省略此域。對(duì)于無(wú)權(quán)圖，如果沒(méi)有與邊相關(guān)的其他信息，可省略此域。 每個(gè)鏈表設(shè)一個(gè)每個(gè)鏈表設(shè)一個(gè)表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)(稱為頂點(diǎn)結(jié)點(diǎn)稱為頂點(diǎn)結(jié)點(diǎn))，由兩個(gè)域組，由兩個(gè)域組成，如圖所示。成，如圖所示。鏈域鏈域(firstarc)指向鏈表中的第一個(gè)結(jié)點(diǎn)；指向鏈表中的第一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域數(shù)據(jù)域(data) 存儲(chǔ)頂點(diǎn)名或其他信息

32、。存儲(chǔ)頂點(diǎn)名或其他信息。adjvex info nextarc表結(jié)點(diǎn)表結(jié)點(diǎn)：data firstarc頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)： 鄰接鏈表結(jié)點(diǎn)結(jié)構(gòu)鄰接鏈表結(jié)點(diǎn)結(jié)構(gòu) 在圖的鄰接鏈表表示中，在圖的鄰接鏈表表示中，所有頂點(diǎn)結(jié)點(diǎn)所有頂點(diǎn)結(jié)點(diǎn)用一用一個(gè)向量以順序結(jié)構(gòu)形式存儲(chǔ)，可以隨機(jī)訪問(wèn)任意個(gè)向量以順序結(jié)構(gòu)形式存儲(chǔ)，可以隨機(jī)訪問(wèn)任意頂點(diǎn)的鏈表，該向量稱為頂點(diǎn)的鏈表，該向量稱為表頭向量表頭向量，向量的下標(biāo)，向量的下標(biāo)指示頂點(diǎn)的序號(hào)。指示頂點(diǎn)的序號(hào)。無(wú)向圖及其鄰接鏈表無(wú)向圖及其鄰接鏈表v1v2v3v4v501234MAX_VEX-1v1 v2v3 v4 v5 213 02 0314 204 23 (a) 有向圖有向

33、圖v1v2v3v4v513 014 2 3 01234MAX_VEX-1v1 2 v2 0 v3 3v4 1 v5 1 (b) 正鄰接鏈表，出度直觀正鄰接鏈表，出度直觀2 02 2 01234MAX_VEX-1v1 1v2 2v3 1v4 2 v5 1 3 04 (c) 逆鄰接鏈表，入度直觀逆鄰接鏈表，入度直觀有向圖及其鄰接鏈表有向圖及其鄰接鏈表對(duì)有向圖，其鄰接鏈表對(duì)有向圖，其鄰接鏈表有兩種形式，如圖所示。有兩種形式，如圖所示。2 2 鄰接表法的特點(diǎn)鄰接表法的特點(diǎn)表頭向量中每個(gè)分量就是一個(gè)單鏈表的頭結(jié)點(diǎn)，分量個(gè)表頭向量中每個(gè)分量就是一個(gè)單鏈表的頭結(jié)點(diǎn)，分量個(gè)數(shù)就是圖中的頂點(diǎn)數(shù)目；數(shù)就是圖中的頂

34、點(diǎn)數(shù)目；在邊或弧稀疏的條件下，用鄰接表表示比用鄰接矩陣表在邊或弧稀疏的條件下，用鄰接表表示比用鄰接矩陣表示節(jié)省存儲(chǔ)空間；示節(jié)省存儲(chǔ)空間；在在無(wú)向圖無(wú)向圖，頂點(diǎn)，頂點(diǎn)V Vi i的度是第的度是第i i個(gè)鏈表的結(jié)點(diǎn)數(shù)；個(gè)鏈表的結(jié)點(diǎn)數(shù)；對(duì)對(duì)有向圖有向圖可以建立可以建立正鄰接表或逆鄰接表正鄰接表或逆鄰接表。正鄰接表是以。正鄰接表是以頂點(diǎn)頂點(diǎn)V Vi i為出度為出度( (即為弧的起點(diǎn)即為弧的起點(diǎn)) )而建立的鄰接表；逆鄰接表而建立的鄰接表；逆鄰接表是以頂點(diǎn)是以頂點(diǎn)V Vi i為入度為入度( (即為弧的終點(diǎn)即為弧的終點(diǎn)) )而建立的鄰接表；而建立的鄰接表；在在有向圖有向圖中，第中，第i i個(gè)鏈表中的結(jié)點(diǎn)數(shù)

35、是頂點(diǎn)個(gè)鏈表中的結(jié)點(diǎn)數(shù)是頂點(diǎn)V Vi i的出的出 ( (或入或入) )度；求入度；求入 ( (或出或出) )度，須遍歷整個(gè)鄰接表；度，須遍歷整個(gè)鄰接表；在鄰接表上容易找出任一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)在鄰接表上容易找出任一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)。鄰接點(diǎn)。7.2.3 7.2.3 十字鏈表法十字鏈表法 十字鏈表十字鏈表(Orthogonal List)(Orthogonal List)是有向圖的另一種鏈?zhǔn)酱媸怯邢驁D的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是將有向圖的儲(chǔ)結(jié)構(gòu)，是將有向圖的正鄰接表和逆鄰接表結(jié)合正鄰接表和逆鄰接表結(jié)合起來(lái)得到的起來(lái)得到的一種鏈表。一種鏈表。 在這種結(jié)構(gòu)中，每條弧的弧頭結(jié)點(diǎn)和弧尾

36、結(jié)點(diǎn)都存放在在這種結(jié)構(gòu)中，每條弧的弧頭結(jié)點(diǎn)和弧尾結(jié)點(diǎn)都存放在鏈表中，并將弧結(jié)點(diǎn)分別組織到鏈表中，并將弧結(jié)點(diǎn)分別組織到以弧尾結(jié)點(diǎn)為頭以弧尾結(jié)點(diǎn)為頭( (頂點(diǎn)頂點(diǎn)) )結(jié)點(diǎn)結(jié)點(diǎn)和以弧頭結(jié)點(diǎn)為頭和以弧頭結(jié)點(diǎn)為頭( (頂點(diǎn)頂點(diǎn)) )結(jié)點(diǎn)結(jié)點(diǎn)的鏈表中。這種結(jié)構(gòu)的結(jié)點(diǎn)邏的鏈表中。這種結(jié)構(gòu)的結(jié)點(diǎn)邏輯結(jié)構(gòu)如下圖所示。輯結(jié)構(gòu)如下圖所示?；〗Y(jié)點(diǎn)弧結(jié)點(diǎn)tailvex headvex info hlink tlink頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)Data firstin firstout十字鏈表結(jié)點(diǎn)結(jié)構(gòu)十字鏈表結(jié)點(diǎn)結(jié)構(gòu) datadata域：域：存儲(chǔ)和頂點(diǎn)相關(guān)的信息；存儲(chǔ)和頂點(diǎn)相關(guān)的信息； 指針域指針域firstinfirstin：

37、指向以該頂點(diǎn)為弧頭的第一條弧所對(duì)指向以該頂點(diǎn)為弧頭的第一條弧所對(duì)應(yīng)的弧結(jié)點(diǎn)；應(yīng)的弧結(jié)點(diǎn)； 指針域指針域firstoutfirstout：指向以該頂點(diǎn)為弧尾的第一條弧所對(duì)指向以該頂點(diǎn)為弧尾的第一條弧所對(duì)應(yīng)的弧結(jié)點(diǎn)；應(yīng)的弧結(jié)點(diǎn)； 尾域尾域tailvextailvex：指示弧尾頂點(diǎn)在圖中的位置；指示弧尾頂點(diǎn)在圖中的位置； 頭域頭域headvexheadvex：指示弧頭頂點(diǎn)在圖中的位置；指示弧頭頂點(diǎn)在圖中的位置； 指針域指針域hlinkhlink：指向弧頭相同的下一條??；指向弧頭相同的下一條弧； 指針域指針域tlinktlink：指向弧尾相同的下一條弧；指向弧尾相同的下一條弧； InfoInfo域：域

38、：指向該弧的相關(guān)信息。指向該弧的相關(guān)信息?；〗Y(jié)點(diǎn)弧結(jié)點(diǎn)tailvex headvex info hlink tlink頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)Data firstin firstout十字鏈表結(jié)點(diǎn)結(jié)構(gòu)十字鏈表結(jié)點(diǎn)結(jié)構(gòu) 下圖所示是一個(gè)有向圖及其十字鏈表下圖所示是一個(gè)有向圖及其十字鏈表( (略去了表結(jié)點(diǎn)的略去了表結(jié)點(diǎn)的infoinfo域域) )。從這種存儲(chǔ)結(jié)構(gòu)圖可以看出，從一個(gè)頂點(diǎn)結(jié)點(diǎn)的。從這種存儲(chǔ)結(jié)構(gòu)圖可以看出，從一個(gè)頂點(diǎn)結(jié)點(diǎn)的firstoutfirstout出發(fā)，沿表結(jié)點(diǎn)的出發(fā)，沿表結(jié)點(diǎn)的tlinktlink指針構(gòu)成了正鄰接表的鏈指針構(gòu)成了正鄰接表的鏈表結(jié)構(gòu)，而從一個(gè)頂點(diǎn)結(jié)點(diǎn)的表結(jié)構(gòu)，而從一個(gè)頂點(diǎn)結(jié)點(diǎn)

39、的firstinfirstin出發(fā)，沿表結(jié)點(diǎn)的出發(fā)，沿表結(jié)點(diǎn)的hlinkhlink指針構(gòu)成了逆鄰接表的鏈表結(jié)構(gòu)。指針構(gòu)成了逆鄰接表的鏈表結(jié)構(gòu)。V V0 0V V1 1V V2 2V V3 30 10 2 2 02 3 3 0 3 1 3 2 0213V0V1 V2V3有向圖的十字鏈表結(jié)構(gòu)有向圖的十字鏈表結(jié)構(gòu)7.2.4 7.2.4 鄰接多重表鄰接多重表 鄰接多重表鄰接多重表(Adjacency (Adjacency MultilistMultilist) )是無(wú)向圖的另一種是無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。這是一種有效的存儲(chǔ)結(jié)構(gòu)，在無(wú)向圖的鄰鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。這是一種有效的存儲(chǔ)結(jié)構(gòu)，在無(wú)向圖的鄰接表中，

40、接表中，一條邊一條邊( (v,wv,w) )的兩個(gè)表結(jié)點(diǎn)分別出現(xiàn)在以的兩個(gè)表結(jié)點(diǎn)分別出現(xiàn)在以v v和和w w為頭為頭結(jié)點(diǎn)的鏈表結(jié)點(diǎn)的鏈表中，很容易求得頂點(diǎn)和邊的信息，但在涉及到中，很容易求得頂點(diǎn)和邊的信息，但在涉及到邊的操作會(huì)帶來(lái)不便。邊的操作會(huì)帶來(lái)不便。 鄰接多重表的結(jié)構(gòu)和十字鏈表類似，每條邊用一個(gè)結(jié)鄰接多重表的結(jié)構(gòu)和十字鏈表類似，每條邊用一個(gè)結(jié)點(diǎn)表示；鄰接多重表中的頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)與鄰接表中的完全點(diǎn)表示；鄰接多重表中的頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)與鄰接表中的完全相同，而表結(jié)點(diǎn)包括六個(gè)域，如圖所示。相同，而表結(jié)點(diǎn)包括六個(gè)域，如圖所示。data firstedge頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn) 鄰接多重表的結(jié)點(diǎn)結(jié)構(gòu)鄰接多重表的

41、結(jié)點(diǎn)結(jié)構(gòu)表結(jié)點(diǎn)表結(jié)點(diǎn)mark ivex jvex info ilink jlink DataData域：域：存儲(chǔ)和頂點(diǎn)相關(guān)的信息；存儲(chǔ)和頂點(diǎn)相關(guān)的信息； 指針域指針域firstedgefirstedge：指向依附于該頂點(diǎn)的第一條邊所對(duì)指向依附于該頂點(diǎn)的第一條邊所對(duì)應(yīng)的表結(jié)點(diǎn)；應(yīng)的表結(jié)點(diǎn)； 標(biāo)志域標(biāo)志域markmark：用以標(biāo)識(shí)該條邊是否被訪問(wèn)過(guò)；用以標(biāo)識(shí)該條邊是否被訪問(wèn)過(guò)； ivexivex和和jvexjvex域：域：分別保存該邊所依附的兩個(gè)頂點(diǎn)在圖分別保存該邊所依附的兩個(gè)頂點(diǎn)在圖中的位置；中的位置； infoinfo域：域：保存該邊的相關(guān)信息；保存該邊的相關(guān)信息； 指針域指針域ilinkil

42、ink：指向下一條依附于頂點(diǎn)指向下一條依附于頂點(diǎn)ivexivex的邊；的邊； 指針域指針域jlinkjlink：指向下一條依附于頂點(diǎn)指向下一條依附于頂點(diǎn)jvexjvex的邊；的邊；data firstedge頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn) 鄰接多重表的結(jié)點(diǎn)結(jié)構(gòu)鄰接多重表的結(jié)點(diǎn)結(jié)構(gòu)表結(jié)點(diǎn)表結(jié)點(diǎn)mark ivex ilink jvex info jlink鄰接多重表與鄰接表的區(qū)別：鄰接多重表與鄰接表的區(qū)別： 后者的同一條邊用兩個(gè)表結(jié)點(diǎn)表示，而前者后者的同一條邊用兩個(gè)表結(jié)點(diǎn)表示，而前者只用一個(gè)表結(jié)點(diǎn)表示只用一個(gè)表結(jié)點(diǎn)表示；除標(biāo)志域外，鄰接多重表除標(biāo)志域外，鄰接多重表與鄰接表表達(dá)的信息是相同的，因此，操作的實(shí)與鄰接

43、表表達(dá)的信息是相同的，因此，操作的實(shí)現(xiàn)也基本相似?，F(xiàn)也基本相似。無(wú)向圖及其多重鄰接鏈表無(wú)向圖及其多重鄰接鏈表v1v2v3v4v1v2v3v40123 0 1 0 2 2 1 2 3 0 37.3 7.3 圖的遍歷圖的遍歷 圖的遍歷圖的遍歷( (TraveringTravering Graph) Graph)：從圖的某一頂點(diǎn)出發(fā)，從圖的某一頂點(diǎn)出發(fā)，訪遍圖中的其余頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問(wèn)一次。圖的遍訪遍圖中的其余頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問(wèn)一次。圖的遍歷算法是各種圖的其他操作的基礎(chǔ)。歷算法是各種圖的其他操作的基礎(chǔ)。 復(fù)雜性：復(fù)雜性：圖的任意頂點(diǎn)可能和其余的頂點(diǎn)相鄰接，圖的任意頂點(diǎn)可能和其余的頂點(diǎn)相鄰

44、接，可能在訪問(wèn)了某個(gè)頂點(diǎn)后，沿某條路徑搜索后又回到原可能在訪問(wèn)了某個(gè)頂點(diǎn)后，沿某條路徑搜索后又回到原頂點(diǎn)。頂點(diǎn)。 解決辦法：解決辦法：在遍歷過(guò)程中記下已被訪問(wèn)過(guò)的頂點(diǎn)。在遍歷過(guò)程中記下已被訪問(wèn)過(guò)的頂點(diǎn)。設(shè)置一個(gè)輔助向量設(shè)置一個(gè)輔助向量Visited0Visited0n-1(nn-1(n為頂點(diǎn)數(shù)為頂點(diǎn)數(shù)) )，其初，其初值為值為0 0，一旦訪問(wèn)了頂點(diǎn)，一旦訪問(wèn)了頂點(diǎn)v vi i后，使后，使VisitedVisitedi i 為為1 1或?yàn)樵L或?yàn)樵L問(wèn)的次序號(hào)。問(wèn)的次序號(hào)。 圖的遍歷算法有圖的遍歷算法有深度優(yōu)先搜索算法深度優(yōu)先搜索算法和和廣度優(yōu)先搜索算法廣度優(yōu)先搜索算法。7.3.1 7.3.1 深度

45、優(yōu)先搜索算法深度優(yōu)先搜索算法 深度優(yōu)先搜索深度優(yōu)先搜索(Depth First Search-DFS)(Depth First Search-DFS)遍歷類似樹(shù)遍歷類似樹(shù)的先序遍歷，是樹(shù)的先序遍歷的推廣。的先序遍歷，是樹(shù)的先序遍歷的推廣。1 1 算法思想算法思想 設(shè)初始狀態(tài)時(shí)圖中的所有頂點(diǎn)未被訪問(wèn)，深度優(yōu)先搜索設(shè)初始狀態(tài)時(shí)圖中的所有頂點(diǎn)未被訪問(wèn)，深度優(yōu)先搜索從圖中某個(gè)初始頂點(diǎn)從圖中某個(gè)初始頂點(diǎn)v v出發(fā)出發(fā), ,首先訪問(wèn)初始頂點(diǎn)首先訪問(wèn)初始頂點(diǎn)v,v,然后選擇然后選擇一個(gè)與頂點(diǎn)一個(gè)與頂點(diǎn)v v相鄰且沒(méi)被訪問(wèn)過(guò)的頂點(diǎn)相鄰且沒(méi)被訪問(wèn)過(guò)的頂點(diǎn)w w為初始頂點(diǎn)為初始頂點(diǎn), ,再?gòu)脑購(gòu)膚 w出發(fā)進(jìn)行深度

46、優(yōu)先搜索出發(fā)進(jìn)行深度優(yōu)先搜索, ,直到圖中與當(dāng)前頂點(diǎn)直到圖中與當(dāng)前頂點(diǎn)v v鄰接的所有鄰接的所有頂點(diǎn)都被訪問(wèn)過(guò)為止。顯然頂點(diǎn)都被訪問(wèn)過(guò)為止。顯然, ,這個(gè)遍歷過(guò)程是個(gè)遞歸過(guò)程。這個(gè)遍歷過(guò)程是個(gè)遞歸過(guò)程。 無(wú)向圖深度優(yōu)先搜索遍歷無(wú)向圖深度優(yōu)先搜索遍歷(a) 無(wú)向圖無(wú)向圖Gv1v2v3v4v5(b) G的鄰接鏈表的鄰接鏈表01234MAX_VEX-1v1 v2v3 v4 v5 21 20 01 4 3 下圖是無(wú)向圖的深度優(yōu)先搜索遍歷示例下圖是無(wú)向圖的深度優(yōu)先搜索遍歷示例( (紅色箭頭紅色箭頭) )。某一種某一種DFSDFS次序是：次序是：v v1 1 v v3 3 v v2 2 v v4 4 v

47、v5 5例：例：求圖求圖G G以以V V0 0起始點(diǎn)的的深度優(yōu)先序列。起始點(diǎn)的的深度優(yōu)先序列。 V0 V7 V6 V5 V4 V3 V2 V1,V6V0V1V3V2V7V5 V4V0 ,V1 ,V4 ,V7 ,V3 ,V2 ,V5 ,V6 V0 ,V1,V3,V7,V4,V2,V5圖圖GV6由于沒(méi)有規(guī)定由于沒(méi)有規(guī)定訪問(wèn)鄰接點(diǎn)的順序，訪問(wèn)鄰接點(diǎn)的順序，DFS序列不是唯一的序列不是唯一的DFSDFS遍歷類似遍歷類似樹(shù)的先序遍歷樹(shù)的先序遍歷如果將圖的頂點(diǎn)的未被訪問(wèn)鄰接點(diǎn)看作樹(shù)結(jié)點(diǎn)的孩子，如果將圖的頂點(diǎn)的未被訪問(wèn)鄰接點(diǎn)看作樹(shù)結(jié)點(diǎn)的孩子，圖的深度優(yōu)先遍歷與樹(shù)的先根遍歷是圖的深度優(yōu)先遍歷與樹(shù)的先根遍歷是類

48、似類似的。的。 圖的深度優(yōu)先遍歷圖的深度優(yōu)先遍歷 從圖中某頂點(diǎn)從圖中某頂點(diǎn)v v出發(fā)：出發(fā)： （1 1）訪問(wèn)頂點(diǎn)）訪問(wèn)頂點(diǎn)v v； （2 2）依次從）依次從v v的未被訪問(wèn)的鄰接點(diǎn)的未被訪問(wèn)的鄰接點(diǎn) 出發(fā)，對(duì)圖進(jìn)行深度優(yōu)先遍歷。出發(fā)，對(duì)圖進(jìn)行深度優(yōu)先遍歷。樹(shù)的先根遍歷樹(shù)的先根遍歷 若樹(shù)非空若樹(shù)非空 （1 1）訪問(wèn)根結(jié)點(diǎn)；）訪問(wèn)根結(jié)點(diǎn)； （2 2）依次先根遍歷各棵子樹(shù)。）依次先根遍歷各棵子樹(shù)。比較比較2 2 算法實(shí)現(xiàn)算法實(shí)現(xiàn) 由算法思想知，這是一個(gè)遞歸過(guò)程。由算法思想知，這是一個(gè)遞歸過(guò)程。在遍歷過(guò)程中便于在遍歷過(guò)程中便于區(qū)分頂點(diǎn)是否已被訪問(wèn)，設(shè)置訪問(wèn)標(biāo)志數(shù)區(qū)分頂點(diǎn)是否已被訪問(wèn)，設(shè)置訪問(wèn)標(biāo)志數(shù)Vi

49、sited0Visited0n-1 n-1 (n(n為頂點(diǎn)數(shù)為頂點(diǎn)數(shù)) )，其初值為，其初值為0 0，一旦訪問(wèn)了頂點(diǎn)，一旦訪問(wèn)了頂點(diǎn)v vi i后，使后，使VisitedVisitedi i 為為1 1。void DFS(Graph G, int v) /算法7.4 /從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通圖 G visitedv = TRUE; VisitFunc(v); for(w=FirstAdjVex(G, v);w=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); /對(duì)v的尚未訪問(wèn)的鄰接頂點(diǎn)w，遞歸調(diào)用DFS /DFSF F F F F F

50、 F F F0 1 2 3 4 5 6 7 8T T T T T T T T Tach dfke bg訪問(wèn)標(biāo)志訪問(wèn)標(biāo)志: :訪問(wèn)次序訪問(wèn)次序: :例如例如: :abchdekfg812345670achkfedbg3 3 算法分析算法分析遍歷時(shí)，對(duì)圖的每個(gè)頂點(diǎn)至多調(diào)用一次遍歷時(shí)，對(duì)圖的每個(gè)頂點(diǎn)至多調(diào)用一次DFSDFS函數(shù)，因?yàn)橐坏┠硞€(gè)頂點(diǎn)被標(biāo)志成為已被訪問(wèn)，函數(shù)，因?yàn)橐坏┠硞€(gè)頂點(diǎn)被標(biāo)志成為已被訪問(wèn)，就不再?gòu)乃霭l(fā)進(jìn)行搜索。遍歷圖的過(guò)程實(shí)質(zhì)上就不再?gòu)乃霭l(fā)進(jìn)行搜索。遍歷圖的過(guò)程實(shí)質(zhì)上就是就是對(duì)每個(gè)頂點(diǎn)查找鄰接頂點(diǎn)的過(guò)程對(duì)每個(gè)頂點(diǎn)查找鄰接頂點(diǎn)的過(guò)程，其耗費(fèi)的，其耗費(fèi)的時(shí)間取決于所采用的存儲(chǔ)結(jié)構(gòu)。時(shí)

51、間取決于所采用的存儲(chǔ)結(jié)構(gòu)。當(dāng)用二維數(shù)組表示鄰接矩陣作為圖的存儲(chǔ)結(jié)當(dāng)用二維數(shù)組表示鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為構(gòu)時(shí)，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為O(nO(n2 2) .) .當(dāng)以鄰接表作圖的存儲(chǔ)結(jié)構(gòu)時(shí)，找鄰接點(diǎn)所當(dāng)以鄰接表作圖的存儲(chǔ)結(jié)構(gòu)時(shí)，找鄰接點(diǎn)所需時(shí)間為需時(shí)間為O(e)O(e)，e e為無(wú)向圖中邊的數(shù)或有向圖中弧為無(wú)向圖中邊的數(shù)或有向圖中弧的數(shù)，此時(shí)的時(shí)間復(fù)雜度為的數(shù)，此時(shí)的時(shí)間復(fù)雜度為O(O(n+en+e) ) 。7.3.2 7.3.2 廣度優(yōu)先搜索算法廣度優(yōu)先搜索算法 廣度優(yōu)先搜索廣度優(yōu)先搜索(Breadth First Search-BFS)(Bread

52、th First Search-BFS)遍歷類遍歷類似樹(shù)的按層次遍歷的過(guò)程。似樹(shù)的按層次遍歷的過(guò)程。1 1 算法思想算法思想 廣度優(yōu)先搜索遍歷的過(guò)程是：首先訪問(wèn)初始點(diǎn)廣度優(yōu)先搜索遍歷的過(guò)程是：首先訪問(wèn)初始點(diǎn)v vi i, ,接著接著訪問(wèn)訪問(wèn)v vi i的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)v vi1i1,v,vi2i2,v vitit, ,然后再按然后再按照照v vi1i1,v,vi2i2,v vitit的次序的次序, ,訪問(wèn)每一個(gè)頂點(diǎn)的所有未被訪問(wèn)過(guò)訪問(wèn)每一個(gè)頂點(diǎn)的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)的鄰接點(diǎn), ,依次類推依次類推, ,直到圖中所有和初始點(diǎn)直到圖中所有和初始點(diǎn)v vi i有路徑相

53、通有路徑相通的頂點(diǎn)都被訪問(wèn)過(guò)為止。的頂點(diǎn)都被訪問(wèn)過(guò)為止。下圖是有向圖的廣度優(yōu)先搜索遍歷示例下圖是有向圖的廣度優(yōu)先搜索遍歷示例(紅色箭頭紅色箭頭)。上述圖的上述圖的BFS次序是次序是：v1 v2 v4 v3 v5(b) G的正鄰接鏈表的正鄰接鏈表13 014 2 3 01234MAX_VEX-1v1 2 v2 0 v3 3v4 1 v5 1 有向圖廣度優(yōu)先搜索遍歷有向圖廣度優(yōu)先搜索遍歷(a) 有向圖有向圖Gv1v2v3v4v5例：例：求圖求圖G G以以V V0 0起始點(diǎn)的的廣度優(yōu)先序列。起始點(diǎn)的的廣度優(yōu)先序列。 V0 V7 V6 V5 V4 V3 V2 V1,V7V0V1V3V2V7V5 V4V

54、0 ,V2 ,V1 ,V5 ,V6 ,V3 ,V4 ,V7 V0 ,V1,V2,V3,V4,V5,V6圖圖GV6由于沒(méi)有規(guī)定由于沒(méi)有規(guī)定訪問(wèn)鄰接點(diǎn)的順序，訪問(wèn)鄰接點(diǎn)的順序，BFS序列不是唯一的序列不是唯一的BFSBFS遍歷類似遍歷類似樹(shù)的按層次遍歷樹(shù)的按層次遍歷2 2 算法實(shí)現(xiàn)算法實(shí)現(xiàn) 為了標(biāo)記圖中頂點(diǎn)是否被訪問(wèn)過(guò)，同樣需要一個(gè)訪問(wèn)為了標(biāo)記圖中頂點(diǎn)是否被訪問(wèn)過(guò)，同樣需要一個(gè)訪問(wèn)標(biāo)記數(shù)組；其次，為了依次訪問(wèn)與標(biāo)記數(shù)組；其次，為了依次訪問(wèn)與v vi i相鄰接的各個(gè)頂點(diǎn)，相鄰接的各個(gè)頂點(diǎn)，需要附加一個(gè)隊(duì)列來(lái)保存訪問(wèn)需要附加一個(gè)隊(duì)列來(lái)保存訪問(wèn)v vi i的相鄰接的頂點(diǎn)。的相鄰接的頂點(diǎn)。typedef

55、emnu FALSE , TRUE BOOLEAN ;BOOLEAN VisitedMAX_VEX ;typedef struct Queue int elemMAX_VEX ;int front , rear ;Queue ; /* 定義一個(gè)隊(duì)列保存將要訪問(wèn)頂點(diǎn) */void BFSTraverse(Graph G, Status (*Visit)(int v) /算法算法7.6 for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化訪問(wèn)標(biāo)志 InitQueue(Q); / 置空的輔助隊(duì)列Q for ( v=0; v=0 ; w=NextAdjVex(

56、G,u,w) if ( ! visitedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); /if /while /if / BFSTraverse 用廣度優(yōu)先搜索算法遍歷圖與深度優(yōu)先搜索用廣度優(yōu)先搜索算法遍歷圖與深度優(yōu)先搜索算法遍歷圖的算法遍歷圖的唯一區(qū)別是鄰接點(diǎn)搜索次序不同唯一區(qū)別是鄰接點(diǎn)搜索次序不同，因此，當(dāng)以鄰接表作圖的存儲(chǔ)結(jié)構(gòu)時(shí)廣度優(yōu)先搜因此，當(dāng)以鄰接表作圖的存儲(chǔ)結(jié)構(gòu)時(shí)廣度優(yōu)先搜索算法遍歷圖的總時(shí)間復(fù)雜度也為索算法遍歷圖的總時(shí)間復(fù)雜度也為O(O(n+en+e) )。 圖的遍歷可以系統(tǒng)地訪問(wèn)圖中的每個(gè)頂點(diǎn)，圖的遍歷可以系統(tǒng)地訪問(wèn)圖中的每個(gè)頂點(diǎn)，因此，

57、圖的遍歷算法是圖的最基本、最重要的算因此，圖的遍歷算法是圖的最基本、最重要的算法，許多有關(guān)圖的操作都是在圖的遍歷基礎(chǔ)之上法，許多有關(guān)圖的操作都是在圖的遍歷基礎(chǔ)之上加以變化來(lái)實(shí)現(xiàn)的。加以變化來(lái)實(shí)現(xiàn)的。7.4 7.4 圖的連通性問(wèn)題圖的連通性問(wèn)題7.4.1 7.4.1 無(wú)向圖的連通分量與生成樹(shù)無(wú)向圖的連通分量與生成樹(shù) 對(duì)于無(wú)向圖，對(duì)其進(jìn)行遍歷時(shí)：對(duì)于無(wú)向圖，對(duì)其進(jìn)行遍歷時(shí)： 若是若是連通圖連通圖：僅需從圖中僅需從圖中任一頂點(diǎn)出發(fā)任一頂點(diǎn)出發(fā)，就，就能訪問(wèn)圖中的所有頂點(diǎn)；能訪問(wèn)圖中的所有頂點(diǎn)； 若是若是非連通圖非連通圖：需從圖中需從圖中多個(gè)頂點(diǎn)出發(fā)多個(gè)頂點(diǎn)出發(fā)。每。每次從一個(gè)新頂點(diǎn)出發(fā)所訪問(wèn)的頂點(diǎn)集

58、序列次從一個(gè)新頂點(diǎn)出發(fā)所訪問(wèn)的頂點(diǎn)集序列恰好恰好是是各個(gè)連通分量的頂點(diǎn)集。各個(gè)連通分量的頂點(diǎn)集。(a) 無(wú)向圖無(wú)向圖Gv1v2v3v4v5(b) G的鄰接鏈表的鄰接鏈表01234MAX_VEX-1v1 v2v3 v4 v5 21 20 01 4 3 無(wú)向圖及深度優(yōu)先生成森林無(wú)向圖及深度優(yōu)先生成森林(c) 深度優(yōu)先生成森林深度優(yōu)先生成森林v1v2v3v4v5 如圖所示的無(wú)向圖是非連通圖，按圖中給定的鄰如圖所示的無(wú)向圖是非連通圖，按圖中給定的鄰接表進(jìn)行深度優(yōu)先搜索遍歷，接表進(jìn)行深度優(yōu)先搜索遍歷，2 2次調(diào)用次調(diào)用DFSDFS所得到的頂點(diǎn)所得到的頂點(diǎn)訪問(wèn)序列集是：訪問(wèn)序列集是： v1 ,v3 ,v2

59、 v1 ,v3 ,v2和和 v4 ,v5 v4 ,v5 若若G=(V,E)G=(V,E)是是無(wú)向連通圖無(wú)向連通圖， 頂點(diǎn)集和邊集分別是頂點(diǎn)集和邊集分別是V(G) V(G) ，E(G) E(G) 。若從。若從G G中任意點(diǎn)出發(fā)遍歷時(shí)，中任意點(diǎn)出發(fā)遍歷時(shí)， E(G)E(G)被被分成兩個(gè)互不相交的集合：分成兩個(gè)互不相交的集合：T(G) T(G) ：遍歷過(guò)程中：遍歷過(guò)程中所經(jīng)過(guò)的邊所經(jīng)過(guò)的邊的集合；的集合；B(G) B(G) ：遍歷過(guò)程中：遍歷過(guò)程中未經(jīng)過(guò)的邊未經(jīng)過(guò)的邊的集合；的集合； 顯然：顯然： E(G)=T(G)B(G) E(G)=T(G)B(G) ，T(G)B(G)=T(G)B(G)= 顯然，

60、圖顯然，圖G=(V, T(G)G=(V, T(G)是是G G的的極小連通子圖極小連通子圖，且，且GG是一棵樹(shù)。是一棵樹(shù)。GG稱為圖稱為圖G G的一棵的一棵生成樹(shù)生成樹(shù)。 從任意點(diǎn)出發(fā)按從任意點(diǎn)出發(fā)按DFSDFS算法得到生成樹(shù)算法得到生成樹(shù)GG稱為稱為深度深度優(yōu)先生成樹(shù)優(yōu)先生成樹(shù)；按；按BFSBFS算法得到的算法得到的GG稱為稱為廣度優(yōu)先生成廣度優(yōu)先生成樹(shù)樹(shù)。深度優(yōu)先遍歷序列：深度優(yōu)先遍歷序列：1,2,4,8,6,3,7,5廣度優(yōu)先遍歷序列：廣度優(yōu)先遍歷序列：1,2,3,4,5,6,7,8若若G=(V,E)G=(V,E)是是無(wú)向非連通圖無(wú)向非連通圖，對(duì)圖進(jìn)行遍歷時(shí)得到，對(duì)圖進(jìn)行遍歷時(shí)得到若干個(gè)連通分量的頂點(diǎn)集：若干個(gè)連通分量的頂點(diǎn)集：V V1 1(G) ,V(G) ,V2 2(G) ,(G) ,