Graph: Depth-First Search(DFS，深度優先搜尋)

演算法 Togglenavigation SecondRound Archives Tags About 先備知識與注意事項 在BinaryTree:Traversal(尋訪)中介紹過Pre-OrderTraversal，其Visiting順序：「Current(V)-left(L)-right(R)」可以解讀成「先遇到的node就先Visiting」，因此，每一組「Current-left-right」必定是CurrentNode先Visiting，接著是leftchild，最後才是rightchild。

若對圖一中的BinaryTree進行Pre-OrderTraversal，定義Visiting為印出(print)資料，將得到： ABDEGHCF 圖一。

Depth-FirstSearch(DFS，深度優先搜尋)的核心精神便如同Pre-OrderTraversal：「先遇到的vertex就先Visiting」，並且以先遇到的vertex作為新的搜尋起點，直到所有「有edge相連的vertex」都被探索過。

以圖二的迷宮為例，把迷宮矩陣中的每一格定義成一個vertex，若兩個vertex之間有路，則建立edge相連。

若要在迷宮中尋找抵達終點的路線，通常會先選擇其中一條路線，只要有路就繼續往前走。

有可能一路走到終點，也有可能遇到死路。

若遇到死路則回到上一個岔路，往另一條路探索路線。

依此類推，直到走出迷宮。

圖二：迷宮問題(mazeproblem)。

目錄 Depth-FirstSearch(DFS，深度優先搜尋) 演算法 程式碼 討論 Depth-FirstTree 4種edge 參考資料 BFS/DFS系列文章 Depth-FirstSearch(DFS，深度優先搜尋) 考慮圖三(a)的Graph(沒有weight的directedgraph)： 圖三(a)：。

若以vertex(A)為起點進行DFS()，可以得到： 若Graph中的vertex與vertex(A)之間存在至少一條path，則DFS()必定能找到其中一條path從vertex(A)抵達該vertex。

但是這條path未必保證是最短路徑(shortestpath)。

看起來好像沒有BFS()這麼殺手級，雖然找到一條路卻不保證是最短路徑。

但其實DFS()還是很有用的，因為經過一次DFS()後，將得到一項資料稱作finish，而finish竟然可以用來...！？ 別轉台，看下去。

演算法 以下介紹的DFS()需要資料項目共有： time：在整個DFS()的過程會有一條「時間軸」，若Graph中有\(N\)個vertex，「時間軸」上一共會有\(2N\)個「時間點」。

discover與finisharray：每個vertex會被標記上兩個「時間點」，分別是「被發現(discover)」的時間與「結束(finish)」的時間： discover：例如，vertex(B)被vertex(A)找到，則discover[B]會是discover[A]加一，表示vertex(B)在整個時間軸上是在vertex(A)之後被找到(這其中便存在「ancestor-descendant」的關係)。

finish：若vertex(B)已經經由有效edge探索過所有與之相連的vertex，表示以vertex(B)為起點的探索已經結束，便標上finish[B]。

colorarray：利用color標記哪些vertex已經「被發現」與「結束」。

白色表示該vertex還沒有「被發現」； 灰色表示該vertex已經「被發現」，但是還沒有「結束」。

黑色表示該vertex已經「結束」。

predecessorarray：記錄某個vertex是被哪一個vertex找到的，如此便能回溯路徑(如同BFS()，DFS()亦能生成一個PredecessorSubgraph)。

DFS()的方法如下： 初始化(initialization)，見圖三(b)： 先把time設為0，表示還沒有任何vertex「被發現」。

把所有vertex塗成白色。

把所有vertex的predecessor清除(或者設成NULL、-1，視資料形態(datatype)而定)。

把所有vertex的discover與finish設成0，表示還沒有開始進行DFS()。

圖三(b)：。

以vertex(A)作為起點，見圖三(c)： 將vertex(A)塗成灰色，表示已經「被發現」。

由於vertex(A)已經「被發現」，便把discover[A]設為++time。

原本time=0，而vertex(A)是DFS()的起點，所以++time之後distance[A]=1便表示vertex(A)是第一個被發現。

接著尋找所有與vertex(A)相連之vertex，只要遇到第一個仍為白色的vertex，便把該vertex設為新的搜尋起點，並將該vertex之predecessor設為vertex(A)。

圖三(a)之AdjacencyList中，第一個與vertex(A)相連的vertex為vertex(B)，接著便以vertex(B)為起點，繼續尋找與vertex(B)相連之「最近的」vertex。

由於從vertex(A)找到了vertex(B)，便表示「從vertex(A)出發的path」還在更新，於是vertex(A)便還沒有「結束」，所以finish[A]不需要更新。

那麼，什麼時候會更新finish[A]呢？ 在AdjacencyList中，與vertex(A)相連之vertex有vertex(B)與vertex(C)，要在這兩個vertex都「作為搜尋起點」，並且「探索完所有相連的vertex」後(也就是更新完finish[B]與finish[C]後)，才會更新到finish[A]。

圖三(c)中的「TimeStamp(時間戳記)」即為「時間軸」。

