數(shù)據(jù)結(jié)構(gòu)圖的遍歷與連通性參考用PPT課件

1、鄰接矩陣鄰接矩陣是用于描述圖中頂點(diǎn)之間關(guān)系是用于描述圖中頂點(diǎn)之間關(guān)系( (即弧或即弧或邊的權(quán)邊的權(quán)) )的矩陣。的矩陣。 鄰接表鄰接表類似樹的孩子鏈表。即對(duì)圖中的每個(gè)頂類似樹的孩子鏈表。即對(duì)圖中的每個(gè)頂點(diǎn)點(diǎn)vivi建立一個(gè)單鏈表，表中結(jié)點(diǎn)表示依附于該建立一個(gè)單鏈表，表中結(jié)點(diǎn)表示依附于該頂點(diǎn)頂點(diǎn)vivi的邊或弧。的邊或弧。鄰接點(diǎn)域鄰接點(diǎn)域鏈域鏈域數(shù)據(jù)域數(shù)據(jù)域數(shù)據(jù)域數(shù)據(jù)域鏈域鏈域表結(jié)點(diǎn)表頭結(jié)點(diǎn)第1頁(yè)/共30頁(yè)V1V3V2V4例： 4 3 2 121113442第2頁(yè)/共30頁(yè)3.3.有向圖的十字鏈表存儲(chǔ)表示有向圖的十字鏈表存儲(chǔ)表示兩種結(jié)點(diǎn)結(jié)構(gòu)：尾域尾域tailvextailvex頭域頭域headv

2、exheadvex鏈域鏈域hlinkhlink鏈域鏈域tlinktlink信息域信息域infoinfo數(shù)據(jù)域數(shù)據(jù)域datadata鏈域鏈域firstinfirstin鏈域鏈域firstoutfirstout頂點(diǎn)結(jié)點(diǎn)弧結(jié)點(diǎn)第3頁(yè)/共30頁(yè)v1v2v3v4 0 1 2 3 10/20v3v1 v4v2 /03/13/2302/32例：datadatafirstinfirstinfirstoutfirstouttailvexheadvex hlinktlink/第4頁(yè)/共30頁(yè)標(biāo)志域標(biāo)志域邊頂點(diǎn)邊頂點(diǎn)i i邊頂點(diǎn)邊頂點(diǎn)j j鏈域鏈域i i 鏈域鏈域j j 信息域信息域數(shù)據(jù)域數(shù)據(jù)域邊鏈域邊鏈域4.4.

3、無(wú)向圖的鄰接多重表存儲(chǔ)表示無(wú)向圖的鄰接多重表存儲(chǔ)表示邊結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)第5頁(yè)/共30頁(yè)1 3 4 2 例：1234121324第6頁(yè)/共30頁(yè)第7章 圖7.1 圖的定義和術(shù)語(yǔ)7.2 圖的存儲(chǔ)結(jié)構(gòu)7.3 圖的遍歷7.4 圖的連通性問(wèn)題7.5 有向無(wú)環(huán)圖及其應(yīng)用7.6 最短路徑第7頁(yè)/共30頁(yè)7.3 7.3 圖的遍歷圖的遍歷 從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪問(wèn)一次。這一過(guò)程就叫且使每一個(gè)頂點(diǎn)僅被訪問(wèn)一次。這一過(guò)程就叫做做圖的遍歷圖的遍歷。 通常有兩條遍歷圖的路徑：通常有兩條遍歷圖的路徑：n深度優(yōu)先搜索深度優(yōu)先搜索n廣度優(yōu)先搜索廣度優(yōu)先搜索第8

