目錄

一、BFS 和 DFS 的核心思想

1.?BFS（廣度優先搜索）

2.?DFS（深度優先搜索）

二、BFS 和 DFS 的對比

三、C++ 代碼實現

1. BFS 實現（鄰接表表示的無向圖）

2. DFS 實現（遞歸與迭代兩種方式）

四、關鍵細節說明

1. BFS 的關鍵點

2. DFS 的關鍵點

五、應用場景對比

六、總結

---

一、BFS 和 DFS 的核心思想

1.?BFS（廣度優先搜索）

• 核心思想：按“層級”逐層遍歷，先訪問離起點最近的節點，再逐步向外擴散。

• 類比：類似水波擴散，一層一層向外推進。

• 數據結構：隊列（FIFO）。

• 適用場景：最短路徑（未加權圖）、社交網絡層級關系、迷宮最短路徑。

2.?DFS（深度優先搜索）

• 核心思想：沿著一條路徑盡可能深入，直到無法繼續時回溯，嘗試其他分支。

• 類比：走迷宮時，遇到岔路選擇一條路走到頭，再返回選擇其他路。

• 數據結構：棧（LIFO）或遞歸調用棧。

• 適用場景：拓撲排序、連通性檢測、回溯問題（如八皇后）、圖的環路檢測。

---

二、BFS 和 DFS 的對比

特性	BFS	DFS
遍歷順序	層級遍歷（近到遠）	深度優先（一條路走到黑）
數據結構	隊列（先進先出）	棧（后進先出）或遞歸
空間復雜度	O(N)（最壞情況，如完全二叉樹）	O(H)（H為樹的高度，平衡樹時為 O(logN)）
時間復雜度	O(N + E)（N為節點數，E為邊數）	同左
最短路徑	天然支持（未加權圖）	需額外處理（如記錄路徑長度）
內存消耗	較高（存儲每一層節點）	較低（僅存儲當前路徑）
實現復雜度	簡單（固定隊列操作）	遞歸簡單，迭代需顯式棧

---

三、C++ 代碼實現

1. BFS 實現（鄰接表表示的無向圖）

#include <iostream>
#include <queue>
#include <vector>
using namespace std;void bfs(const vector<vector<int>>& graph, int start) {vector<bool> visited(graph.size(), false);queue<int> q;q.push(start);visited[start] = true;while (!q.empty()) {int node = q.front();q.pop();cout << node << " "; // 訪問節點// 遍歷當前節點的所有鄰居for (int neighbor : graph[node]) {if (!visited[neighbor]) {visited[neighbor] = true;q.push(neighbor);}}}
}// 示例圖結構
vector<vector<int>> graph = {{1, 2},     // 節點0的鄰居{0, 3, 4},  // 節點1的鄰居{0, 5, 6},  // 節點2的鄰居{1},        // 節點3的鄰居{1},        // 節點4的鄰居{2},        // 節點5的鄰居{2}         // 節點6的鄰居
};int main() {cout << "BFS遍歷結果: ";bfs(graph, 0); // 輸出: 0 1 2 3 4 5 6return 0;
}

2. DFS 實現（遞歸與迭代兩種方式）

// 遞歸實現
void dfsRecursive(const vector<vector<int>>& graph, int node, vector<bool>& visited) {visited[node] = true;cout << node << " "; // 訪問節點for (int neighbor : graph[node]) {if (!visited[neighbor]) {dfsRecursive(graph, neighbor, visited);}}
}// 迭代實現（顯式棧）
void dfsIterative(const vector<vector<int>>& graph, int start) {vector<bool> visited(graph.size(), false);stack<int> s;s.push(start);visited[start] = true;while (!s.empty()) {int node = s.top();s.pop();cout << node << " ";// 反向遍歷鄰居以保證與遞歸順序一致for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {if (!visited[*it]) {visited[*it] = true;s.push(*it);}}}
}int main() {cout << "DFS遞歸遍歷結果: ";vector<bool> visited(graph.size(), false);dfsRecursive(graph, 0, visited); // 輸出: 0 1 3 4 2 5 6cout << "\nDFS迭代遍歷結果: ";dfsIterative(graph, 0);          // 輸出: 0 1 3 4 2 5 6return 0;
}

---

四、關鍵細節說明

1. BFS 的關鍵點

• 隊列操作：每次從隊頭取出節點，并將未訪問的鄰居加入隊尾。

• 最短路徑：BFS 首次訪問到目標節點時，路徑一定是最短的（適用于未加權圖）。

• 空間復雜度：最壞情況下需存儲所有節點（如完全二叉樹最后一層）。

2. DFS 的關鍵點

• 遞歸與棧：遞歸隱式使用系統棧，迭代顯式使用棧。

• 遍歷順序：迭代實現中，若按正序訪問鄰居，結果可能與遞歸順序不同（需反向遍歷鄰居）。

• 應用場景：適合探索所有可能性（如回溯問題），但可能陷入深層分支無法及時返回。

---

五、應用場景對比

問題類型	推薦算法	原因
未加權圖最短路徑	BFS	天然支持最短路徑
圖的連通性檢測	DFS/BFS	二者均可快速遍歷所有連通節點
拓撲排序	DFS	天然支持后序遍歷的逆序
迷宮所有路徑	DFS	回溯特性適合探索所有可能路徑
社交網絡層級關系分析	BFS	按層遍歷符合實際場景
檢測環路	DFS	通過回溯標記路徑，容易檢測重復訪問

---

六、總結

• BFS?適合“廣度優先”問題，如最短路徑；DFS?適合“深度優先”問題，如回溯和連通性。

• 代碼實現：BFS 用隊列，DFS 用棧或遞歸，注意遍歷順序和空間消耗。

• 選擇依據：根據問題特性（如是否需要最短路徑、內存限制）選擇算法。