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

Posted by Chiu CC on 2 11, 2016


先備知識與注意事項

Binary Tree: Traversal(尋訪)中介紹過Pre-Order Traversal,其Visiting順序:「Current(V)-left(L)-right(R)」可以解讀成「先遇到的node就先Visiting」,因此,每一組「Current-left-right」必定是CurrentNode先Visiting,接著是leftchild,最後才是rightchild
若對圖一中的Binary Tree進行Pre-Order Traversal,定義Visiting為印出(print)資料,將得到:

A B D E G H C F

dfs

圖一。

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

以圖二的迷宮為例,把迷宮矩陣中的每一格定義成一個vertex,若兩個vertex之間有路,則建立edge相連。若要在迷宮中尋找抵達終點的路線,通常會先選擇其中一條路線,只要有路就繼續往前走。有可能一路走到終點,也有可能遇到死路。若遇到死路則回到上一個岔路,往另一條路探索路線。依此類推,直到走出迷宮。

dfs

圖二:迷宮問題(maze problem)。


目錄


Depth-First Search(DFS,深度優先搜尋)

考慮圖三(a)的Graph(沒有weight的directed graph):

dfs

圖三(a):。

若以vertex(A)為起點進行DFS(),可以得到:

  • 若Graph中的vertex與vertex(A)之間存在至少一條path,則DFS()必定能找到其中一條path從vertex(A)抵達該vertex。但是這條path未必保證是最短路徑(shortest path)。

看起來好像沒有BFS()這麼殺手級,雖然找到一條路卻不保證是最短路徑。
但其實DFS()還是很有用的,因為經過一次DFS()後,將得到一項資料稱作finish,而finish竟然可以用來...!?

別轉台,看下去。


演算法

以下介紹的DFS()需要資料項目共有:

  1. time:在整個DFS()的過程會有一條「時間軸」,若Graph中有\(N\)個vertex,「時間軸」上一共會有\(2N\)個「時間點」。
  2. discoverfinish array:每個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]
  3. color array:利用color標記哪些vertex已經「被發現」與「結束」。
    • 白色表示該vertex還沒有「被發現」;
    • 灰色表示該vertex已經「被發現」,但是還沒有「結束」。
    • 黑色表示該vertex已經「結束」。
  4. predecessor array:記錄某個vertex是被哪一個vertex找到的,如此便能回溯路徑(如同BFS()DFS()亦能生成一個Predecessor Subgraph)。

DFS()的方法如下:

初始化(initialization),見圖三(b):

  • 先把time設為0,表示還沒有任何vertex「被發現」。
  • 把所有vertex塗成白色。
  • 把所有vertex的predecessor清除(或者設成NULL-1,視資料形態(data type)而定)。
  • 把所有vertex的discoverfinish設成0,表示還沒有開始進行DFS()

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)之Adjacency List中,第一個與vertex(A)相連的vertex為vertex(B),接著便以vertex(B)為起點,繼續尋找與vertex(B)相連之「最近的」vertex。
  • 由於從vertex(A)找到了vertex(B),便表示「從vertex(A)出發的path」還在更新,於是vertex(A)便還沒有「結束」,所以finish[A]不需要更新。
    • 那麼,什麼時候會更新finish[A]呢?
      Adjacency List中,與vertex(A)相連之vertex有vertex(B)與vertex(C),要在這兩個vertex都「作為搜尋起點」,並且「探索完所有相連的vertex」後(也就是更新完finish[B]finish[C]後),才會更新到finish[A]
  • 圖三(c)中的「Time Stamp(時間戳記)」即為「時間軸」。
    此時進入「剛發現vertex(A)」,並且尚未結束「以vertex(A)作為搜尋起點」的階段。

dfs

圖三(c):。

從vertex(A)作為探索起點,「最先發現」的是vertex(B),便以其作為新的起點:

  • 把vertex(B)塗成灰色,表示已經「被發現」。
  • 由於vertex(B)已經「被發現」,便把discover[B]設為++time,也就是distance[B]=2
  • 接著,找到Adjacency List中第一個與vertex(B)相連,且為白色的vertex(D),將vertex(D)視為新的搜尋起點。
  • 此時圖三(d)的「時間軸」表示,「以vertex(A)作為起點」之搜尋尚未結束(vertex(A)還沒有被塗黑),而且「以vertex(B)作為起點」之搜尋剛剛開始。

