【舌尖上的演算法】Day9 -- Brute Force - DFS & BFS

本系列文章同步分享於IT邦幫忙第12屆鐵人賽

前言

應該有人跟我一樣真心覺得Brute Force其實看起來也沒什麼，就都是很簡單的邏輯和實作方式，希望到目前為止大家都能理解。今天會是最後一天介紹Brute Force類別的演算法，而今天要講的內容是Depth-First Search(DFS)和Breadth-First Search(BFS)，這兩種演算法基本上都是拿來計算點對點之間的關聯，而具體這兩種方式是怎麼運作的呢？讓我們接著看下去。

遇到的問題？

上面提到DFS和BFS是用來計算點對點之間的關聯，用簡化的圖來表示的話，大概可以用上方的圖來舉例，會把資料設定成節點與連線，但是實際上需要用到這兩種方式解決的問題是什麼呢？最簡單最貼近生活的例子就是路徑導航，路徑導航其實也就是用點對點串起來計算最短的路徑，另外，當然也是可以拿到解謎宮的路線，或著計算電力網的串連是否完善等。例子很多，但我感覺路徑導航是最容易想像的問題。

Depth-First Search(DFS)

Depth-First Search在進行的過程中，會跑過所有的節點(Node)，並在跑過的節點做上記號，並記錄順序，直到所有的節點都有了記號，流程如下：

1. 先決定一個起始節點，並將其做上記號。
2. 從這個節點開始，去尋找下一個相連但無記號的節點，並將這個新的節點做上記號。
3. 反覆第二個步驟，直到進行到了一個不再與其他節點相連的節點（dead end)。
4. 從dead end的節點進行『返回追蹤』，找出『上一個』還有相連節點沒被做上記號的節點，然後在進行第二個步驟。
5. 反覆上述步驟，直到所有節點都做上了記號。

讓我們看看下面動圖來讓我們更了解這個流程：

有幾點特別提出來解釋一下：

• 當流程跑到節點Ｃ的時候，一開始原本是連線到節點Ａ，但是後來發現節點Ａ已經做過記號，表示在Output中已經有節點Ａ的紀錄了，因此才轉換成下一個節點Ｄ。（綠色虛線表示該連線對象已有紀錄）
• 當流程跑到節點Ｆ之後，因為節點Ｆ已經是不再有相連且無記號的節點，因此之後開始進行返回追蹤，直到找到節點Ｃ還有其他節點沒有記號，因此再從節點Ｃ去連下一個節點。

Breadth-First Search(BFS)

Breadth-First Search跟Depth-First Search一樣，也是會跑過所有的節點，一樣嘢是在跑過的節點上做記號，然後記錄順序，但是不同的地方是BFS是『分層』的概念去進行整個流程，整體流程如下：

1. 先決定一個起始節點，並將其做上記號。
2. 針對這個起始節點，依次紀錄所有的鄰居節點，並在這些節點上做記號。
3. 當對於起始節點的所有鄰居節點都記錄過後，再從第一個鄰居節點開始重複第二步驟。
4. 依序上述步驟反覆進行，直到所有節點都有記號。

再讓我們看看BFS的動圖來熟悉一下流程：

Depth-First Search和Breadth-First Search兩者都可以用來求出節點間的關聯性，而Breadth-First Search還可以用來尋找最短路徑。

DFS和BFS的時間複雜度

還記得第四天我們講抽象資料型別介紹Graph（忘記的可以點這裡複習)時，有提到Graph可以轉換成Adjacency Matrix和Adjacency List，而DFS和BFS在進行時針對的抽象資料型別就是Graph，所以這兩個演算法的時間複雜度也會因為所使用的資料結構（Adjacency Matrix和Adjacency List）而有所不同：

Ｖ： 節點(Node)數；Ｅ：連線(Edge)數

小結

• ＤＦＳ和ＢＦＳ用來解決與Graph相關的問題。
• ＤＦＳ是一個節點一個節點進行，而ＢＦＳ是一層節點一層節點進行。
• ＤＦＳ和ＢＦＳ的時間複雜度會依據所使用的資料結構Adjacency Matrix和Adjacency List而有所不同。

預告

明天我們將會介紹新的演算法類別-Decrease and Conquer及其一個演算法-Insertion Sort。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin

• ← 【舌尖上的演算法】Day8 -- Brute Force - Knapsack
• → 【舌尖上的演算法】Day10 -- Decrease and Conquer - Insertion Sort