前面的章節談了很多tree的應用，接下來要談談另一種結構，Graph。

Graph有點類似Tree，但他比Tree的限制更少，如下面四張圖的範例：

Tree有個條件是任意兩個節點之間只可能存在一種路徑，而Graph則沒有這個限制。

但Graph也有個限制是不可以節點自己連結自己，也不能有兩個節點互相連結：

也由於Graph有可能形成一個環狀的結構，方向性就是一個可以被額外定義的屬性。以下是加入方向性的Graph分類：

在介紹完Graph是什麼後，接著來討論Graph中的一個問題，s-t connectivity。

在以下的Graph中，我們知道s跟t是有連結在一起的，那我們該如何透過演算法來找出一個Graph中任意兩點是有連結的呢？

可能可以搞一個類似如下的recursion：

boolean connected(GraphNode a, GraphNode b){
    if(a.val == b.val){
        return true;
    }
    for(GraphNode neighbor : a.neighbors){
        connected(neighbor, b);
    }
    return false;
}

但是這樣會有infinite loop，我們從connected(0, 7)開始，由於0 ≠ 7，所以不會return true，進行到neighbor這邊時，neighbor會等於1，所以繼續connected(1, 7)，而1 ≠ 7，又會進到neighbor的環節，這時候如果neighbor選到0，那就是不斷反覆了～

所以我們要多一個動作，就是把connected(a, t)做過的a點mark起來，並在neighbor的判斷中多判斷是否有mark過，有mark過的就不再進行connected(n, t)：

boolean connected(GraphNode a, GraphNode b){
    a.mark = true;
    if(a.val == b.val){
        return true;
    }
    for(GraphNode neighbor : a.neighbors){
        if(!neighbor.mark){
            connected(neighbor, b);
        }
    }
    return false;
}

以下是程式行進的詳解：

在Graph中的traversal大致可分成兩種，一種叫做Depth First Search，另一種叫做Breadth First Search，這章節會先來介紹dps(Depth First Search)。

其實剛剛我們已經實際應用過dps了，會發現只要有沒被mark的鄰近元素，就會往那顆元素邁進，然後不斷往深處推進，直到盡頭。

這邊我們再來討論一個題目，那就是如何找出graph中某一點到任意一點的路徑？我們稱這個題目為depth first path：

先前提到過的Tree Traversal會有preorder跟postorder之分，在Graph也會有，其實差別就在於是在recursion之前做動作還是之後做動作的差別，在recursion之前先做動作就稱為preorder，反之就是postorder，所以剛剛depth first path中，我們的動作是set edgeTo，而且是在dfs(n)之前，所以就是preorder，稱之為DFS preorder。

反之也會有DFS postorder；假若我們要做的動作是print(GraphNode)，一樣用上面範例的graph來舉例，其結果如下：

DFS preorder：012543678

DFS postorder：347685210

既然Graph Traversal可以對應到Tree Traversal的preorder跟postorder，那level order是不是也有相對應的Graph Traversal呢？沒有錯，這就是我們下一章節要討論的Breadth First Search。

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License