dfs

圖三(d):。

來到「以vertex(D)作為起點」之搜尋,大致上與「以vertex(B)作為起點」之搜尋相同:

  • 把vertex(D)塗成灰色,表示已經「被發現」。
  • 由於vertex(D)已經「被發現」,便把discover[D]設為++time,也就是distance[D]=3
  • 接著,找到Adjacency List中第一個與vertex(D)相連,且為白色的vertex(E),將vertex(E)視為新的搜尋起點。
  • 此時圖三(e)的「時間軸」表示,「以vertex(A)與vertex(B)作為起點」之搜尋都還沒結束(vertex(A)、vertex(B)還沒有被塗黑),而且「以vertex(D)作為起點」之搜尋剛剛開始。

dfs

圖三(e):。

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

dfs

圖三(f):。

關鍵是圖三(g)。
當vertex(E)再也找不到任何「能夠抵達、且為白色」的vertex時(見圖三(g)中Graph的箭頭方向,並對照圖三(a)之Adjacency List),就表示「以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]=4finish[E]=5,往後搜尋過程就不會再有vertex(E)出現。而以vertex(A)、vertex(B)、vertex(D)作為起點的搜尋則持續進行。

dfs

圖三(g):。

接著,從vertex(E)退回到vertex(D),並從vertex(D)繼續發現vertex(F)還是白色,於是便以「vertex(F)作為起點」進行搜尋:

  • 把vertex(F)塗成灰色。
  • discover[F]設為++time
  • 繼續尋找所有從vertex(F)能夠走到,且為白色的vertex。

dfs

圖三(h):。

觀察圖三(i)的Graph與圖三(a)的Adjacency List,發現從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。

dfs

