圖的深度優(yōu)先遍歷ppt課件

1、7.3圖的遍歷回顧其他數(shù)據(jù)結(jié)構(gòu)的遍歷：順序表的遍歷單鏈表的遍歷二叉樹的遍歷展望：那么對于圖，我們怎樣進行遍歷呢？圖的深度優(yōu)先遍歷圖的廣度優(yōu)先遍歷這兩個算法是后面拓?fù)渑判?、求關(guān)鍵路徑算法的基礎(chǔ)1；.7.3.1.連通圖的深度優(yōu)先遍歷2；.1.深度優(yōu)先遍歷以v開始的連通圖訪問v分別深度優(yōu)先遍歷v的各個未被訪問的鄰接點算法描述算法描述:3；.2.算法演示4；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例圖及其鄰接表表示5；.演示開始，以v1為遍歷的起點6；.01v12v23V34V45v56

2、v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v17；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v18；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3v29；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v210；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v

3、1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5v411；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5v412；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v413；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2v814；.01v1

4、2v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2v815；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v816；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4v517；.01v12v23V34V45v56v67v78v8v2v3v1v4v5

5、v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4v518；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v519；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v820；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v

6、8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v821；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v822；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v823；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3

7、v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v824；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v825；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v826；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v

8、3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v827；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v828；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v829；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6

9、v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v330；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v6v731；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v6v732；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v

10、2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v633；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3v734；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3v735；.01v12v2

11、3V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v736；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v637；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5

12、, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v638；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v639；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v640；.01v12v23V34V45v5

13、6v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v641；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v642；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v

14、2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v643；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v644；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v645；.演示結(jié)束46；.3.算法實現(xiàn) 從演示過程可

15、以看出，我們必須知道頂點是否已經(jīng)被訪問過。在具體實現(xiàn)時，我們用一個全局?jǐn)?shù)組visited來記錄頂點是否被訪問過。如果visitedi的值為True，則頂點vi已經(jīng)被訪問，否則沒有被訪問。47；.3.算法實現(xiàn)Void DFS（Graph G，int v）Visitedv=True；coutv;For(v的每一個鄰接點w)If(visitedw=false)/如果沒有被訪問過DFS(G,w)48；.3.算法實現(xiàn)當(dāng)圖的存儲結(jié)構(gòu)為鄰接表時，深度優(yōu)先算法可以表示如下：bool visited100=false;void DFS(ALGraph mg,int v)visitedv=true;/以前未被訪問，此處被訪問改變對應(yīng)的標(biāo)志為已經(jīng)訪問coutmg.vexsv.data0;w=NextAdjVex(mg,v,w)對于v的每一個鄰接點進行考察if(visitedw=false)當(dāng)該結(jié)點未被訪問時DFS(mg,w);進行深度優(yōu)先遍歷49；.練習(xí)題：對于下面一個圖及其存儲結(jié)構(gòu)，寫出以v2、v8為起始點的深度優(yōu)先遍歷序列。50；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例圖及其鄰接表