第七章圖(2)圖的遍歷

《第七章圖(2)圖的遍歷》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、第7章圖（2）圖的遍歷主講：劉春學(xué)習(xí)目標(biāo)①掌握?qǐng)D的基本概念，包括圖、有向圖、無(wú)向圖、完全圖、子圖連通圖、度、入度、初度、簡(jiǎn)單回路和環(huán)等基本概念的定義。②重點(diǎn)掌握?qǐng)D的各種存儲(chǔ)結(jié)構(gòu)、包括鄰接矩陣和鄰接表等③重點(diǎn)掌握?qǐng)D的基本元素、包括創(chuàng)建圖、輸出圖、深度優(yōu)先遍歷、廣度優(yōu)先遍歷算法等④掌握?qǐng)D的其他運(yùn)算、包括最小生成樹(shù)、最短路徑、拓?fù)渑判蚝完P(guān)鍵路徑等算法⑤靈活運(yùn)用圖這種數(shù)據(jù)結(jié)構(gòu)解決一些綜合應(yīng)用問(wèn)題。7.3圖的遍歷圖的遍歷的定義從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問(wèn)一次的過(guò)程。1問(wèn)題：圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通

2、，在訪問(wèn)完某個(gè)頂點(diǎn)之后23可能會(huì)沿著某些邊又回到了曾經(jīng)訪問(wèn)過(guò)的頂點(diǎn)。為了避免重復(fù)訪問(wèn)，可設(shè)置一個(gè)標(biāo)志輔助數(shù)組456visited[]，它的初始狀態(tài)為0，在圖的遍歷過(guò)程7中，一旦某一個(gè)頂點(diǎn)i被訪問(wèn)，就立即讓visited[i]為1，防止它被多次訪問(wèn)。8根據(jù)搜索方法的不同，圖的遍歷有兩種：深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜素(WFS)。7.3圖的遍歷深度優(yōu)先搜索(Depp_thFirstSearch)主要思想：從圖中某個(gè)頂點(diǎn)V出發(fā)，訪問(wèn)此頂點(diǎn)，然后選擇一個(gè)0與V鄰接且未被訪問(wèn)的頂點(diǎn)W為初始頂點(diǎn),再?gòu)腤出發(fā)進(jìn)行深度優(yōu)0先搜索,直至圖中所有和V有路徑相通的頂點(diǎn)都被訪

3、問(wèn)到；0若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。深度優(yōu)先搜索是個(gè)遞歸的過(guò)程7.3圖的遍歷連通圖DFS的具體搜索過(guò)程：在訪問(wèn)圖中任意選某一起始頂點(diǎn)v后，由v出發(fā)，訪問(wèn)它的任一鄰接頂點(diǎn)w；再?gòu)膚出發(fā)，訪問(wèn)與w鄰接但還沒(méi)有訪問(wèn)過(guò)的頂點(diǎn)111w；然后再?gòu)膚出發(fā)，進(jìn)行類似的訪問(wèn)，…如此進(jìn)行下去，直至22到達(dá)所有的鄰接頂點(diǎn)都被訪問(wèn)過(guò)的頂點(diǎn)u為止。接著，退回一步，退到前一次剛訪問(wèn)過(guò)的頂點(diǎn)，看是否還有其它沒(méi)有被訪問(wèn)的鄰接頂點(diǎn)。如果有，則訪問(wèn)此頂點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類似的訪問(wèn)；如果沒(méi)有，

4、就再退回一步進(jìn)行搜索。重復(fù)上述過(guò)程，直到連通圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。7.3圖的遍歷深度優(yōu)先搜索(Depp_thFirstSearch)深度優(yōu)先搜索過(guò)程深度優(yōu)先生成樹(shù)7.3圖的遍歷分析：假設(shè)W、W和W均為V的鄰接點(diǎn)，SG、SG和SG123123分別為含頂點(diǎn)W、W和W的子圖。123V訪問(wèn)頂點(diǎn)V：for(W、W、W)123若該鄰接點(diǎn)W未被訪問(wèn)，iww1w23則從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。SGSGSG312結(jié)論：深度優(yōu)先搜索遍歷連通圖的過(guò)程類似于樹(shù)的先根遍歷7.3圖的遍歷Eg7-4對(duì)無(wú)向圖連通圖G1，寫出從頂點(diǎn)1出發(fā)的深度優(yōu)先搜索遍歷序列？1深度優(yōu)先搜索序列2

5、31,2,4,8,5,6,3,7561,2,5,8,4,7,3,6471,3,6,8,7,4,2,58無(wú)向圖G1結(jié)論：從某一個(gè)頂點(diǎn)出發(fā)的遍歷結(jié)果是不唯一的。7.3圖的遍歷voidDFSTraverse(GraphG,Status(*Visit)(intv)){//對(duì)連通圖G作深度優(yōu)先遍歷。VisitFunc=Visit;for(vfor(v0;=0;v

6、TraversevoidDFS((p,GraphG,intv)){{//從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通圖Gvisited[v]=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);//對(duì)v的尚未訪問(wèn)的鄰接頂點(diǎn)w//遞歸調(diào)用DFS}//DFS7.3圖的遍歷非連通圖的深度優(yōu)先遍歷①在每個(gè)連通分量或每個(gè)強(qiáng)連通分量中都選一個(gè)頂點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，最后將每個(gè)連通分量或每個(gè)強(qiáng)連通分量的遍歷結(jié)果合起來(lái)，則得到整個(gè)非連通圖的遍歷結(jié)果。②遍

7、歷算法實(shí)現(xiàn)與連通圖的只有一點(diǎn)不同，即對(duì)所有頂點(diǎn)進(jìn)行循環(huán)，反復(fù)調(diào)用連通圖的深度優(yōu)先搜索遍歷算法即可。7.3圖的遍歷Eg7-5對(duì)無(wú)向圖非連通圖G2，從頂點(diǎn)a開(kāi)始，進(jìn)行深度優(yōu)先遍歷。0a1bab2cg3d4ecdef5f6g7hhi8i012345678訪問(wèn)標(biāo)志:TFTFTFTFFTFTTFTFFT訪問(wèn)次序:achdifebg7.3圖的遍歷voidDFSTraverse(GraphG,Status(*Visit)(intv)){//對(duì)非連通圖G作深度優(yōu)先遍歷。VisitFunc=Visit;for(vfor(v0;=0;v

8、v);++v)visited[v]=FALSE;//