圖三(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。

dfs

圖三(j):。

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

dfs

圖三(k):。

dfs

圖三(l):。

dfs

圖三(m):。

dfs

圖三(n):。

在「以vertex(A)為起點」之搜尋結束後,必須確認Graph中還有沒有白色的vertex,如圖三(n),Graph裡還有vertex(G)與vertex(H)仍然是白色,因此挑選其中一個vertex作為新的起點。這裡是按照Adjacency List的順序,由於vertex(G)在vertex(H)之前,便先挑選vertex(G),接著重複上述步驟,見圖三(o)-(r)。

dfs

圖三(o):。

dfs

圖三(p):。

dfs

圖三(q):。

dfs

圖三(r):。

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


程式碼

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

如同上一篇Graph: Breadth-First Search(BFS,廣度優先搜尋),以下將使用int處理資料,把\(9\)個vertexchar A~I依序對應到int 0~8

範例程式碼包含兩個部分main()class Graph

main()中,主要兩件事情:

  1. 建立如圖三(a)的Adjacency List
  2. 進行DFS()

class Graph中:

  • private member:
    • num_vertex:需要在定義Graph的object(物件)時,給定vertex的數目,以便建立Adjacency List(或者Adjacency Matrix)。
    • std::vector< std::list<int> > AdjList:利用C++標準函式庫(STL)提供的container(容器):std::vectorstd::list來實現。
    • colordiscoverfinishpredecessor:將在DFS()中使用,功能如上述。
  • public member:
    • Constructor:Graph(int num_vertex):在定義Graph的object(物件)時,需要知道vertex的數目,並在constructor中定義好AdjList
    • AddEdgeList(int from, in to):功能便是在AdjList新增從fromto的edge。
    • DFS(int Start):需要知道起點vertex。
    • DFSVisit(int vertex, int &time):利用遞迴函式呼叫,進行colordiscoverfinishpredecessor等資料更新的主要函式。


// C++ code
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <iomanip>      // for std::setw()

class Graph{
private:
    int num_vertex;
    std::vector< std::list<int> > AdjList;
    int *color,             // 0:white, 1:gray, 2:black
        *predecessor,
        *discover,
        *finish;
public:
    Graph():num_vertex(0){};
    Graph(int N):num_vertex(N){
        // initialize Adj List
        AdjList.resize(num_vertex);
    };
    void AddEdgeList(int from, int to);
    void BFS(int Start);    // 定義見上一篇文章
    void DFS(int Start);
    void DFSVisit(int vertex, int &time);
};

void Graph::DFS(int Start){
    color = new int[num_vertex];           // 配置記憶體位置
    discover = new int[num_vertex];
    finish = new int[num_vertex];
    predecessor = new int[num_vertex];

    int time = 0;                          // 初始化, 如圖三(b)
    for (int i = 0; i < num_vertex; i++) { 
        color[i] = 0;
        discover[i] = 0;
        finish[i] = 0;
        predecessor[i] = -1;
    }

    int i = Start;
    for (int j = 0; j < num_vertex; j++) { // 檢查所有Graph中的vertex都要被搜尋到
        if (color[i] == 0) {               // 若vertex不是白色, 則進行以該vertex作為起點之搜尋
            DFSVisit(i, time);
        }
        i = j;                             // j會把AdjList完整走過一遍, 確保所有vertex都被搜尋過
    }
}

void Graph::DFSVisit(int vertex, int &time){   // 一旦有vertex被發現而且是白色, 便進入DFSVisit()
    color[vertex] = 1;                         // 把vertex塗成灰色
    discover[vertex] = ++time;                 // 更新vertex的discover時間
    for (std::list<int>::iterator itr = AdjList[vertex].begin();   // for loop參數太長
         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時間
}

int main(){
    // 定義一個具有八個vertex的Graph
    Graph g2(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] is empty
    g2.AddEdgeList(5, 1);
    g2.AddEdgeList(6, 4);g2.AddEdgeList(6, 7);
    g2.AddEdgeList(7, 6);

    g2.DFS(0);    // 以vertex(0), 也就是vertex(A作為DFS()的起點

    return 0;
}


討論

若在DFS()函式主體的最後多加入幾行程式來檢查predecessordiscoverfinish三項資料是否符合預期:

void Graph::DFS(int Start){
 // after for loop
 std::cout << "predecessor:" << std::endl;         // 印出 A(0) ~ H(7)的predecessor
    for (int i = 0; i < num_vertex; i++){
        std::cout << std::setw(4) << i;
    }
    std::cout << std::endl;
    for (int i = 0; i < num_vertex; i++){
        std::cout << std::setw(4) << predecessor[i];
    }
    std::cout << "\ndiscover time:" << std::endl;  // 印出 A(0) ~ H(7)的discover time
    for (int i = 0; i < num_vertex; i++){
        std::cout << std::setw(4) << i;
    }
    std::cout << std::endl;
    for (int i = 0; i < num_vertex; i++){
        std::cout << std::setw(4) << discover[i];
    }
    std::cout << "\nfinish time:" << std::endl;    // 印出 A(0) ~ H(7)的finish time
    for (int i = 0; i < num_vertex; i++){
        std::cout << std::setw(4) << i;
    }
    std::cout << std::endl;
    for (int i = 0; i < num_vertex; i++){
        std::cout << std::setw(4) << finish[i];
    }
}

便能得到:

predecessor:
   0   1   2   3   4   5   6   7
  -1   0   0   1   3   3  -1   6
discover time:
   0   1   2   3   4   5   6   7
   1   2  10   3   4   6  13  14
finish time:
   0   1   2   3   4   5   6   7
  12   9  11   8   5   7  16  15

與預期的結果相同,如圖四。

dfs

圖四:。

Depth-First Tree

如同BFS(),在Graph上進行DFS()同樣可以得到Predecessor Subgraph,又稱為Depth-First Tree。若Graph本身不是(strongly) connected component,則有可能得到Depth-First Forest,如圖五:

dfs

圖五:。

根據圖五的「時間軸」,可以直接由discoverfinish觀察出各個vertex之間的「ancestor-descendant」關係(也就包含了predecessor關係):

  1. discover[X]discover[Y]大,而且finish[X]finish[Y]小,表示vertex(X)比vertex(Y)較晚「被發現」,而且較早「結束」,則vertex(X)必定是vertex(Y)的descendant。
    • 以vertex(E)與vertex(A)為例,vertex(E)的「搜尋生命週期」完全在vertex(A)的「搜尋生命週期」之內,因此vertex(E)必定是vertex(A)的descendant。
  2. 相反,若discover[X]discover[Y]小,而且finish[X]finish[Y]大,表示vertex(X)比vertex(Y)較早「被發現」,而且較晚「結束」,則vertex(X)必定是vertex(Y)的ancestor。
    • 以vertex(B)與vertex(F)為例,vertex(B)的「搜尋生命週期」完全包覆住vertex(F)的「搜尋生命週期」,因此vertex(B)必定是vertex(F)的ancestor。
  3. 第三種情形,若兩個vertex的「搜尋生命週期」完全沒有重疊,那麼這兩個vertex在Depth-First Forest中:
    1. 有可能在同一棵Depth-First Tree,但是互相沒有「ancestor-descendant」的關係,例如vertex(D)與vertex(C)。此時,discover[D]\(<\)discover[C],而且finish[D]\(<\)finish[C]
    2. 也有可能在不同棵Depth-First Tree,例如vertex(C)與vertex(H)。此時,discover[C]\(<\)discover[H],而且finish[C]\(<\)finish[H]

4種edge

dfs

圖六:。

經過DFS()後,還可以分類出四種edge:

  1. Tree edge:若vertex(Y)是被vertex(X)「發現」,則edge(X,Y)即為Tree edge,也就是Depth-First Tree中的edge。
    • 透過顏色判斷edge:當vertex(X)搜尋到vertex(Y),且vertex(Y)為「白色」時,就會建立出Tree edge。
  2. Back edge:所有指向ancestor的edge,稱為Back edge。如圖六中,edge(F,B)與edge(H,G)。
    • 透過顏色判斷edge:當vertex(X)搜尋到vertex(Y),且vertex(Y)為「灰色」,就會建立起Back edge,見圖三(j)、圖三(q)與圖六。
  3. Forward edge:所有指向descendant但不是Tree edge的edge,稱為Forward edge。觀察「時間軸」,若Graph存在例如:edge(A,D)、edge(A,E)或者edge(B,E),即可稱之為Forward edge。很遺憾的,圖六中,沒有Forward edge。
    • 透過顏色判斷edge:當vertex(X)搜尋到vertex(Y)時,vertex(Y)為「黑色」,並且discover[X]\(<\)discover[Y],edge(X,Y)即為Forward edge。
  4. Cross edge:若兩個vertex不在同一棵Depth-First Tree上,例如vertex(C)與vertex(H),或者兩個vertex在同一棵Depth-First Tree上卻沒有「ancestor-descendant」的關係,例如vertex(C)與vertex(F),則稱連結此兩個vertex的edge為Cross edge。
    • 透過顏色判斷edge:當vertex(X)搜尋到vertex(Y)時,vertex(Y)為「黑色」,並且discover[X]\(>\)discover[Y],edge(X,Y)即為Cross edge。

分類出四種edge除了可以作為大腦體操,還可以根據Graph中是否具有/不具有某些edge來區分Graph的性質:

  • 若在undirected graph上執行一次DFS(),所有的edge不是Tree edge就是Back edge。
  • 若在directed graph上執行一次DFS(),沒有產生Back edge,則此directed graph必定是acyclic(沒有迴路)。

諸如此類的,是不是很有趣呢?
(好像也還好。)

最後再看一次DFS()的流程,見圖七:

dfs

圖七:。


以上便是Depth-First Search(DFS,深度優先搜尋)的介紹。
在接下來的文章中,將利用DFS()與神奇的finish

  1. 進行Topological Sort(拓撲排序)
  2. 找到directed graph中的Strongly Connected Component(SCC)

不過在這之前,會先介紹利用BFS()DFS()找到undirected graph中的connected component作為暖身。



參考資料:


BFS/DFS系列文章

Graph: Breadth-First Search(BFS,廣度優先搜尋)
Graph: Depth-First Search(DFS,深度優先搜尋)
Graph: 利用DFS和BFS尋找Connected Component
Grpah: 利用DFS尋找Strongly Connected Component(SCC)
Grpah: 利用DFS尋找DAG的Topological Sort(拓撲排序)

回到目錄:

目錄:演算法與資料結構


tags: C++, Graph, DFS,