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

《圖的深度優(yōu)先遍歷》由會(huì)員分享，可在線閱讀，更多相關(guān)《圖的深度優(yōu)先遍歷（54頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級(jí),,第三級(jí),,第四級(jí),,第五級(jí),,,*,7.3圖的遍歷,,回顧其他數(shù)據(jù)結(jié)構(gòu)的遍歷：,,順序表的遍歷,,單鏈表的遍歷,,二叉樹(shù)的遍歷,,展望：,,那么對(duì)于圖，我們?cè)鯓舆M(jìn)行遍歷呢？,,圖的深度優(yōu)先遍歷,,圖的廣度優(yōu)先遍歷,,,這兩個(gè)算法是后面拓?fù)渑判?、求關(guān)鍵路徑算法的基礎(chǔ),,,7.3.1.連通圖的深度優(yōu)先遍歷,,,,1.深度優(yōu)先遍歷以v開(kāi)始的連通圖,訪問(wèn),v,,分別深度優(yōu)先遍歷,v,的各個(gè)未被訪問(wèn)的鄰接點(diǎn),算法描述:,,2.算法演示,,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8

2、,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,v1,v2,v3,v4,v5,v6,v7,v8,例圖及其鄰接表表示,,演示開(kāi)始，以v1為遍歷的起點(diǎn),,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,v1,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,

3、8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,v2,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,

4、v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,v4,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,

5、,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,v4,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,,,v4,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,

6、,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,,,v4,v2,v8,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,,,v4,v2,v8,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v

7、8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,,,v4,v2,,,v8,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,,,v4,v2,,,v8,v4,v5,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v

8、5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,,,v4,v2,,,v8,v4,v5,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7

9、,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,

10、,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1

11、,v3,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2

12、,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7

13、,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,0,

14、,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,v3,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,,,

15、v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,,v3,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,,v3,v1,v6,v7,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,

16、v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,,v3,v1,v6,v7,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,,v3,v1,v7,,,v6,,0,,,1,v1,,

17、2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,,v3,v1,v7,,,v6,v3,v7,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,

18、v5,,,,v1,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,,v3,v1,v7,,,v6,v3,v7,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,,v3,v1,v7,,,v6,v3,,,v7,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6

19、,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,,v3,v1,v7,,,v6,v3,,,v7,v3,v6,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,,,v2,v1,v5,

20、,,v4,v2,,,v8,v4,,,v5,v2,v8,,,v3,v1,v7,,,v6,v3,,,v7,v3,v6,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,,v3,v1,v7,,,v6,v3,,,v7,v3,v6,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7

21、,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,,v3,v1,v7,,,v6,v3,,,v7,v3,v6,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,,,v2,v1,v5,,,v4,v

22、2,,,v8,v4,,,v5,v2,v8,,,v3,v1,v7,,,v6,v3,,,v7,v3,v6,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,,v3,v1,v7,,,v6,v3,,,v7,v3,v6,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8

23、,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,,v3,v1,v7,,,v6,v3,,,v7,v3,v6,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,,,v2,v1,v5,,,v4,v2,,,v8

24、,v4,,,v5,v2,v8,,,v3,v1,v7,,,v6,v3,,,v7,v3,v6,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,,,v1,,,v2,v1,v5,,,v4,v2,,,v8,v4,,,v5,v2,v8,,,v3,v1,v7,,,v6,v3,,,v7,v3,v6,,演示結(jié)束,,3.算法實(shí)現(xiàn),,從演示過(guò)程可以看出，我們必須知道頂點(diǎn)是否已經(jīng)被訪問(wèn)過(guò)。在具體實(shí)現(xiàn)時(shí)，我們用一個(gè)全局?jǐn)?shù)

25、組visited[]來(lái)記錄頂點(diǎn)是否被訪問(wèn)過(guò)。如果visited[i]的值為T(mén)rue，則頂點(diǎn)vi已經(jīng)被訪問(wèn)，否則沒(méi)有被訪問(wèn)。,,3.算法實(shí)現(xiàn),,Void DFS（Graph G，int v）,,{,,Visited[v]=True；cout<

26、rue;//以前未被訪問(wèn)，此處被訪問(wèn),,／／改變對(duì)應(yīng)的標(biāo)志為已經(jīng)訪問(wèn),,cout<0;w=NextAdjVex(mg,v,w)),,{／／對(duì)于v的每一個(gè)鄰接點(diǎn)進(jìn)行考察,,if(visited[w]==false)／／當(dāng)該結(jié)點(diǎn)未被訪問(wèn)時(shí),,DFS(mg,w);／／進(jìn)行深度優(yōu)先遍歷,,},,},,練習(xí)題：,,,對(duì)于下面一個(gè)圖及其存儲(chǔ)結(jié)構(gòu)，寫(xiě)出以v2、v8為起始點(diǎn)的深度優(yōu)先遍歷序列。,,0,,,1,v1,,2,v2,,3,V3,,4,V4,,5,v5,,6,v6,,7,v7,

27、,8,v8,,v2,,v3,,v1,,v4,,v5,,v1,,v6,,v7,,v2,,v8,,v2,,v8,,v3,,v7,,v3,,v6,,v4,,v5,,v1,v2,v3,v4,v5,v6,v7,v8,例圖及其鄰接表表示,,,答案為：,,以v2為起始點(diǎn)：v2-v1-v3-v6-v7-v4-v8-v5,,,以v8為起始點(diǎn)：v8-v4-v2-v1-v3-v6-v7-v5,,思考題：,,若圖不是連通圖，如何進(jìn)行深度優(yōu)先遍歷？,,請(qǐng)建立下圖的鄰接表結(jié)構(gòu)，并進(jìn)行深度優(yōu)先遍歷．,v1,v2,v3,v4,v5,v6,v7,,bool visited[100]={false}；,,,void DFSTraverse(ALGraph mg),,{,,for(int i=1 ;i<=mg.vexnum;i++),,{,,if(visited[i]==false),,DFS(mg,i);,,},,},,