4、頁(yè)/共30頁(yè)1.1.深度優(yōu)先搜索深度優(yōu)先搜索(DFS)(DFS)基本思想： 從圖中某頂點(diǎn)V0出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從V0的各個(gè)未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問(wèn)到； 若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)； 重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。第9頁(yè)/共30頁(yè) 例：從頂點(diǎn)v1出發(fā)，DFS下圖。頂點(diǎn)訪問(wèn)序列為：v1,v2,v4,v8,v5,v3,v6,v7v1v6v2v5v3v8v4v7第10頁(yè)/共30頁(yè)圖的DFS算法一般描述int visitedMAXVEX; /訪問(wèn)標(biāo)志數(shù)組void DFSgraph(G

5、raph G, Visit() /對(duì)圖G作深度優(yōu)先遍歷 for( v=0; vG.vexnum; +v ) visitedv=FALSE; /訪問(wèn)標(biāo)志數(shù)組初始化 for( v=0; v=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G,w); /對(duì)v的尚未訪問(wèn)的鄰接頂點(diǎn)w遞歸調(diào)用DFS 第12頁(yè)/共30頁(yè)用鄰接表實(shí)現(xiàn)圖的深度優(yōu)先搜索v1v6v2v5v3v8v4v7v9v1012345678 2 8 2 8 3 7 3 6 4 5 2 3 2 3 1 6 7 1 4 5910 9 / 10 /第13頁(yè)/共30頁(yè)分析：分析： 在遍歷圖時(shí)，對(duì)圖中每個(gè)頂點(diǎn)至多調(diào)用

6、一在遍歷圖時(shí)，對(duì)圖中每個(gè)頂點(diǎn)至多調(diào)用一次次DFSDFS函數(shù)，因?yàn)橐坏┠硞€(gè)頂點(diǎn)被標(biāo)志成已被函數(shù)，因?yàn)橐坏┠硞€(gè)頂點(diǎn)被標(biāo)志成已被訪問(wèn)，就不再?gòu)乃霭l(fā)進(jìn)行搜索。訪問(wèn)，就不再?gòu)乃霭l(fā)進(jìn)行搜索。 因此，遍歷圖的過(guò)程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)因此，遍歷圖的過(guò)程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過(guò)程。其耗費(fèi)的時(shí)間則取決于查找其鄰接點(diǎn)的過(guò)程。其耗費(fèi)的時(shí)間則取決于所采用的存儲(chǔ)結(jié)構(gòu)。所采用的存儲(chǔ)結(jié)構(gòu)。 第14頁(yè)/共30頁(yè)2.2.廣度優(yōu)先搜索廣度優(yōu)先搜索(BFS)(BFS)基本思想： 從圖中某個(gè)頂點(diǎn)V0出發(fā)，并在訪問(wèn)此頂點(diǎn)后依次訪問(wèn)V0的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問(wèn)的先后次序依次訪問(wèn)它們的鄰接點(diǎn)，直至圖中所有和

