创见博客
图的深度优先遍历与广度优先遍历：同一个图，两种走法
七崽爱吃小饼干2026/09/16阅读 0

假设有一张社交关系图，A 认识 B，B 认识 C，A 也直接认识 C。现在要从 A 出发找到 C：

  • 深度优先（DFS）会沿着一条路一直走到底：A → B → C，找到就停。
  • 广度优先（BFS）会先看完 A 的所有直接朋友：B 和 C，一轮就命中。

同一张图，两种遍历给出了不同的路径和顺序。搞清它们的差别，决定了你在写「连通性判断」「无权图最短路」「拓扑排序」时选哪个。

一、先确定图的表示

遍历的效率几乎完全取决于图怎么存。

邻接表：graph[v] 存 v 的所有邻居。稀疏图首选，遍历所有边是 O(E)。

ts
const graph: Record<number, number[]> = {
  0: [1, 2],
  1: [0, 3],
  2: [0, 3],
  3: [1, 2, 4],
  4: [3],
};

邻接矩阵：matrix[i][j] = 1 表示有边。查两点是否相邻是 O(1)，但要扫一整行是 O(V)，总遍历成本 O(V²)，只适合稠密图。

下面统一用邻接表，两者遍历的「骨架」是一样的。

二、深度优先遍历（DFS）

DFS 的思想是「一条路走到黑，走不动再回头」。递归写法最直观：

ts
function dfs(
  graph: Record<number, number[]>,
  node: number,
  visited: Set<number> = new Set(),
): void {
  visited.add(node);
  console.log(node); // 访问

  for (const next of graph[node] ?? []) {
    if (!visited.has(next)) {
      dfs(graph, next, visited);
    }
  }
}

dfs(graph, 0); // 0 1 3 2 4

递归天然用调用栈保存了「回退点」，所以代码很短。但图可能很深，深递归会把 JS 调用栈压爆。这时改成显式栈的迭代版：

ts
function dfsIterative(
  graph: Record<number, number[]>,
  start: number,
): void {
  const visited = new Set<number>();
  const stack = [start];

  while (stack.length) {
    const node = stack.pop()!;
    if (visited.has(node)) continue; // 可能被重复压栈，出栈时去重
    visited.add(node);
    console.log(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) stack.push(next);
    }
  }
}

一个容易踩的坑：递归版和迭代版、甚至迭代版不同的压栈顺序，都会产生不同的访问顺序。遍历顺序本身不是唯一的，别把某个顺序写死进测试用例。要想让迭代版和递归版顺序一致，压栈时要反着压。

三、广度优先遍历（BFS）

BFS 用队列，一层一层向外扩散：

ts
function bfs(
  graph: Record<number, number[]>,
  start: number,
): Map<number, number> {
  const visited = new Set<number>([start]);
  const queue: number[] = [start];
  const dist = new Map<number, number>([[start, 0]]);
  let head = 0; // 用下标代替 shift()，避免 O(n) 出队

  while (head < queue.length) {
    const node = queue[head++];

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        visited.add(next); // 入队时就标记，见下方易错点
        dist.set(next, dist.get(node)! + 1);
        queue.push(next);
      }
    }
  }

  return dist;
}

BFS 会按「距离起点的边数」分层访问，所以顺带就能求出无权图的最短路径长度——这正是 DFS 做不到的。

四、两个必须记牢的易错点

1. BFS 要在「入队时」标记 visited，不能等「出队时」。 如果在出队时才标记，同一个节点可能被多个邻居重复入队，队列膨胀，最坏情况从 O(V+E) 劣化。DFS 因为有栈的去重（或天然递归）影响较小，但同样建议访问即标记。

2. 非连通图要遍历所有起点。 从单个点出发只会访问到它所在的连通分量。要覆盖整张图，得对每个未访问节点再启动一次遍历：

ts
function countComponents(
  n: number,
  graph: Record<number, number[]>,
): number {
  const visited = new Set<number>();
  let count = 0;

  for (let v = 0; v < n; v++) {
    if (!visited.has(v)) {
      count++;
      dfs(graph, v, visited); // 这里换成 bfs 结果一样
    }
  }

  return count;
}

求连通分量时，DFS 和 BFS 完全等价，选哪个都行。

五、复杂度

用邻接表：时间 O(V + E)，空间 O(V)（visited + 栈/队列），递归 DFS 还要加上最深路径的栈空间。

用邻接矩阵：时间 O(V²)，因为每个节点都要扫一整行。

所以「遍历用哪种」不取决于 DFS/BFS，而取决于图的存储方式。

六、什么时候用哪个

问题首选原因
无权图最短路、最少步数BFS逐层扩散，首次到达即最短
层次遍历、按距离分层BFS天然按层处理
判断二分图BFS按层染色
连通分量 / 可达性都行结果一致
环检测（有向图）DFS用三色标记（白/灰/黑）判断回边
拓扑排序都行DFS 后序反转，或 BFS（Kahn 算法）
桥、割点、强连通分量DFSTarjan / Kosaraju 都基于 DFS 的访问序
回溯、枚举路径DFS沿路径深入与撤销天然匹配

一句话选型口诀：要找「最短/最近/分层」用 BFS；要处理「结构/顺序/环/连通性」用 DFS。

七、一个关键区别的直觉

为什么 BFS 能求无权最短路，DFS 不能？

BFS 是「一圈一圈」推进的：第 k 层节点一定在第 k+1 层之前全部处理完，所以第一次到达某节点时，走过的边数必然是全局最少。

DFS 是「一条路走到黑」：它可能在一条很长的路径上先撞到目标，但那条路径未必最短。上例里 DFS 走 A→B→C（2 条边）纯属巧合；如果先走到 A 的另一个朋友再绕回来，路径就会更长。

结语

DFS 和 BFS 的骨架都只有几行：一个栈、一个队列、一个 visited 集合，差别只在容器的存取顺序（LIFO vs FIFO）。

真正决定你选谁的，是问题本身：BFS 解决「距离」问题，DFS 解决「结构」问题。 记住这一点，加上「入队即标记」「非连通图遍历所有起点」这两个易错点，图的遍历基本就不会写错了。

评论
0/100