1. BFS與DFS

1.1 BFS

DFS即Depth First Search，深度優先搜索。它是一種圖遍歷算法，它從一個起始點開始，逐層擴展搜索范圍，直到找到目標節點為止。

這種算法通常用于解決“最短路徑”問題，比如在迷宮中找到從起點到終點的最短路徑

• 首先，從起點開始，檢查所有與它相鄰的位置，也就是距離起點為1的位置
• 然后，繼續向外擴展，檢查所有距離起點為2的位置，以此類推，直到找到出口
  

我們發現每次搜索的位置都是距離當前節點最近的點。因此，BFS是具有最短路的性質的。在BFS中，可以使用隊列來存儲待搜索的節點。起始點首先加入隊列中，然后不斷從隊列中取出節點，檢查它是否是目標節點。如果不是，就將它的所有未被訪問過的鄰居加入隊列中。這樣，隊列中的節點總是按照它們距離起點的距離排序，先加入隊列的節點總是先被取出來搜索。

通過這種方式，BFS可以找到起點到目標節點的最短路徑。在實際應用中，BFS還可以用于拓撲排序、連通性檢測等問題的解決。

1.2 DFS

DFS即Depth First Search，深度優先搜索。它從一個起始點開始，一直往下走直到不能再走為止（簡單理解：一條路走到黑），然后返回到前一個節點，繼續探索它的其他分支，直到找到目標節點為止。這種算法通常用于解決“遍歷”問題，比如在樹中查找所有的葉子節點。

要理解DFS，也還可以想象自己在迷宮中尋找所有可行的路徑

• 首先，你會從起點開始，順著一條路一直走，直到你走到一個死胡同
• 再返回到前一個節點，繼續探索其他分支

在DFS中，你可以使用遞歸或棧來實現深度優先搜索。通過這種方式，DFS可以找到所有可行的路徑，或者在樹中查找所有的葉子節點。

在實際應用中，DFS還可以用于拓撲排序、連通性檢測等問題的解決。與BFS相比，DFS通常更適合處理深度優先的問題，而BFS更適合處理廣度優先的問題。

1.3 BFS與DFS的比較

如果分別用DFS 與 BFS 將二叉樹的所有結點遍歷一遍，那么它們遍歷結點的順序分別如下所示

接下來，讓我們先看看在二叉樹上進行 BFS 遍歷和 DFS 遍歷的代碼比較

（1）DFS 使用遞歸遍歷：

void dfs(TreeNode* root) 
{if (root == nullptr) {return;}// 依次遞歸遍歷它的左子樹和右子樹dfs(root->left);dfs(root->right);
}

（2）BFS 遍歷使用隊列相關的數據結構：

void bfs(TreeNode* root) 
{// 創建一個隊列queue<TreeNode*> q;q.push(root);while (!q.empty()) {// 在每次循環中，使用 q.front() 獲取隊頭節點，并將其出隊TreeNode* node = q.front();q.pop();// 然后將下一層的節點加入隊列中// 檢查這個節點的左右子節點是否為空，如果不為空，就將它們加入隊列中if (node->left != nullptr) {q.push(node->left);}if (node->right != nullptr){q.push(node->right);}}
}

參考博客: https://blog.csdn.net/v_JULY_v/article/details/6111353