圖的遍歷概念
圖的遍歷
和樹的遍歷類似圖的遍歷也是從某個頂點出發沿著某條搜索路徑對圖中每個頂點各做一次且僅做一次訪問它是許多圖的算
法的基礎
深度優先遍歷和廣度優先遍歷是最為重要的兩種遍歷圖的方法它們對無向圖和有向圖均適用
注意
以下假定遍歷過程中訪問頂點的操作是簡單地輸出頂點
布爾向量visited[n]的設置
圖中任一頂點都可能和其它頂點相鄰接在訪問了某頂點之後又可能順著某條回路又回到了該頂點為了避免重復訪問同一個
頂點必須記住每個已訪問的頂點為此可設一布爾向量visited[n]其初值為假一旦訪問了頂點V i 之後便將
visited[i]置為真
深度優先遍歷(DepthFirst Traversal)
圖的深度優先遍歷的遞歸定義
假設給定圖G的初態是所有頂點均未曾訪問過在G中任選一頂點v為初始出發點(源點)則深度優先遍歷可定義如下首先訪問出
發點v並將其標記為已訪問過;然後依次從v出發搜索v的每個鄰接點w若w未曾訪問過則以w為新的出發點繼續進行深度優先遍歷
直至圖中所有和源點v有路徑相通的頂點(亦稱為從源點可達的頂點)均已被訪問為止若此時圖中仍有未訪問的頂點則另選一個
尚未訪問的頂點作為新的源點重復上述過程直至圖中所有頂點均已被訪問為止
圖的深度優先遍歷類似於樹的前序遍歷采用的搜索方法的特點是盡可能先對縱深方向進行搜索這種搜索方法稱為深度優先搜
索(DepthFirst Search)相應地用此方法遍歷圖就很自然地稱之為圖的深度優先遍歷
深度優先搜索的過程
設x是當前被訪問頂點在對x做過訪問標記後選擇一條從x出發的未檢測過的邊(xy)若發現頂點y已訪問過則重新選擇另
一條從x出發的未檢測過的邊否則沿邊(xy)到達未曾訪問過的y對y訪問並將其標記為已訪問過;然後從y開始搜索直到搜索
完從y出發的所有路徑即訪問完所有從y出發可達的頂點之後才回溯到頂點x並且再選擇一條從x出發的未檢測過的邊上述過程
直至從x出發的所有邊都已檢測過為止此時若x不是源點則回溯到在x之前被訪問過的頂點;否則圖中所有和源點有路徑相通的
頂點(即從源點可達的所有頂點)都已被訪問過若圖G是連通圖則遍歷過程結束否則繼續選擇一個尚未被訪問的頂點作為新源點
進行新的搜索過程
From:http://tw.wingwit.com/Article/program/sjjg/201311/23840.html
