[演算法] [C++ / Python] 深度優先搜尋 Depth-First-Search － Part I

更新：熱騰騰的 Part II 出爐囉！

深度優先搜尋，Depth-First-Search，簡稱 DFS，是一種用於圖或樹的遍歷、搜尋演算法。

• 樹

我們先畫一棵樹如下：

  是不是很繽紛呢(X 畫完樹之後，我們要選一個「起點」，在這裡我們選紅色的  1 。接下來我們可以看到，有三個節點與 1 相連，分別是  2 ,  3 ,  4 。

  接下來就是 DFS 的精華：先選一個節點「深」入研究，於是在這裡我們先選 2 來進行下一步。選 2 之後呢？我們會把  2  當作新的起點，再做一次 DFS，因此我們找到了  5 。

  糟了，以 5 為起點的話就找不到任何的節點了，這樣就結束了嗎？當然不是，這種情況下我們要返回到上一個節點，也就是 2，看看有沒有還沒去過的節點。

  －－也沒有，我們只好再回到 1，有了！剛剛先被我們放到一邊的 3 和 4，於是我們選擇  3  作為我們新 DFS 的起點。啊糟糕，原來 3 下面也沒有其他節點了XD 

  我們只好回到 1，去尋求 4 的幫助(?)，我們以  4  為起點進行 DFS，發現有  6  跟  7  兩個節點；依據 DFS 的原則，先訪問其中一個，在這裡選 6，接著回到 4，再走到 7。

  因為 7 後面沒有節點了，所以回到 4，再回到 1，結果發現 1 也沒了，因此，DFS 到此全部完畢。

• 程式碼實作 － C++

void dfs(Node* start){
    if (start == nullptr){  // 如果這個位置沒有節點
        return;  // 返回上一個
    }
    cout << start->data << " visited." << endl;
    for (int i = 0; i < 3; i++){
        dfs(start->next[i]);  // 分別以目前所找到的節點作為下一次 DFS 的起點
    }
}

這裡僅列出重點部分，完整程式碼請至這裡查看

• 程式碼實作 － Python

def dfs(start):
    if start is None:  # 如果這個位置沒有節點
        return  # 返回上一個
    print(start.data, ' visited.')
    for i in range(3):
        dfs(start.next[i])  # 分別以目前所找到的節點作為下一次 DFS 的起點

這裡一樣只列出重點部分，完整程式碼請至這裡查看