BFS和DFS
BFS（廣度優先搜尋）
廣度優先搜尋（Breadth-First Search，BFS），是一種逐層往外擴展的搜尋演算法，用 佇列（Queue） 實現。
簡單來說，其搜尋過程和 “湖面丟進一塊石頭激起層層漣漪” 類似 —— 先把離起點最近的點全部走完，再走下一層。
適用時機
- 找無權圖的最短路徑：因為一層一層往外擴，第一次碰到目標時的層數就是最短距離（搜到即最優解）。
- 二元樹的層序走訪（Level-order Traversal）。
- 找「最少幾步」這類問題。
JS 範例（用 Queue）
// 圖用 adjacency list 表示
function bfs(graph, start) {
const visited = new Set([start]);
const queue = [start]; // 用陣列當佇列
const result = [];
while (queue.length > 0) {
const node = queue.shift(); // 從隊頭取出
result.push(node);
for (const next of graph[node]) {
if (!visited.has(next)) {
visited.add(next); // 入隊時就標記，避免重複入隊
queue.push(next); // 加到隊尾
}
}
}
return result;
}
Array.shift() 是 O(n)，資料量大時佇列會變慢；要嚴謹可改用 head 指標或雙端佇列（deque）避免每次搬移整個陣列。
複雜度
- 時間：O(V + E)，V 為節點數、E 為邊數（每個節點與每條邊各處理一次）。
- 空間：O(V)，最壞情況佇列要存下同一層的所有節點，寬圖時可能很大。
DFS（深度優先搜尋）
深度優先搜尋（Depth-First Search，DFS），是一種沿著一條路走到底才回頭的搜尋演算法，可用 遞迴（隱式呼叫堆疊）或 明確的堆疊（Stack） 實現。
簡單來說，其搜尋過程和 “不撞南牆不回頭” 類似 —— 一個方向能走多深就走多深，走不下去才回溯換方向。
適用時機
- 找所有解 / 是否存在路徑（連通性、是否成環）。
- 二元樹的前序 / 中序 / 後序走訪。
- 拓樸排序、回溯（backtracking）類問題（排列組合、N 皇后等）。
- 空間效率通常比 BFS 好，但找到的不保證是最短路徑。
JS 範例（遞迴版）
function dfs(graph, start, visited = new Set(), result = []) {
visited.add(start);
result.push(start);
for (const next of graph[start]) {
if (!visited.has(next)) {
dfs(graph, next, visited, result);
}
}
return result;
}
JS 範例（迭代版，用 Stack）
function dfsIterative(graph, start) {
const visited = new Set();
const stack = [start];
const result = [];
while (stack.length > 0) {
const node = stack.pop(); // 從堆疊頂取出（後進先出）
if (visited.has(node)) continue;
visited.add(node);
result.push(node);
for (const next of graph[node]) {
if (!visited.has(next)) {
stack.push(next);
}
}
}
return result;
}
遞迴版本質上就是用「函式呼叫堆疊」取代了顯式 Stack。圖很深時遞迴可能 stack overflow，這時改用迭代版較安全。
複雜度
- 時間：O(V + E)，與 BFS 相同。
- 空間：O(V)，遞迴深度（或堆疊大小）最壞為節點數；深而窄的圖通常比 BFS 省空間。
BFS vs DFS 快速比較
| 面向 | BFS | DFS |
|---|---|---|
| 資料結構 | 佇列（Queue，FIFO） | 堆疊（Stack，LIFO）/ 遞迴 |
| 走訪順序 | 逐層往外 | 沿一路走到底再回溯 |
| 最短路徑（無權圖） | ✅ 搜到即最優 | ❌ 不保證最短 |
| 適合 | 最短路徑、層序 | 找所有解、連通性、回溯 |
| 時間複雜度 | O(V + E) | O(V + E) |
| 空間複雜度 | O(V)（寬圖大） | O(V)（深圖大） |