Graph theory圖論 DFS、BFS演算法的統整與比較

本篇文章將會著重在幾個圖論常用的演算法BFS 與 DFS 的統整與比較。

DFS 深度優先搜索: 先天具有一股腦往前探索，一條路走到底的性質。

適合的底層資料結構:

Stack 或者 Recursion function 遞迴函式呼叫(站在人的觀點，比較好寫)

利用Stack 和 Recursion function時對應建立call stack的Last in First out性質，來維持深度優先的探索順序。

適合的應用領域:

1. 尋找路徑的存在性(有一條路徑從起點走到終點即可)

例題:

Find if Path Exists in Graph — LeetCode

2. 在探索Tree/Binary tree相關的領域中，還有一個名字，叫做preorder前序/inorder中序/postorder後序 traversal，依照指定的順序拜訪整棵樹。

Binary Tree Preorder Traversal-Leetcode

Binary Tree Inorder Traversal-Leetcode

Binary Tree Postorder Traversal-Leetcode

3. 從樹根開始搜索到葉子節點，在這種題目中，其實DFS就是我們Single source path algorithm的模板，把Root視為探索的起點。

例如 Path sum系列的題目

Path Sum — LeetCode

Path Sum II — LeetCode

Path Sum III — LeetCode

4. 展開整個搜索空間(Search space/State space)的題目，常常結合回溯法backtracking一起使用，適合子集合、組合、直線排列...等類型的題目。

Subsets — Leetcode

Combinations — Leetcode

Permutations — Leetcode

BFS 廣度優先: 先天具有點播源擴散的性質，起點視為波源，由內往外一層一層擴散，抵達終點時的擴散層數就代表最短路徑。

適合的底層資料結構:

Queue 佇列，利用佇列First in First out的特性，來維持廣度優先 level by level探索的前後順序。

1. 無權重圖或者圖中權重默認相等的最短路徑

Shortest path in binary matrix -Leetcode

Shortest path to get all keys — Leetcode

2. 在探索Tree/Binary tree相關的領域中，還有一個名字，叫做Level-order traversal 逐層探索演算法。從第一層Root根接點，逐層探索到Leaf葉子節點 也是最深的那一層。

Binary Tree Level Order Traversal — Leetcode

Time Needed to Inform All Employees — LeetCode

3. 點波源擴散的模式，探索整張圖。也可以用這個性質來尋找起終點的路徑是否存在。

Find if Path Exists in Graph — LeetCode