此時進入「剛發現vertex(A)」，並且尚未結束「以vertex(A)作為搜尋起點」的階段。

圖三(c)：。

從vertex(A)作為探索起點，「最先發現」的是vertex(B)，便以其作為新的起點： 把vertex(B)塗成灰色，表示已經「被發現」。

由於vertex(B)已經「被發現」，便把discover[B]設為++time，也就是distance[B]=2。

接著，找到AdjacencyList中第一個與vertex(B)相連，且為白色的vertex(D)，將vertex(D)視為新的搜尋起點。

此時圖三(d)的「時間軸」表示，「以vertex(A)作為起點」之搜尋尚未結束(vertex(A)還沒有被塗黑)，而且「以vertex(B)作為起點」之搜尋剛剛開始。

圖三(d)：。

來到「以vertex(D)作為起點」之搜尋，大致上與「以vertex(B)作為起點」之搜尋相同： 把vertex(D)塗成灰色，表示已經「被發現」。

由於vertex(D)已經「被發現」，便把discover[D]設為++time，也就是distance[D]=3。

接著，找到AdjacencyList中第一個與vertex(D)相連，且為白色的vertex(E)，將vertex(E)視為新的搜尋起點。

此時圖三(e)的「時間軸」表示，「以vertex(A)與vertex(B)作為起點」之搜尋都還沒結束(vertex(A)、vertex(B)還沒有被塗黑)，而且「以vertex(D)作為起點」之搜尋剛剛開始。

圖三(e)：。

來到「以vertex(E)作為起點」之搜尋，與前兩個步驟相同，不再贅述，見圖三(f)。

圖三(f)：。

關鍵是圖三(g)。

當vertex(E)再也找不到任何「能夠抵達、且為白色」的vertex時(見圖三(g)中Graph的箭頭方向，並對照圖三(a)之AdjacencyList)，就表示「以vertex(E)作為起點」之搜尋已經「結束」，此時： 把vertex(E)塗成黑色，表示「以vertex(E)作為起點」之搜尋已經「結束」。

把finish[E]設成++time。

原先在vertex(E)「被發現」時time=4，更新後，表示vertex(E)之搜尋在time=5時「結束」。

當vertex(E)「結束」後，便回到vertex(E)的predecessor，也就是「發現vertex(E)」的vertex(D)，繼續探索其他vertex(D)能夠走到的vertex。

此時，圖三(g)的「時間軸」表示，discover[E]=4，finish[E]=5，往後搜尋過程就不會再有vertex(E)出現。

而以vertex(A)、vertex(B)、vertex(D)作為起點的搜尋則持續進行。

圖三(g)：。

接著，從vertex(E)退回到vertex(D)，並從vertex(D)繼續發現vertex(F)還是白色，於是便以「vertex(F)作為起點」進行搜尋： 把vertex(F)塗成灰色。

把discover[F]設為++time。

繼續尋找所有從vertex(F)能夠走到，且為白色的vertex。

圖三(h)：。

觀察圖三(i)的Graph與圖三(a)的AdjacencyList，發現從vertex(F)能夠走到vertex(B)，但是由於vertex(B)已經是「灰色」，表示「以vertex(B)為起點」之搜尋已經開始且尚未結束，於是vertex(F)無法「發現」vertex(B)，也無法走到其餘vertex，所以，vertex(F)便宣告「結束」： 把vertex(F)塗成黑色，表示「以vertex(F)作為起點」之搜尋已經「結束」。

把finish[F]設成++time。

當vertex(F)「結束」後，便回到vertex(F)的predecessor，也就是「發現vertex(F)」的vertex(D)，繼續探索其他vertex(D)能夠走到的vertex。

圖三(i)：。

如圖三(j)，所有vertex(D)能夠抵達的vertex都已經變成黑色，於是「以vertex(D)作為起點」之搜尋便結束： 把vertex(D)塗成黑色，表示「以vertex(D)作為起點」之搜尋已經「結束」。

把finish[D]設成++time。

當vertex(D)「結束」後，便回到vertex(D)的predecessor，也就是「發現vertex(D)」的vertex(B)，繼續探索其他vertex(B)能夠走到的vertex。

圖三(j)：。

接著便以上述邏輯重複步驟，直到vertex(A)被塗成黑色，見圖三(k)-(n)。

圖三(k)：。

圖三(l)：。

圖三(m)：。

圖三(n)：。

在「以vertex(A)為起點」之搜尋結束後，必須確認Graph中還有沒有白色的vertex，如圖三(n)，Graph裡還有vertex(G)與vertex(H)仍然是白色，因此挑選其中一個vertex作為新的起點。

這裡是按照AdjacencyList的順序，由於vertex(G)在vertex(H)之前，便先挑選vertex(G)，接著重複上述步驟，見圖三(o)-(r)。

圖三(o)：。

圖三(p)：。

圖三(q)：。

圖三(r)：。

當Graph中所有vertex都被塗成黑色，便完成DFS()。

