入门：DFS 深入到底、BFS 逐层扩展
基于通用算法概念 · 核于 2026-07
速查
- 图遍历：系统地访问图中所有顶点（或从某起点出发能到达的全部顶点）——核心是「不走回头路」，靠
visited标记已访问节点。 - 两种范式：DFS（深度优先） 一条路走到底再回溯，用递归或栈；BFS（广度优先） 一层一层向外扩，用队列。
- DFS 直觉：像走迷宫「贴着一只手摸墙」，不撞南墙不回头，撞墙就回退到上一个岔口换路——擅长找路径、判连通、探环、拓扑。
- BFS 直觉：像水波扩散，从起点先访问距离为 1 的所有点，再距离为 2……——天然带层序，层 = 到起点的距离，故是无权图最短路唯一正解。
- visited 数组：图可能有环，不标记会死循环（树无环所以不用）；这是图遍历区别于树遍历的根本点。
- 复杂度：DFS / BFS 都是 O(V+E)（邻接表）或 O(V²)（邻接矩阵）——每条边、每个顶点各访问常数次，是最优遍历；空间 O(V)（visited + 栈/队列）。
- DFS 数据结构：递归（系统栈，写法最简）或显式栈（迭代，可规避栈溢出）；访问顺序是「后进先出」。
- BFS 数据结构：队列（FIFO）；访问顺序是「先进先出」，保证按距离（层）有序。
- 选型：找任意路径 / 判连通 / 探环 / 拓扑 → DFS；求最短步数（无权图）/ 层序 / 最近邻 → BFS。
- 网格图：岛屿/迷宫把每个格子当节点、四（或八）邻接当边，配方向数组
dirs=[[-1,0],[1,0],[0,-1],[0,1]]遍历。 - 边界：图的存储（邻接矩阵/邻接表）在叶「图的表示」讲，本叶只讲遍历算法——框架对两种存储通用，仅「取邻居」方式不同。
- 进阶顺序：DFS 与 BFS 详解 → 应用 → 参考。
一、为什么图遍历要 visited
树遍历不会无限循环——因为树无环，沿着父→子走不会回到祖先。但图可能有环（A→B→C→A），如果像遍历树那样「访问邻居的邻居」而不标记，就会在环上无限绕：
无 visited：A → B → C → A → B → C → A → ... 死循环 ❌
有 visited：A →(标记A) B →(标记B) C →(标记C) A 已访问，跳过 ✅所以图遍历的第一性原则是：进入一个节点，立刻标记 visited；之后遇到已访问的节点直接跳过。这保证了每个节点只被处理一次，从而复杂度是 O(V+E) 而非指数级。这也解释了为什么 DFS/BFS 模板里 visited 的位置那么关键——标记太晚（比如出队/出栈时才标记）会导致同一节点被重复入队，徒增开销甚至出错。
二、DFS：一条路走到黑
深度优先搜索（DFS）的策略是「能往下走就往下走，走不动了就回溯到上一个有岔路的节点」。它的访问轨迹像一条纵深方向的路径，到极点再回退。
// DFS 递归写法（最常用，本质是系统栈）
const visited = new Array(V).fill(false);
function dfs(u) {
visited[u] = true; // 进入即标记
for (const v of adj[u]) { // 遍历所有邻居
if (!visited[v]) dfs(v);// 未访问的邻居递归深入
}
}
dfs(0); // 从节点 0 出发- 特点：写法极简（递归），擅长找「任意一条路径」（递归栈本身就是路径）、判连通（一次 DFS 能到的点都在同一连通块）、探测环（递归栈上的节点是「当前路径」，遇到它们即有环）、拓扑排序（后序逆序）。
- 风险：递归深度 = 图的最长简单路径，深链状图（如十万个节点连成一条链）会栈溢出（JS 默认栈深约一万），需改**迭代（显式栈）**或手动扩栈。
// DFS 迭代写法（显式栈，规避栈溢出）
function dfsIter(start) {
const visited = new Array(V).fill(false);
const stack = [start];
while (stack.length) {
const u = stack.pop();
if (visited[u]) continue; // 可能重复入栈，出栈时再判一次
visited[u] = true; // 出栈时标记（栈版本防重复入栈）
for (const v of adj[u]) if (!visited[v]) stack.push(v);
}
}三、BFS：一层一层向外扩
广度优先搜索（BFS）的策略是「先把起点周围距离为 1 的点全访问完，再访问距离为 2 的……」像水波纹一圈圈扩散。它用队列（FIFO）保证「先发现的先处理」，从而按距离（层）有序。
// BFS 队列写法
function bfs(start) {
const visited = new Array(V).fill(false);
const queue = [start];
visited[start] = true; // ⚠️ 入队时标记，不是出队时！
while (queue.length) {
const u = queue.shift(); // 队首出队
for (const v of adj[u]) {
if (!visited[v]) {
visited[v] = true; // 入队即标记
queue.push(v);
}
}
}
}- 层序 = 距离：BFS 第 k 层的节点到起点的边数恰好是 k（无权图的最短路径长度）。求最短步数时，只需记录层号或在入队时
dist[v] = dist[u] + 1。 - visited 必须入队时标记：若改成「出队时标记」，同一节点会被多个邻居重复入队，队列膨胀到 O(E) 甚至更多，且可能重复处理——这是 BFS 最高频的 bug。
- 适用：无权图（或等权图）最短路、层序遍历、最近邻问题（如最少转换次数、最近的 X）。
四、复杂度：为什么是 O(V+E)
用 visited 去重后，DFS 和 BFS 的代价完全相同：
- 每个顶点进入一次（被标记 visited 时），处理它「取邻居」的代价取决于存储。
- 邻接表：取所有邻居的代价之和 = 所有节点的度之和 = 2E（无向图）或 E（有向图），加上 V 个顶点的常数处理，总计 O(V+E)。
- 邻接矩阵：每个顶点要扫一整行（V 个元素）找邻居，V 个顶点共 O(V²)，与边数无关。
两者空间都是 O(V)：visited 数组 V、递归栈/迭代栈/队列最坏存 V 个节点。所以「邻接表 + DFS/BFS = O(V+E)」是稀疏图的最优；稠密图（E≈V²）用邻接矩阵也是 O(V²)，与遍历算法无关。
五、DFS 与 BFS 怎么选
| 维度 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈 / 递归 | 队列 |
| 访问顺序 | 一条路走到底再回溯 | 按层（按距离）扩散 |
| 找任意路径 | ✅ 顺手（递归栈即路径） | 一般 |
| 找最短路径（无权） | ❌ 要遍历所有路径比较 | ✅ 天然最短路（首次访问即最短） |
| 判连通 / 连通分量 | ✅ | ✅ |
| 探环 / 拓扑 | ✅（后序逆序 / 三色标记） | ✅（入度法 / Kahn） |
| 二分图判定 | ✅（DFS 染色） | ✅（BFS 染色） |
| 层序 / 最少步数 | ❌ | ✅ |
| 空间（最坏） | O(V)（递归深度/栈） | O(V)（队列宽度） |
| 风险 | 深链图栈溢出 | 宽扇形图队列较大 |
口诀：「求最短步数/层序 → BFS；找路径/探环/拓扑/连通性 → DFS（递归写法最简，深图改迭代）」。两者复杂度相同，区别只在「访问顺序」带来的适用性——BFS 的层序让它垄断了无权最短路。
下一步
理解了 DFS/BFS 的定义与直觉后，下一步是把它们写成通用框架——递归 DFS、迭代（栈）DFS、队列 BFS，并推广到网格图（岛屿/迷宫）的方向数组写法，见DFS 与 BFS 详解。