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

1、7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)n圖的數(shù)組圖的數(shù)組( (鄰接矩陣鄰接矩陣) )存儲(chǔ)表示存儲(chǔ)表示n圖的鄰接表存儲(chǔ)表示圖的鄰接表存儲(chǔ)表示n有向圖的十字鏈表存儲(chǔ)表示有向圖的十字鏈表存儲(chǔ)表示n無向圖的鄰接多重表存儲(chǔ)表示無向圖的鄰接多重表存儲(chǔ)表示鄰接矩陣鄰接矩陣是用于描述圖中頂點(diǎn)之間關(guān)系是用于描述圖中頂點(diǎn)之間關(guān)系( (即弧或邊即弧或邊的權(quán)的權(quán)) )的矩陣。的矩陣。 鄰接表鄰接表類似樹的孩子鏈表。即對(duì)圖中的每個(gè)頂點(diǎn)類似樹的孩子鏈表。即對(duì)圖中的每個(gè)頂點(diǎn)vivi建立一個(gè)單鏈表，表中結(jié)點(diǎn)表示依附于該頂點(diǎn)建立一個(gè)單鏈表，表中結(jié)點(diǎn)表示依附于該頂點(diǎn)vivi的的邊或弧。邊或弧。鄰接點(diǎn)域鄰接點(diǎn)域鏈域鏈域數(shù)據(jù)域數(shù)據(jù)

2、域數(shù)據(jù)域數(shù)據(jù)域鏈域鏈域表結(jié)點(diǎn)表結(jié)點(diǎn)表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)v1v3v2v4例：例： 4 3 2 1211134423.3.有向圖的十字鏈表存儲(chǔ)表示有向圖的十字鏈表存儲(chǔ)表示兩種結(jié)點(diǎn)結(jié)構(gòu)：兩種結(jié)點(diǎn)結(jié)構(gòu)：尾域尾域tailvextailvex頭域頭域headvexheadvex鏈域鏈域hlinkhlink鏈域鏈域tlinktlink信息域信息域infoinfo數(shù)據(jù)域數(shù)據(jù)域datadata鏈域鏈域firstinfirstin鏈域鏈域firstoutfirstout頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)弧結(jié)點(diǎn)弧結(jié)點(diǎn)v v1 1v v2 2v v3 3v v4 4 0 1 2 3 10/20v3v1 v4v2 /03/13/2302/3

3、2例：例：datadatafirstinfirstinfirstoutfirstouttailvexheadvex hlinktlink/標(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.無向圖的鄰接多重表存儲(chǔ)表示無向圖的鄰接多重表存儲(chǔ)表示邊結(jié)點(diǎn)邊結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)1 3 4 2 例：例：1234121324第第7 7章章 圖圖7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)7.3 7.3 圖的遍歷圖的遍歷7.4 7.4 圖的連通性問題圖的連通性問題7.5 7.5 有向無環(huán)圖及其應(yīng)用

4、有向無環(huán)圖及其應(yīng)用7.6 7.6 最短路徑最短路徑7.3 7.3 圖的遍歷圖的遍歷 從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，且使從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪問一次。這一過程就叫做每一個(gè)頂點(diǎn)僅被訪問一次。這一過程就叫做圖的圖的遍歷遍歷。 通常有兩條遍歷圖的路徑：通常有兩條遍歷圖的路徑：n深度優(yōu)先搜索深度優(yōu)先搜索n廣度優(yōu)先搜索廣度優(yōu)先搜索1.1.深度優(yōu)先搜索深度優(yōu)先搜索(dfs)(dfs)基本思想：基本思想： 從圖中某頂點(diǎn)從圖中某頂點(diǎn)v v0 0出發(fā)，訪問此頂點(diǎn)，然后依次出發(fā)，訪問此頂點(diǎn)，然后依次從從v v0 0的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜

5、索深度優(yōu)先搜索遍遍歷圖，直至圖中所有和歷圖，直至圖中所有和v v0 0有路徑相通的頂點(diǎn)都被訪有路徑相通的頂點(diǎn)都被訪問到；問到； 若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)；個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)； 重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。為止。 例：例：從頂點(diǎn)從頂點(diǎn)v1v1出發(fā)，出發(fā)，dfsdfs下圖。下圖。頂點(diǎn)訪問序列為：頂點(diǎn)訪問序列為：v v1,v2,v4,v8,v5,v3,v6,v71,v2,v4,v8,v5,v3,v6,v7v1v1v6v6v2v2v5v5v3v3v8v8v

