深度優先遍歷序列
對圖進行深度優先遍歷時按訪問頂點的先後次序得到的頂點序列稱為該圖的深度優先遍歷序列或簡稱為DFS序列
()一個圖的DFS序列不一定惟一
當從某頂點x出發搜索時若x的鄰接點有多個尚未訪問過則我們可任選一個訪問之
()源點和存儲結構的內容均已確定的圖的DFS序列惟一
① 鄰接矩陣表示的圖確定源點後DFS序列惟一
DFSM算法中當從v i 出發搜索時是在鄰接矩陣的第i行上從左至右選擇下一個未曾訪問過的鄰接點作為新的出發點若這樣
的鄰接點多於一個則選中的總是序號較小的那一個
【例】對連通圖G 用鄰接矩陣表示時以v 為初始出發點的 DFS遍歷過程如下圖(a)所示具體算法的執行過程【 參見動
畫演示 】DFS序列是v v v v v v v v
②只有給出了鄰接表的內容及初始出發點才能惟一確定其DFS序列
鄰接表作為給定圖的存儲結構時其表示不惟一因為鄰接表上邊表裡的鄰接點域的內容與建表時的輸入次序相關
因此只有給出了鄰接表的內容及初始出發點才能惟一確定其DFS序列
【例】連通圖G 用鄰接表表示時以v 為初始出發點的 DFS算法的執行過程和DFS序列【 參見動畫演示 】
( )棧在深度優先遍歷算法中的作用
深度優先遍歷過程中後訪問的頂點其鄰接點被先訪問故在遞歸調用過程中使用棧(系統運行時刻棧)來保存已訪問的頂點
算法分析
對於具有n個頂點和e條邊的無向圖或有向圖遍歷算法DFSTraverse對圖中每頂點至多調用一次DFS或DFSM從DFSTraverse中調用
DFS(或DFSM)及DFS(或DFSM)內部遞歸調用自己的總次數為n
當訪問某頂點v i 時DFS(或DFSM)的時間主要耗費在從該頂點出發搜索它的所有鄰接點上用鄰接矩陣表示圖時其搜索時間為
O(n);用鄰接表表示圖時需搜索第i個邊表上的所有結點因此對所有n個頂點訪問在鄰接矩陣上共需檢查n 個矩陣元素
在鄰接表上需將邊表中所有O(e)個結點檢查一遍
所以DFSTraverse的時間復雜度為O(n ) (調用DFSM)或(n+e)(調用DFS)
From:http://tw.wingwit.com/Article/program/sjjg/201311/23835.html
