BFS 與 DFS — 廣度優先與深度優先搜尋完整教學 | 資料結構與演算法
2026/07/09
BFS（廣度優先搜尋） 與 DFS（深度優先搜尋） 是圖論中最核心的兩種遍歷策略。BFS 如同水波向外擴散，逐層推進，天然找到無權圖的最短路徑；DFS 如同走迷宮，沿一條路徑深入到底再回溯，自然揭示圖的拓撲結構。掌握這兩種思想，等於拿到了圖演算法的入場券。
前言
想像你被困在一座迷宮中。面對眼前的岔路口，你有兩種基本策略：
策略一：從起點出發，先把所有距離你一步之遙的路口都探索完，再走到兩步遠的地方，依此類推，像漣漪一樣向外一圈圈擴散——這是 BFS（Breadth-First Search，廣度優先搜尋）。
策略二：從起點出發，選一條路一直走到底（死路或出口），走不通了再原路返回，換另一條路繼續深入——這是 DFS（Depth-First Search，深度優先搜尋）。
這兩種策略看似簡單，卻能解決圖論中絕大多數問題：最短路徑、連通分量、環偵測、二分圖判定、島嶼計數……
讀完本文，你將能夠：
- 理解 BFS 與 DFS 的核心思想差異，以及各自的最佳應用場景
- 掌握 Queue（佇列） 驅動 BFS、Stack（堆疊）／遞迴驅動 DFS 的底層機制
- 熟練
visited陣列的正確使用時機（入隊時 vs 出隊時） - 用 TypeScript 實作 BFS、DFS 通用模板，以及最短路徑、連通分量、二分圖、島嶼問題
- 對照 C++ 的慣用寫法
- 解析 5 道 LeetCode 精選題（200、994、130、785、207）
核心概念
BFS：波紋擴散
BFS 如同石頭投入水中的漣漪，從起點向外一圈圈擴散，距離相同的節點在同一「波紋圈」中同時被訪問。
起點 S，BFS 擴散順序：
S ← 第 0 層（距離 0）
/|\
/ | \
1 2 3 ← 第 1 層（距離 1）
/| |
4 5 6 ← 第 2 層（距離 2）
|
7 ← 第 3 層（距離 3）
訪問順序：S → 1 → 2 → 3 → 4 → 5 → 6 → 7
關鍵工具：Queue（先進先出）
enqueue S
dequeue S → enqueue 1, 2, 3
dequeue 1 → enqueue 4, 5
dequeue 2 → （無子節點）
dequeue 3 → enqueue 6
...
BFS 的關鍵性質：第一次到達某節點時，所走的路徑必定是邊數最少的路徑（最短路徑）。原因很直覺：BFS 按距離由近到遠擴展，遠的節點不可能比近的節點先被訪問。
DFS：深入探索
DFS 如同走迷宮：沿著一條路走到底（死路或終點），再回頭嘗試其他分支。
同一張圖，DFS 探索順序（鄰居按數字升序）：
S ← 進入
/|\
/ | \
1 2 3
/| |
4 5 6
|
7
訪問順序（前序）：S → 1 → 4 → 5 → 7 → 2 → 3 → 6
遞迴呼叫棧：
call(S) → call(1) → call(4) → return
→ call(5) → call(7) → return
→ call(2) → return
→ call(3) → call(6) → return
DFS 的關鍵性質：可以訪問所有可達節點，但路徑長度不保證最短。DFS 的遞迴天性讓它天然擅長發現「結構」——前序遍歷可用於路徑搜尋，後序遍歷可用於依賴收集（拓撲排序）。
BFS vs DFS 核心差異
| 特性 | BFS | DFS |
|---|---|---|
| 資料結構 | Queue（先進先出） | Stack / 遞迴呼叫棧 |
| 探索順序 | 按層（距離）由近到遠 | 按深度，一條路走到底 |
| 最短路徑 | 保證（無權圖） | 不保證 |
| 空間複雜度 | O(V)，最壞整層節點入 Queue | O(V)，最壞退化鏈結串列 |
| 時間複雜度 | O(V + E) | O(V + E) |
| 適合問題 | 最短路徑、層級、最近鄰 | 連通性、環路、拓撲、路徑搜尋 |
| 天然性質 | 層序（Level Order） | 前序 / 後序遍歷 |
visited 的正確時機
一個常見的陷阱：應該在節點入 Queue（或 Stack）時就標記 visited，而非出隊時。
若在出隊時才標記，同一個節點可能被它的多個鄰居各自加入一次，導致重複處理。正確做法：
錯誤（出隊時標記）：同一節點可能被加入 Queue 多次
正確（入隊時標記）：節點最多只被加入 Queue 一次
JS/TS 實作
BFS 通用模板（含層級追蹤）
BFS 的標準框架非常固定，只需要一個 Queue 和一個 visited 集合：
// ─── BFS 模板：圖的廣度優先遍歷（含距離資訊）────────────────────────────────
function bfsGraph(
start: number,
adjList: Map<number, number[]>
): { order: number[]; distance: Map<number, number> } {
const visited = new Set<number>();
const distance = new Map<number, number>();
const order: number[] = [];
// 初始化：起點加入 Queue，距離為 0
const queue: number[] = [start];
visited.add(start);
distance.set(start, 0);
while (queue.length > 0) {
// 注意：shift() 是 O(n)；大規模場景請用索引指標代替
const curr = queue.shift()!;
order.push(curr);
for (const neighbor of (adjList.get(curr) ?? [])) {
if (!visited.has(neighbor)) {
visited.add(neighbor); // 入隊時標記！
distance.set(neighbor, distance.get(curr)! + 1);
queue.push(neighbor);
}
}
}
return { order, distance };
}
當需要按層處理（例如二元樹層序遍歷、按距離分組）時，使用「固定層大小」技巧：
// ─── BFS 模板：逐層處理（Level-by-Level）──────────────────────────────────
function bfsLevelOrder(
start: number,
adjList: Map<number, number[]>
): number[][] {
const visited = new Set<number>([start]);
const levels: number[][] = [];
let currentLevel = [start];
while (currentLevel.length > 0) {
levels.push(currentLevel);
const nextLevel: number[] = [];
for (const curr of currentLevel) {
for (const neighbor of (adjList.get(curr) ?? [])) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
nextLevel.push(neighbor);
}
}
}
currentLevel = nextLevel;
}
return levels;
}
// 使用範例：levels[0] = [start]，levels[1] = 距離1的節點，以此類推
DFS 通用模板（遞迴 + 迭代）
// ─── DFS 模板：遞迴版（程式碼簡潔，適合多數場景）────────────────────────────
function dfsRecursive(
start: number,
adjList: Map<number, number[]>
): number[] {
const visited = new Set<number>();
const order: number[] = [];
function dfs(node: number): void {
visited.add(node);
order.push(node); // 前序：進入時記錄
for (const neighbor of (adjList.get(node) ?? [])) {
if (!visited.has(neighbor)) {
dfs(neighbor);
}
}
// 後序記錄：在此處 order.push(node)（可用於拓撲排序）
}
dfs(start);
return order;
}
// ─── DFS 模板：迭代版（顯式 Stack，避免呼叫棧溢位）──────────────────────────
function dfsIterative(
start: number,
adjList: Map<number, number[]>
): number[] {
const visited = new Set<number>();
const order: number[] = [];
const stack: number[] = [start];
while (stack.length > 0) {
const curr = stack.pop()!;
if (visited.has(curr)) continue; // 有向圖可能多次入棧
visited.add(curr);
order.push(curr);
// Stack 後進先出，若需按升序訪問鄰居，需反序壓入
const neighbors = adjList.get(curr) ?? [];
for (let i = neighbors.length - 1; i >= 0; i--) {
if (!visited.has(neighbors[i])) {
stack.push(neighbors[i]);
}
}
}
return order;
}
無權圖最短路徑（BFS）
BFS 是無權圖最短路徑的最優解。Dijkstra 演算法可看作 BFS 的加權版延伸：
// ─── 無權圖 BFS 最短路徑 ───────────────────────────────────────────────────
function shortestPath(
start: number,
end: number,
adjList: Map<number, number[]>
): number {
if (start === end) return 0;
const visited = new Set<number>([start]);
const queue: [number, number][] = [[start, 0]]; // [節點, 距離]
let head = 0; // 用索引指標代替 shift()，避免 O(n) 成本
while (head < queue.length) {
const [curr, dist] = queue[head++];
for (const neighbor of (adjList.get(curr) ?? [])) {
if (neighbor === end) return dist + 1; // 提前終止
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push([neighbor, dist + 1]);
}
}
}
return -1; // 不可達
}
連通分量計數（DFS）
遍歷所有頂點，每次遇到未訪問的節點就啟動一次 DFS，計數加一：
// ─── 連通分量計數（無向圖）────────────────────────────────────────────────
function countConnectedComponents(
n: number,
edges: number[][]
): number {
// 建構鄰接表
const adj = new Map<number, number[]>();
for (let i = 0; i < n; i++) adj.set(i, []);
for (const [u, v] of edges) {
adj.get(u)!.push(v);
adj.get(v)!.push(u);
}
const visited = new Set<number>();
let components = 0;
function dfs(node: number): void {
visited.add(node);
for (const neighbor of adj.get(node)!) {
if (!visited.has(neighbor)) dfs(neighbor);
}
}
for (let i = 0; i < n; i++) {
if (!visited.has(i)) {
dfs(i); // 從未訪問的頂點啟動新的 DFS，代表新的連通分量
components++;
}
}
return components;
}
// 測試：5 個頂點，邊 [[0,1],[1,2],[3,4]]
// 連通分量：{0,1,2} 和 {3,4}，共 2 個
console.log(countConnectedComponents(5, [[0,1],[1,2],[3,4]])); // 2
環偵測（DFS，有向圖）
無向圖的環偵測只需追蹤 visited。有向圖需要三種狀態：未訪問（0）、訪問中（1，在當前 DFS 路徑上）、已完成（2）。
// ─── 有向圖環偵測（DFS，三色標記）────────────────────────────────────────
function hasCycle(n: number, edges: number[][]): boolean {
const adj: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) adj[u].push(v);
const state = new Array(n).fill(0); // 0=未訪問, 1=訪問中, 2=已完成
function dfs(node: number): boolean {
state[node] = 1; // 標記為「訪問中」
for (const neighbor of adj[node]) {
if (state[neighbor] === 1) return true; // 遇到「訪問中」的節點 = 有環
if (state[neighbor] === 0 && dfs(neighbor)) return true;
}
state[node] = 2; // 標記為「已完成」
return false;
}
for (let i = 0; i < n; i++) {
if (state[i] === 0 && dfs(i)) return true;
}
return false;
}
// 陷阱：若只用 visited/unvisited（兩色），跨邊會被誤判為環
二分圖判定（BFS 染色）
二分圖（Bipartite Graph）：可將頂點分為兩組，所有邊都在組間（無組內邊）。等價條件：圖中不存在奇數長度的環。判定方法：BFS 染色，若相鄰兩節點顏色相同則非二分圖。
// ─── 二分圖（Bipartite Graph）判定 ───────────────────────────────────────
function isBipartite(n: number, graph: number[][]): boolean {
// graph[i] = 頂點 i 的所有鄰居（LeetCode 785 的輸入格式）
const color = new Array(n).fill(-1); // -1 = 未染色，0 = 紅，1 = 藍
for (let start = 0; start < n; start++) {
if (color[start] !== -1) continue; // 已處理過的連通分量跳過
const queue = [start];
color[start] = 0; // 起點染為紅色
while (queue.length > 0) {
const curr = queue.shift()!;
for (const neighbor of graph[curr]) {
if (color[neighbor] === -1) {
// 未染色：染成對立顏色
color[neighbor] = 1 - color[curr];
queue.push(neighbor);
} else if (color[neighbor] === color[curr]) {
// 相鄰節點顏色相同：存在奇數環，非二分圖
return false;
}
}
}
}
return true;
}
// 測試：
console.log(isBipartite(4, [[1,3],[0,2],[1,3],[0,2]])); // true（四邊形）
console.log(isBipartite(4, [[1,2,3],[0,2],[0,1,3],[0,2]])); // false（有奇數環）
網格 BFS / DFS（島嶼問題通用框架）
網格問題是 BFS/DFS 的高頻應用。四方向移動是標準模板：
// ─── 網格四方向定義 ────────────────────────────────────────────────────────
const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]] as const; // 上下左右
type Grid = string[][];
// ─── 網格 DFS（遞迴，原地修改標記已訪問）──────────────────────────────────
function dfsGrid(grid: Grid, r: number, c: number): void {
const rows = grid.length;
const cols = grid[0].length;
// 越界或非陸地（'1'）則返回
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return;
grid[r][c] = '#'; // 原地標記為已訪問（避免額外 visited 陣列）
for (const [dr, dc] of DIRS) {
dfsGrid(grid, r + dr, c + dc);
}
}
// ─── 網格 BFS ─────────────────────────────────────────────────────────────
function bfsGrid(grid: Grid, startR: number, startC: number): void {
const rows = grid.length;
const cols = grid[0].length;
grid[startR][startC] = '#'; // 入隊前立即標記
const queue: [number, number][] = [[startR, startC]];
let head = 0;
while (head < queue.length) {
const [r, c] = queue[head++];
for (const [dr, dc] of DIRS) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
grid[nr][nc] = '#'; // 入隊時標記，避免重複
queue.push([nr, nc]);
}
}
}
}
C++ 對照
C++ 的標準庫提供 std::queue（BFS）和 std::stack（迭代 DFS），以及 std::function 可以方便地定義遞迴 lambda：
#include <queue>
#include <stack>
#include <vector>
#include <functional>
// ─── BFS（含層序）──────────────────────────────────────────────────────────
std::vector<std::vector<int>> bfsLevelOrder(
int start,
const std::vector<std::vector<int>>& adj) {
int n = static_cast<int>(adj.size());
std::vector<bool> visited(n, false);
std::vector<std::vector<int>> levels;
std::queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
std::vector<int> level;
int sz = static_cast<int>(q.size()); // 固定當前層大小
for (int i = 0; i < sz; ++i) {
int curr = q.front(); q.pop();
level.push_back(curr);
for (int neighbor : adj[curr]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
levels.push_back(std::move(level));
}
return levels;
}
// ─── DFS（遞迴版，使用 lambda）────────────────────────────────────────────
std::vector<int> dfsRecursive(int start, const std::vector<std::vector<int>>& adj) {
std::vector<bool> visited(adj.size(), false);
std::vector<int> order;
std::function<void(int)> dfs = [&](int node) {
visited[node] = true;
order.push_back(node);
for (int neighbor : adj[node]) {
if (!visited[neighbor]) dfs(neighbor);
}
};
dfs(start);
return order;
}
// ─── 連通分量計數 ─────────────────────────────────────────────────────────
int countComponents(int n, const std::vector<std::vector<int>>& edges) {
std::vector<std::vector<int>> adj(n);
for (const auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
std::vector<bool> visited(n, false);
int count = 0;
std::function<void(int)> dfs = [&](int node) {
visited[node] = true;
for (int nb : adj[node]) {
if (!visited[nb]) dfs(nb);
}
};
for (int i = 0; i < n; ++i) {
if (!visited[i]) { dfs(i); ++count; }
}
return count;
}
// ─── 二分圖判定（BFS 染色）───────────────────────────────────────────────
bool isBipartite(int n, const std::vector<std::vector<int>>& graph) {
std::vector<int> color(n, -1);
for (int start = 0; start < n; ++start) {
if (color[start] != -1) continue;
std::queue<int> q;
q.push(start);
color[start] = 0;
while (!q.empty()) {
int curr = q.front(); q.pop();
for (int nb : graph[curr]) {
if (color[nb] == -1) {
color[nb] = 1 - color[curr];
q.push(nb);
} else if (color[nb] == color[curr]) {
return false;
}
}
}
}
return true;
}
// ─── 網格 DFS（LeetCode 200 島嶼問題）───────────────────────────────────
constexpr int DIRS[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
void dfsGrid(std::vector<std::vector<char>>& grid, int r, int c) {
int rows = static_cast<int>(grid.size());
int cols = static_cast<int>(grid[0].size());
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return;
grid[r][c] = '#';
for (const auto& d : DIRS) {
dfsGrid(grid, r + d[0], c + d[1]);
}
}
複雜度分析
| 操作 | 時間複雜度 | 空間複雜度 | 備註 |
|---|---|---|---|
| 圖 BFS / DFS | O(V + E) | O(V) | V = 頂點數，E = 邊數 |
| 網格 BFS / DFS | O(m × n) | O(m × n) | m × n = 網格大小 |
| 連通分量計數 | O(V + E) | O(V) | 逐頂點啟動 BFS/DFS |
| 二分圖判定 | O(V + E) | O(V) | BFS 染色 |
| 無權圖最短路徑（BFS） | O(V + E) | O(V) | 保證最短 |
| 有向圖環偵測（DFS） | O(V + E) | O(V) | 三色標記 |
JavaScript 注意事項：Array.shift() 是 O(n) 操作，在大規模 BFS 中應改用索引指標（let head = 0; const curr = queue[head++]），將整體複雜度維持在 O(V + E)。
變體與延伸
多源 BFS（Multi-Source BFS）
當問題有多個起點時（如「所有腐爛橘子同時開始蔓延」），將所有起點同時加入 Queue，作為「第 0 層」一起展開。這是 LeetCode 994 的核心思路：
// 多源 BFS 初始化
const queue: [number, number][] = [];
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === 2) queue.push([r, c]); // 所有起點一起入隊
}
}
// 之後正常 BFS，queue.length 自然代表「當前層」所有擴散前沿
錯誤做法：對每個起點分別執行獨立的 BFS，無法正確模擬「同時擴散」的時間計算。
雙向 BFS（Bidirectional BFS）
從起點和終點各維護一個 frontier，每次擴展較小的那個。當兩個 frontier 相交時，即找到路徑。這能將搜尋空間從 O(b^d) 降低到 O(b^(d/2))（b = 分支因子，d = 深度），適用於起點和終點都已知的最短路徑問題（如 LeetCode 127 Word Ladder）。
DFS 時間戳記
在 DFS 中記錄每個節點的進入時間（discovery time）和離開時間（finish time），可以用來：
- 判斷哪些邊是樹邊、後向邊（發現環）、前向邊、跨邊
- 實作拓撲排序（離開時間倒序即為拓撲序）
- 找強連通分量（Kosaraju 演算法）
面試考點：BFS vs DFS 如何選擇
實戰中如何快速決策？以下是選擇框架：
選 BFS 的時機：
- 需要最短路徑（無權圖，邊數最少）
- 需要層序遍歷（按距離分組）
- 多源擴散問題（腐爛橘子、地圖染色等）
- 圖比較淺而寬，DFS 可能遞迴過深
選 DFS 的時機：
- 判斷連通性（是否可達）
- 找到所有路徑（回溯搜尋）
- 環偵測（有向圖三色標記）
- 拓撲排序（後序 DFS）
- 圖比較深而窄，BFS 可能 Queue 過大
- 網格問題中「淹沒整個島嶼」（直覺上 DFS 更簡潔）
兩者皆可的時機：
- 計算連通分量數（BFS/DFS 均可，選程式碼更簡潔的）
- 網格的可達性問題
- 二分圖判定（BFS 染色更直覺，DFS 也可以）
LeetCode 精選練習
LeetCode 200 — Number of Islands（M）
每遇到未訪問的 '1' 就啟動 DFS 淹沒整個島嶼，計數加一。
// 思路：DFS 計算連通分量數（陸地）
// 時間：O(m × n)，空間：O(m × n)（遞迴深度）
function numIslands(grid: string[][]): number {
if (!grid.length) return 0;
const rows = grid.length;
const cols = grid[0].length;
let islands = 0;
const g = grid.map(row => [...row]); // 複製，避免修改輸入
function dfs(r: number, c: number): void {
if (r < 0 || r >= rows || c < 0 || c >= cols || g[r][c] !== '1') return;
g[r][c] = '#'; // 淹沒：標記為已訪問
dfs(r - 1, c); dfs(r + 1, c); dfs(r, c - 1); dfs(r, c + 1);
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (g[r][c] === '1') {
dfs(r, c);
islands++;
}
}
}
return islands;
}
// 測試
console.log(numIslands([
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1'],
])); // 3
LeetCode 994 — Rotting Oranges（M）
多源 BFS，所有腐爛橘子作為起點，BFS 的層數即為所需時間：
// 思路：多源 BFS，BFS 層數 = 時間
// 時間：O(m × n)，空間：O(m × n)
function orangesRotting(grid: number[][]): number {
const rows = grid.length;
const cols = grid[0].length;
const queue: [number, number][] = [];
let fresh = 0;
// 初始化：收集所有腐爛橘子，計算新鮮橘子數
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === 2) queue.push([r, c]);
else if (grid[r][c] === 1) fresh++;
}
}
if (fresh === 0) return 0; // 沒有新鮮橘子
const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
let minutes = 0;
let head = 0; // 索引指標，避免 shift() 的 O(n) 成本
while (head < queue.length) {
minutes++;
const levelSize = queue.length - head; // 固定當前層大小
for (let i = 0; i < levelSize; i++) {
const [r, c] = queue[head++];
for (const [dr, dc] of dirs) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
grid[nr][nc] = 2;
fresh--;
queue.push([nr, nc]);
}
}
}
}
// minutes - 1：最後一輪進入 while 時 minutes 已多加一次
return fresh === 0 ? minutes - 1 : -1;
}
// 測試
console.log(orangesRotting([[2,1,1],[1,1,0],[0,1,1]])); // 4
console.log(orangesRotting([[0,2]])); // 0（無新鮮橘子）
console.log(orangesRotting([[2,1,1],[0,1,1],[1,0,1]])); // -1（孤立橘子）
LeetCode 130 — Surrounded Regions（M）
逆向 DFS：從邊界的 'O' 出發標記「安全」節點，其餘 'O' 改為 'X'：
// 思路：反向 DFS，邊界連通的 O 不填充
// 時間：O(m × n)，空間：O(m × n)
function solve(board: string[][]): void {
const rows = board.length;
const cols = board[0].length;
function dfs(r: number, c: number): void {
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== 'O') return;
board[r][c] = 'S'; // 暫時標記為「安全」
dfs(r - 1, c); dfs(r + 1, c); dfs(r, c - 1); dfs(r, c + 1);
}
// 1. 從四邊的 O 出發，標記所有安全的 O
for (let r = 0; r < rows; r++) {
if (board[r][0] === 'O') dfs(r, 0);
if (board[r][cols - 1] === 'O') dfs(r, cols - 1);
}
for (let c = 0; c < cols; c++) {
if (board[0][c] === 'O') dfs(0, c);
if (board[rows - 1][c] === 'O') dfs(rows - 1, c);
}
// 2. 最終轉換：O → X（被包圍），S → O（安全還原）
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (board[r][c] === 'O') board[r][c] = 'X';
else if (board[r][c] === 'S') board[r][c] = 'O';
}
}
}
LeetCode 785 — Is Graph Bipartite?（M）
BFS 染色判定二分圖：
// 思路：BFS 染色，相鄰節點必須顏色不同
// 時間：O(V + E)，空間：O(V)
function isGraphBipartite(graph: number[][]): boolean {
const n = graph.length;
const color = new Array(n).fill(-1);
for (let start = 0; start < n; start++) {
if (color[start] !== -1) continue;
const queue = [start];
color[start] = 0;
while (queue.length > 0) {
const curr = queue.shift()!;
for (const neighbor of graph[curr]) {
if (color[neighbor] === -1) {
color[neighbor] = 1 - color[curr];
queue.push(neighbor);
} else if (color[neighbor] === color[curr]) {
return false; // 相鄰同色，不是二分圖
}
}
}
}
return true;
}
LeetCode 207 — Course Schedule（M）
有向圖環偵測，用 DFS 三色標記。若圖有環，則無法完成所有課程：
// 思路：DFS 有向圖環偵測（三色標記）
// 時間：O(V + E)，空間：O(V)
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
const adj: number[][] = Array.from({ length: numCourses }, () => []);
for (const [course, pre] of prerequisites) {
adj[pre].push(course); // pre → course（修完 pre 才能修 course）
}
const state = new Array(numCourses).fill(0); // 0=未訪問, 1=訪問中, 2=已完成
function dfs(node: number): boolean {
if (state[node] === 1) return true; // 發現環
if (state[node] === 2) return false; // 已安全處理
state[node] = 1;
for (const neighbor of adj[node]) {
if (dfs(neighbor)) return true; // 子樹中有環
}
state[node] = 2;
return false;
}
for (let i = 0; i < numCourses; i++) {
if (state[i] === 0 && dfs(i)) return false;
}
return true; // 無環，可完成所有課程
}
// 測試
console.log(canFinish(2, [[1,0]])); // true（0→1，無環）
console.log(canFinish(2, [[1,0],[0,1]])); // false（0→1→0，有環）
常見陷阱
BFS 使用
shift()效能問題：Array.shift()是 O(n)，在大規模 BFS 中讓整體複雜度退化為 O(V²)。解法：使用索引指標let head = 0; const curr = queue[head++]。有向圖環偵測只用兩色：只有 visited/unvisited 時，跨邊（Cross Edge）會被誤判為環。必須用三色：未訪問（0）、訪問中（1）、已完成（2）。
入隊後才標記 visited：網格 BFS 中若在出隊時標記，同一格子可能被多個鄰居各加入一次，導致重複處理和時間複雜度退化。應在入隊瞬間標記。
多源 BFS 初始化錯誤：不應對每個起點分別執行獨立 BFS，所有起點需在第一輪就全部加入 Queue，才能正確計算「同時擴散」的時間。
DFS 遞迴深度超限：大型網格（如 300×300）的 DFS 可能觸發呼叫棧溢位。解法：改用迭代 DFS（顯式 Stack）。
層級計數錯誤：使用「在每次 while 迭代前固定
queue.length」來分隔層級是唯一可靠的方法，動態讀取queue.length會把新入隊節點誤算入當前層。
總結
BFS 和 DFS 是圖論的兩塊基石，時間複雜度都是 O(V + E)，但應用場景截然不同：
- BFS：佇列驅動，逐層擴展，保證無權圖最短路徑，適合層序遍歷和多源擴散
- DFS：堆疊（或遞迴）驅動，深入到底再回溯，適合路徑搜尋、環偵測、拓撲排序
兩者的底層框架幾乎一樣——只是把 Queue 換成 Stack。正確掌握 visited 標記時機、多源 BFS 初始化、有向圖三色標記這三個細節，就能應對絕大多數面試題。
希望這篇文章能幫助你深入理解圖的遍歷策略。下一篇將進入最短路徑演算法，包括 Dijkstra（加權圖單源最短路徑）和 Bellman-Ford（處理負權邊），是 BFS 最自然的延伸！
上一篇：圖的表示法 — 鄰接矩陣、鄰接串列與邊串列