程式碼 由以上說明可以觀察出，DFS()本質上是一種「遞迴(recursion)結構」，而遞迴結構其實是利用了系統的「堆疊(stack)」，因此，這兩種方式皆能實現DFS()，以下提供的範例程式碼將以遞迴形式完成。

如同上一篇Graph:Breadth-FirstSearch(BFS，廣度優先搜尋)，以下將使用int處理資料，把\(9\)個vertexcharA~I依序對應到int0~8。

範例程式碼包含兩個部分main()與classGraph。

在main()中，主要兩件事情： 建立如圖三(a)的AdjacencyList； 進行DFS()。

在classGraph中： privatemember： num_vertex：需要在定義Graph的object(物件)時，給定vertex的數目，以便建立AdjacencyList(或者AdjacencyMatrix)。

std::vector<:list>>AdjList：利用C++標準函式庫(STL)提供的container(容器):std::vector與std::list來實現。

color、discover、finish、predecessor：將在DFS()中使用，功能如上述。

publicmember： Constructor:Graph(intnum_vertex)：在定義Graph的object(物件)時，需要知道vertex的數目，並在constructor中定義好AdjList。

AddEdgeList(intfrom,into)：功能便是在AdjList新增從from到to的edge。

DFS(intStart)：需要知道起點vertex。

DFSVisit(intvertex,int&time)：利用遞迴函式呼叫，進行color、discover、finish與predecessor等資料更新的主要函式。

//C++code #include #include #include #include #include//forstd::setw() classGraph{ private: intnum_vertex; std::vector<:list>>AdjList; int*color,//0:white,1:gray,2:black *predecessor, *discover, *finish; public: Graph():num_vertex(0){}; Graph(intN):num_vertex(N){ //initializeAdjList AdjList.resize(num_vertex); }; voidAddEdgeList(intfrom,intto); voidBFS(intStart);//定義見上一篇文章 voidDFS(intStart); voidDFSVisit(intvertex,int&time); }; voidGraph::DFS(intStart){ color=newint[num_vertex];//配置記憶體位置 discover=newint[num_vertex]; finish=newint[num_vertex]; predecessor=newint[num_vertex]; inttime=0;//初始化,如圖三(b) for(inti=0;i::iteratoritr=AdjList[vertex].begin();//forloop參數太長 itr!=AdjList[vertex].end();itr++){//分成兩段 if(color[*itr]==0){//若搜尋到白色的vertex predecessor[*itr]=vertex;//更新其predecessor DFSVisit(*itr,time);//立刻以其作為新的搜尋起點,進入新的DFSVisit() } } color[vertex]=2;//當vertex已經搜尋過所有與之相連的vertex後,將其塗黑 finish[vertex]=++time;//並更新finish時間 } intmain(){ //定義一個具有八個vertex的Graph Graphg2(8); //建立如圖三之Graph g2.AddEdgeList(0,1);g2.AddEdgeList(0,2); g2.AddEdgeList(1,3); g2.AddEdgeList(2,1);g2.AddEdgeList(2,5); g2.AddEdgeList(3,4);g2.AddEdgeList(3,5); //AdjList[4]isempty g2.AddEdgeList(5,1); g2.AddEdgeList(6,4);g2.AddEdgeList(6,7); g2.AddEdgeList(7,6); g2.DFS(0);//以vertex(0),也就是vertex(A作為DFS()的起點 return0; } 討論 若在DFS()函式主體的最後多加入幾行程式來檢查predecessor、discover與finish三項資料是否符合預期： voidGraph::DFS(intStart){ //afterforloop std::cout<\)discover[Y]，edge(X,Y)即為Crossedge。

分類出四種edge除了可以作為大腦體操，還可以根據Graph中是否具有/不具有某些edge來區分Graph的性質： 若在undirectedgraph上執行一次DFS()，所有的edge不是Treeedge就是Backedge。

若在directedgraph上執行一次DFS()，沒有產生Backedge，則此directedgraph必定是acyclic(沒有迴路)。

諸如此類的，是不是很有趣呢？ (好像也還好。

) 最後再看一次DFS()的流程，見圖七： 圖七：。

以上便是Depth-FirstSearch(DFS，深度優先搜尋)的介紹。

在接下來的文章中，將利用DFS()與神奇的finish： 進行TopologicalSort(拓撲排序)。

找到directedgraph中的StronglyConnectedComponent(SCC)。

不過在這之前，會先介紹利用BFS()與DFS()找到undirectedgraph中的connectedcomponent作為暖身。

參考資料： IntroductiontoAlgorithms,Ch22 FundamentalsofDataStructuresinC++,Ch6 CodeReview：DepthFirstSearchandBreadthFirstSearchinC++ BFS/DFS系列文章 Graph:Breadth-FirstSearch(BFS，廣度優先搜尋) Graph:Depth-FirstSearch(DFS，深度優先搜尋) Graph:利用DFS和BFS尋找ConnectedComponent Graph:利用DFS尋找StronglyConnectedComponent(SCC) Graph:利用DFS尋找DAG的TopologicalSort(拓撲排序) 回到目錄： 目錄：演算法與資料結構 tags:C++,Graph,DFS,