第七章圖(2)圖的遍歷

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

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

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

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

4、就再退回一步進(jìn)行搜索。重復(fù)上述過程，直到連通圖中所有頂點(diǎn)都被訪問過為止。7.3圖的遍歷深度優(yōu)先搜索(Depp_thFirstSearch)深度優(yōu)先搜索過程深度優(yōu)先生成樹7.3圖的遍歷分析：假設(shè)W、W和W均為V的鄰接點(diǎn)，SG、SG和SG123123分別為含頂點(diǎn)W、W和W的子圖。123V訪問頂點(diǎn)V：for(W、W、W)123若該鄰接點(diǎn)W未被訪問，iww1w23則從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。SGSGSG312結(jié)論：深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷7.3圖的遍歷Eg7-4對無向圖連通圖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無向圖G1結(jié)論：從某一個頂點(diǎn)出發(fā)的遍歷結(jié)果是不唯一的。7.3圖的遍歷voidDFSTraverse(GraphG,Status(*Visit)(intv)){//對連通圖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);//對v的尚未訪問的鄰接頂點(diǎn)w//遞歸調(diào)用DFS}//DFS7.3圖的遍歷非連通圖的深度優(yōu)先遍歷①在每個連通分量或每個強(qiáng)連通分量中都選一個頂點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，最后將每個連通分量或每個強(qiáng)連通分量的遍歷結(jié)果合起來，則得到整個非連通圖的遍歷結(jié)果。②遍

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

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