7、V0有路徑相通的頂點(diǎn)都被訪問(wèn)到； 若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)； 重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。第15頁(yè)/共30頁(yè) 例：從頂點(diǎn)v1出發(fā)，BFS下圖。頂點(diǎn)訪問(wèn)序列為：v1,v2,v3,v4,v5,v6,v7,v8v1v6v2v5v3v8v4v7第16頁(yè)/共30頁(yè)用鄰接表實(shí)現(xiàn)圖的廣度優(yōu)先搜索12345678 2 8 2 8 3 7 3 6 4 5 2 3 2 3 1 6 7 1 4 5v1v6v2v5v3v8v4v7第17頁(yè)/共30頁(yè)B BFSFS非遞歸非遞歸算法算法void BFSTraverse(Graph G, Status (void

8、BFSTraverse(Graph G, Status (* *Visit)(int Visit)(int v)v)/使用輔助隊(duì)列使用輔助隊(duì)列Q Q和訪問(wèn)標(biāo)志數(shù)組和訪問(wèn)標(biāo)志數(shù)組visitedv visitedv for (v=0; vG.vexnum; +v) visitedv = for (v=0; vG.vexnum; +v) visitedv = FALSE;FALSE; InitQueue(Q); InitQueue(Q); / / 置空的輔助隊(duì)列置空的輔助隊(duì)列Q Q for ( v=0; vG.vexnum; +v ) for ( v=0; v=0;w=NextAdjVex(G,u,

9、w)(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)） if ( ! visitedw) if ( ! visitedw) /w/w為為u u的尚未訪問(wèn)的鄰接頂點(diǎn)的尚未訪問(wèn)的鄰接頂點(diǎn) visitedw = TRUE; Visit(w);visitedw = TRUE; Visit(w); EnQueue(Q, w); EnQueue(Q, w); /if /if /while /while if if / BFSTraverse / BFSTraverse第19頁(yè)/共30頁(yè)分析：分析： 每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列。遍歷圖的過(guò)程每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列。遍歷圖的過(guò)

10、程實(shí)質(zhì)上是通過(guò)邊或弧找鄰接點(diǎn)的過(guò)程，因此廣實(shí)質(zhì)上是通過(guò)邊或弧找鄰接點(diǎn)的過(guò)程，因此廣度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度和深度優(yōu)先搜度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度和深度優(yōu)先搜索遍歷相同，兩者不同之處僅僅在于對(duì)頂點(diǎn)訪索遍歷相同，兩者不同之處僅僅在于對(duì)頂點(diǎn)訪問(wèn)的順序不同。問(wèn)的順序不同。 第20頁(yè)/共30頁(yè)第7章 圖7.1 圖的定義和術(shù)語(yǔ)7.2 圖的存儲(chǔ)結(jié)構(gòu)7.3 圖的遍歷7.4 圖的連通性問(wèn)題7.5 有向無(wú)環(huán)圖及其應(yīng)用7.6 最短路徑第21頁(yè)/共30頁(yè)7.4 7.4 圖的連通性問(wèn)題圖的連通性問(wèn)題1 1）無(wú)向圖的無(wú)向圖的連通分量和連通分量和生成樹生成樹2 2）最小生成樹最小生成樹3 3）普里姆算法）普里姆算法4

11、 4）克魯斯卡爾算法）克魯斯卡爾算法第22頁(yè)/共30頁(yè)1.1.無(wú)向圖的無(wú)向圖的連通分量和連通分量和生成樹生成樹基本概念基本概念n連通分量的頂點(diǎn)集連通分量的頂點(diǎn)集：即從該連通分量的某一頂點(diǎn)出發(fā)進(jìn)行搜索所得到：即從該連通分量的某一頂點(diǎn)出發(fā)進(jìn)行搜索所得到的頂點(diǎn)訪問(wèn)序列；的頂點(diǎn)訪問(wèn)序列；n生成樹生成樹：某連通分量的極小連通子圖某連通分量的極小連通子圖；n生成森林生成森林：非連通圖的各個(gè)連通分量的極小連通子圖構(gòu)成的集合：非連通圖的各個(gè)連通分量的極小連通子圖構(gòu)成的集合。第23頁(yè)/共30頁(yè) 設(shè)設(shè)E(G)E(G)為連通子圖為連通子圖G G中所有邊的集合，則從中所有邊的集合，則從圖中任一頂點(diǎn)出發(fā)遍歷圖時(shí)，必定將

12、圖中任一頂點(diǎn)出發(fā)遍歷圖時(shí)，必定將E(G)E(G)分成分成兩個(gè)集合兩個(gè)集合T(G)T(G)和和B(G)B(G)，其中，其中T(G)T(G)是遍歷過(guò)程中是遍歷過(guò)程中歷經(jīng)的邊的集合。顯然，歷經(jīng)的邊的集合。顯然，T(G)T(G)和圖和圖G G中所有頂中所有頂點(diǎn)一起構(gòu)成連通圖點(diǎn)一起構(gòu)成連通圖G G的極小連通子圖，按照的極小連通子圖，按照7.17.1節(jié)的定義，它是連通圖的一棵生成樹，并且稱節(jié)的定義，它是連通圖的一棵生成樹，并且稱由深度優(yōu)先搜索得到的為由深度優(yōu)先搜索得到的為深度優(yōu)先生成樹深度優(yōu)先生成樹；由；由廣度優(yōu)先搜索得到的為廣度優(yōu)先搜索得到的為廣度優(yōu)先生成樹廣度優(yōu)先生成樹。第24頁(yè)/共30頁(yè)例：求下圖的

13、深度優(yōu)先生成樹和廣度優(yōu)先生成樹。v1v6v2v5v3v8v4v7第25頁(yè)/共30頁(yè) 對(duì)非連通圖，每個(gè)連通分量中的頂點(diǎn)集和對(duì)非連通圖，每個(gè)連通分量中的頂點(diǎn)集和遍歷時(shí)走過(guò)的邊一起構(gòu)成若干棵生成樹，這些遍歷時(shí)走過(guò)的邊一起構(gòu)成若干棵生成樹，這些連通分量的生成樹組成非連通圖的連通分量的生成樹組成非連通圖的生成森林生成森林。例：例：第26頁(yè)/共30頁(yè)生成非連通圖的深度優(yōu)先生成森林的算法生成非連通圖的深度優(yōu)先生成森林的算法void DFSForest (Graph G，CSTree &T) /建立無(wú)向圖G的深度優(yōu)先生成森林的(左)孩子(右)兄弟鏈表T。 T=NULL； for( v=0； vG.ve

14、xnum； +v) visitedv=FALSE； for( v=0；vnextsibling = p ; /是其它生成樹的根(前一棵的根的“兄弟”) q = p; /q指示當(dāng)前生成樹的根 DFSTree(G,v,p); /建立以p為根的生成樹 /DFSForest第27頁(yè)/共30頁(yè)void DFSTree (Graph Gvoid DFSTree (Graph G，int vint v，CSTree &T) CSTree &T) /從第從第v v個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖Q Q，建立以，建立以T T為根的生成樹。為根的生成樹。 visitedv=TRUE

15、visitedv=TRUE； first=TRUEfirst=TRUE； for(w=FisrtAdjVex(G,v); w=0; w=NextAdjVex(G, v, w)for(w=FisrtAdjVex(G,v); w=0; w=NextAdjVex(G, v, w) if(!visitedw) if(!visitedw) p=(CSTree)malloc(sizeof(CSNode); p=(CSTree)malloc(sizeof(CSNode); /分配孩子結(jié)分配孩子結(jié)點(diǎn)點(diǎn) * *p=GetVex(G,w)p=GetVex(G,w)，NULLNULL，NULLNULL； if(fi

16、rst) if(first) /w/w是是v v的第一個(gè)未被訪問(wèn)的鄰接頂點(diǎn)的第一個(gè)未被訪問(wèn)的鄰接頂點(diǎn) T Tlchild=plchild=p；first=FALSEfirst=FALSE；/是根的左孩子結(jié)是根的左孩子結(jié)點(diǎn)點(diǎn) else else /w/w是是v v的其它未被訪問(wèn)的鄰接頂點(diǎn)的其它未被訪問(wèn)的鄰接頂點(diǎn) q qnextsibling =pnextsibling =p；/是上一鄰接頂點(diǎn)的右兄弟是上一鄰接頂點(diǎn)的右兄弟結(jié)點(diǎn)結(jié)點(diǎn) q = p q = p； DFSTree(G, w, q)DFSTree(G, w, q)； /從第從第w w個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G G，建立子生，建立子生成樹成樹q q /if/if /DFSTree /DFSTree第28頁(yè)/共30頁(yè)1.1.理解并掌握?qǐng)D的深度優(yōu)先搜索和廣度優(yōu)先搜理解并掌握?qǐng)D的深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法及其性能分析；以及兩種遍歷索兩種遍歷算法及其性能分析；以及兩種遍歷所使用的輔助