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

在上次趴one 裡面我們已經以一棵彩虹樹(?) 來解釋了 DFS 的基礎步驟，並且用 C++ 以及 Python 實作了相關的程式碼，這次我們要來看看圖的部分。

啊，在這之前，我們簡單的複習一下 DFS 的要素：
          1) 選擇起始點
          2) 進入 DFS 後，先判斷是否已經到終端，如果是的話，離開 DFS
          3) 把這個節點設為已走訪過
          4) 尋找下一個可行的節點並進入，回到 2)

• 圖

當然是要先畫一張圖啦：

  為了方便討論，這是個無向圖，也就是每條路都是雙向道。那我們開始吧！一樣先選一個起點，這裡我們選  1 ，可以看到，與 1 相連的節點有  2  和  3 ，根據 DFS 的精神，我們一樣要選一個點來「深」入討論，這裡我們就選 2，並同時約定，之後若要從多個點選擇的話，以數字小的為優先。

  於是我們拿 2 來進行下一次的 DFS，結果找到了  3 ,  4 。因為剛剛的約定，我們在這先選比較小的 3 來進行下一層的 DFS，並找到了  1 ,  5 ,  6 ，咦？1 號節點我們剛剛不是走過了嗎？沒錯，所以我們這次就不用理他，直接選 5 繼續吧。

  接著我們就找到了  4  和  6 ，我們再接著選 4，結果發現他找到的 2 在前面就走訪過了，因此我們就返回到 5，並選擇 6 重新出發。結果發現，走 6 這條路也沒辦法找到還沒走訪過的節點，因此退回到 5。

  而 5 呢？也找不到新的節點了，所以再退，就這樣一路退到 1，發現完全沒有新的節點，因此，圖的 DFS 到此結束。

• 程式碼實作
• C++

void dfs(int now){
    cout << now << "  visited." << endl;
    for (int i = 1; i <= 6; i++){
        if (!visited[i] && e[now][i] == 1){  // 如果還沒來過而且可以走到
            visited[i] = true;
            dfs(i);
        }
    }
}

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

• Python

def dfs(now):
    print(now, ' visited.')
    for j in range(1, 7):
        if not visited[j] and e[now][j] == 1:
            visited[j] = True
            dfs(j)

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

上面程式碼的輸入可以用下面這些資料：

1 2
1 3
2 3
2 4
3 5
3 6
4 5
5 6

  這裡我是採用鄰接矩陣來儲存圖的，因為比較簡單（笑），當然也可以用鄰接串列，這樣對於稀疏圖來說比較省空間。

!! 2018/5/15 補：

  我竟然忘了提到這個部分！我們來看看如果依照走訪的順序把每個節點重新連接的話會長怎樣（左圖）：

  感覺好像不太直觀，那我們把他拉直，拉成右邊那樣，就會發現... 變成一棵樹了！這時我們稱這棵樹為圖的生成樹（之一），或在這裡也可以叫 DFS 樹，其特性有：一個節點的祖先一定會比他本身還早被走訪到等等。生成樹還有很多好玩的，就... 來日方長（遠望），有機會再介紹吧！

話說其實這篇圖和上篇樹的配色是以走訪順序配上彩虹的顏色來塗的。