第七章-圖的深度優(yōu)先遍歷

主講教師：李曉娜《數(shù)據(jù)結(jié)構(gòu)》課程圖的遍歷目錄CONTENTS

圖的遍歷的定義

深度優(yōu)先遍歷的基本思想

深度優(yōu)先遍歷的實現(xiàn)過程圖的遍歷的定義1從圖的任意指定頂點出發(fā)，依照某種規(guī)則去訪問圖中所有頂點，且每個頂點僅被訪問一次，這一過程叫做圖的遍歷。

遍歷實質(zhì)：找每個頂點的鄰接點的過程。圖的遍歷圖的遍歷的定義1圖沒有“自然”的首結(jié)點圖的任意一個頂點都可作為第一個被訪問的首結(jié)點非連通圖中，從一個頂點出發(fā)，只能夠訪問它所在的連通分量上的所有頂點需考慮如何選取下一個出發(fā)點以訪問其余連通分量圖中若有回路存在，則一個頂點被訪問之后，有可能沿回路又回到該頂點區(qū)分已訪問頂點、未訪問頂點搜索路徑圖的特殊性深度優(yōu)先遍歷廣度優(yōu)先遍歷

DFS基本思想2深度優(yōu)先遍歷（Depth_FirstSearch，DFS）是指按照深度方向搜索，它類似于樹的先根遍歷。(1)從圖中某個頂點Vi出發(fā)，首先訪問Vi。(2)選擇一個與剛訪問過的頂點Vi相鄰接且未訪問過的頂點Vj，并訪問該頂點。以該頂點為新頂點，重復(fù)步驟(2)，直到當(dāng)前頂點的鄰接頂點都已被訪問為止。(3)返回前一個訪問過的且仍有未訪問的鄰接點的頂點，找出并訪問該頂點的下一個未被訪問的鄰接點，然后重復(fù)步驟(2)。深度優(yōu)先遍歷

DFS基本思想262024/11/18v5v3v2v7v8v0v6v1（a）這是一個遞歸的過程例：深度優(yōu)先遍歷

v4V0V1V2V3V6V8V7V5V4V0V1V2V3V4V5V6V7V8由此，得到頂點訪問序列為：v0->v1->v2->v3->v4->v5->v6->v7->v8思考：還能生成其他序列嗎？如何判別頂點V的鄰接點是否被訪問？

DFS基本思想2解決辦法：為每個頂點設(shè)立一個“訪問標(biāo)志”位?？稍O(shè)置一個輔助數(shù)組

visited[n]，用來標(biāo)記每個被訪問過的頂點。

初始狀態(tài)，將圖中每個頂點的訪問標(biāo)志設(shè)為0,之后搜索圖中每個頂點，如果未被訪問，就立即改visited[i]為1，防止它被多次訪問。并且以該頂點為新的起始點，繼續(xù)進(jìn)行深度優(yōu)先遍歷，否則繼續(xù)檢查下一個未被訪問的頂點。

DFS的實現(xiàn)過程3123456100000020000003000000400000050000006000000000000123456010000110000111000111010111110111111DFS結(jié)果輔助數(shù)組visited[n]v2→v1→v3→v5→v4→v6123456101110021000103100