6、4v4v7v7圖的圖的dfs算法一般描述算法一般描述intint visitedmaxvex; visitedmaxvex; /訪問標(biāo)志數(shù)組訪問標(biāo)志數(shù)組void dfsgraph(graphvoid dfsgraph(graph g, visit() g, visit() /對(duì)圖對(duì)圖g g作深度優(yōu)先遍歷作深度優(yōu)先遍歷 for( v=0; vg.vexnumfor( v=0; vg.vexnum; +v ) visitedv=false; +v ) visitedv=false; /訪問標(biāo)志數(shù)組初始化訪問標(biāo)志數(shù)組初始化 for( v=0; vg.vexnumfor( v=0; v=0; w=ne

7、xtadjvex(g,v,wfor(w=firstadjvex(g,v); w=0; w=nextadjvex(g,v,w) if (!visitedw) dfs(g,w if (!visitedw) dfs(g,w); ); /對(duì)對(duì)v v的尚未訪問的鄰接頂點(diǎn)的尚未訪問的鄰接頂點(diǎn)w w遞歸調(diào)用遞歸調(diào)用dfsdfs 用鄰接表實(shí)現(xiàn)圖的深度優(yōu)先搜索用鄰接表實(shí)現(xiàn)圖的深度優(yōu)先搜索v1v1v6v6v2v2v5v5v3v3v8v8v4v4v7v7v9v9v10v1012345678 2 8 2 8 3 7 3 6 4 5 2 3 2 3 1 6 7 1 4 5910 9 / 10 /分析：分析： 在遍歷圖時(shí)

8、，對(duì)圖中每個(gè)頂點(diǎn)至多調(diào)用一次在遍歷圖時(shí)，對(duì)圖中每個(gè)頂點(diǎn)至多調(diào)用一次dfsdfs函數(shù)，因?yàn)橐坏┠硞€(gè)頂點(diǎn)被標(biāo)志成已被訪問，函數(shù)，因?yàn)橐坏┠硞€(gè)頂點(diǎn)被標(biāo)志成已被訪問，就不再從它出發(fā)進(jìn)行搜索。就不再從它出發(fā)進(jìn)行搜索。 因此，遍歷圖的過程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查因此，遍歷圖的過程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過程。其耗費(fèi)的時(shí)間則取決于所采找其鄰接點(diǎn)的過程。其耗費(fèi)的時(shí)間則取決于所采用的存儲(chǔ)結(jié)構(gòu)。用的存儲(chǔ)結(jié)構(gòu)。 2.2.廣度優(yōu)先搜索廣度優(yōu)先搜索(bfs)(bfs)基本思想：基本思想： 從圖中某個(gè)頂點(diǎn)從圖中某個(gè)頂點(diǎn)v v0 0出發(fā)，并在訪問此頂點(diǎn)后依出發(fā)，并在訪問此頂點(diǎn)后依次訪問次訪問v v0 0的所有未被訪問過

9、的鄰接點(diǎn)，之后按這些的所有未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有和至圖中所有和v v0 0有路徑相通的頂點(diǎn)都被訪問到；有路徑相通的頂點(diǎn)都被訪問到； 若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)；個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)； 重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。為止。 例：例：從頂點(diǎn)從頂點(diǎn)v v1 1出發(fā)，出發(fā)，bfsbfs下圖。下圖。頂點(diǎn)訪問序列為：頂點(diǎn)訪問序列為：v v1 1,v,v2 2,v

10、,v3 3,v,v4 4,v,v5 5,v,v6 6,v,v7 7,v,v8 8v v1 1v v6 6v v2 2v v5 5v v3 3v v8 8v v4 4v v7 7用鄰接表實(shí)現(xiàn)圖的廣度優(yōu)先搜索用鄰接表實(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 5v v1 1v v6 6v v2 2v v5 5v v3 3v v8 8v v4 4v v7 7bfsbfs非遞歸非遞歸算法算法void bfstraverse(graph g, status (void bfstraverse(graph g, status (* *v

11、isit)(intvisit)(int v) v)/使用輔助隊(duì)列使用輔助隊(duì)列q q和訪問標(biāo)志數(shù)組和訪問標(biāo)志數(shù)組visitedv visitedv for (v=0; vg.vexnum for (v=0; vg.vexnum; +v) visitedv = false; +v) visitedv = false; initqueue(q initqueue(q); ); / / 置空的輔助隊(duì)列置空的輔助隊(duì)列q q for ( v=0; vg.vexnum for ( v=0; v=0;w=nextadjvex(g,u,wfor (w=firstadjvex(g,u);w=0;w=nextadj

12、vex(g,u,w) )） if ( ! visitedwif ( ! visitedw) ) /w/w為為u u的尚未訪問的鄰接頂點(diǎn)的尚未訪問的鄰接頂點(diǎn) visitedw = true; visit(wvisitedw = true; visit(w);); enqueue(q enqueue(q, w);, w); /if /if /while /while if if / bfstraverse / bfstraverse分析：分析： 每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列。遍歷圖的過程實(shí)每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列。遍歷圖的過程實(shí)質(zhì)上是通過邊或弧找鄰接點(diǎn)的過程，因此廣度優(yōu)質(zhì)上是通過邊或弧找鄰接點(diǎn)的過程，因此

13、廣度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度和深度優(yōu)先搜索遍歷先搜索遍歷圖的時(shí)間復(fù)雜度和深度優(yōu)先搜索遍歷相同，兩者不同之處僅僅在于對(duì)頂點(diǎn)訪問的順序相同，兩者不同之處僅僅在于對(duì)頂點(diǎn)訪問的順序不同。不同。 第第7 7章章 圖圖7.1 7.1 圖的定義和術(shù)語圖的定義和術(shù)語7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)7.3 7.3 圖的遍歷圖的遍歷7.4 7.4 圖的連通性問題圖的連通性問題7.5 7.5 有向無環(huán)圖及其應(yīng)用有向無環(huán)圖及其應(yīng)用7.6 7.6 最短路徑最短路徑7.4 7.4 圖的連通性問題圖的連通性問題1 1）無向圖的）無向圖的連通分量和連通分量和生成樹生成樹2 2）最小生成樹）最小生成樹3 3）普里姆算

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

15、圖時(shí)，必定將e(g)e(g)分成兩個(gè)分成兩個(gè)集合集合t(g)t(g)和和b(g)b(g)，其中，其中t(g)t(g)是遍歷過程中歷經(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)先生成樹。例：求下圖的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。例：求

16、下圖的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。v v1 1v v6 6v v2 2v v5 5v v3 3v v8 8v v4 4v v7 7 對(duì)非連通圖，每個(gè)連通分量中的頂點(diǎn)集和遍對(duì)非連通圖，每個(gè)連通分量中的頂點(diǎn)集和遍歷時(shí)走過的邊一起構(gòu)成若干棵生成樹，這些連通歷時(shí)走過的邊一起構(gòu)成若干棵生成樹，這些連通分量的生成樹組成非連通圖的分量的生成樹組成非連通圖的生成森林生成森林。例：例：生成非連通圖的深度優(yōu)先生成森林的算法生成非連通圖的深度優(yōu)先生成森林的算法void dfsforestvoid dfsforest (graph g (graph g，cstreecstree &t) &t) /

17、建立無向圖建立無向圖g g的深度優(yōu)先生成森林的的深度優(yōu)先生成森林的( (左左) )孩子孩子( (右右) )兄弟鏈表兄弟鏈表t t。 t=nullt=null； for( v=0for( v=0； vg.vexnumvg.vexnum； +v) visitedv+v) visitedv=false=false； for( v=0for( v=0；vg.vexnumvnextsiblingnextsibling = p ; = p ; /是其它生成樹的根是其它生成樹的根( (前一棵的根的前一棵的根的“兄弟兄弟”) ) q = p; q = p; /q/q指示當(dāng)前生成樹的根指示當(dāng)前生成樹的根 dfs

18、tree(g,v,pdfstree(g,v,p); ); /建立以建立以p p為根的生成樹為根的生成樹 /dfsforest/dfsforestvoid dfstreevoid dfstree (graph g (graph g，intint v v，cstreecstree &t) &t) /從第從第v v個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖q q，建立以，建立以t t為根的生成樹。為根的生成樹。 visitedvvisitedv=true=true； first=truefirst=true； for(w=fisrtadjvex(g,v); w=0; w=nextadjvex(gfor(w=fisrtadjvex(g,v); w=0; w=nextadjvex(g, v, w), v, w) if(!visitedw if(!visitedw) ) p=(cstree)malloc(sizeof(csnode p=(cstree)malloc(sizeof(csnode); ); /分配孩子結(jié)點(diǎn)分配孩子結(jié)點(diǎn) * *p=getvex(g,wp=getvex(g,w) )，nullnull，nullnull； if(firstif(first) ) /w/w是是v v的第一個(gè)未被訪問的鄰接