01 BFS 与 DFS 全景导览：搜索算法的本质与适用边界

BFS 与 DFS 全景导览：搜索算法的本质与适用边界

摘要

面试中提到”搜索”，大多数人的条件反射是”BFS 或 DFS，选一个套模板”。但真正能在面试中脱颖而出的工程师，能清楚地回答：这道题为什么用 BFS？如果换成 DFS 会怎样？时间复杂度差在哪里？本文不涉及具体题目，而是从状态空间（State Space）这一统一视角出发，推导 BFS 与 DFS 的本质差异、各自的优劣，以及选型的决策逻辑。这是整个搜索专栏的理论基石。

---

第 1 章 一切搜索问题的本质：状态空间树

1.1 什么是状态空间

在深入 BFS 和 DFS 之前，必须先建立”状态空间（State Space）“的直觉。几乎所有搜索问题都可以用以下框架描述：

• 状态（State）：问题在某一时刻的完整描述。例如，在 Word Ladder 中，状态是当前单词；在 N-Queens 中，状态是已放置的皇后数量及位置；在 Sudoku 中，状态是当前棋盘的填充情况。
• 初始状态（Initial State）：搜索的起点。
• 目标状态（Goal State）：我们想到达的终点，有时是一个具体状态，有时是满足某种条件的状态集合。
• 转移函数（Transition Function）：从一个状态出发，能到达哪些相邻状态。这定义了状态之间的边。
• 代价函数（Cost Function）：从一个状态转移到另一个状态的代价。当代价均匀为 1 时，BFS 能找到最短路径；代价不均匀时需要 Dijkstra 等算法。

这四个要素共同构成了状态空间图（State Space Graph）。所有的搜索算法，本质上都是在这张图上做遍历。

1.2 状态空间的三种常见形态

形态一：显式图

图的节点和边被明确给出，如邻接表或邻接矩阵。这是最直接的形态。

图：4 个城市，3 条边
A -- B
A -- C
B -- D

问题通常是：从 A 出发能否到达 D？最短需要几步？

形态二：矩阵/格子图

矩阵中每个格子是一个状态，四个（或八个）方向上的邻格就是相邻状态。矩阵问题中”图”的结构是隐式的，需要通过方向数组即时枚举。

矩阵（每格是一个状态，四方向相邻）：
1 0 1
1 1 0
0 1 1

问题通常是：连通分量数量、最短路径、某区域是否可达。

形态三：递归树（搜索树）

状态是”已做的选择”，转移函数是”下一步可做哪些选择”。这里的图不是预先给定的，而是在搜索过程中动态展开的。回溯算法的状态空间就是这种形态。

状态：[1, 2] 表示已选择了 1 和 2
转移：从 {3, 4} 中选一个，得到 [1, 2, 3] 或 [1, 2, 4]

这种形态下，状态空间的”图”可能极大（指数级），需要剪枝。

核心概念：状态空间

将问题抽象为状态空间图，是解决任何搜索题的第一步。面试时如果不确定用 BFS 还是 DFS，先问自己：这道题的状态是什么？相邻状态是什么？目标状态是什么？把这三个问题回答清楚，算法选型就自然浮现了。

---

第 2 章 BFS：层层推进的宽幅探索

2.1 BFS 的直觉

广度优先搜索（Breadth-First Search）的行为类似于一波波涟漪向外扩散——先访问所有距离起点为 1 的节点，再访问距离为 2 的，以此类推。

这种”按层扩展”的特性，使得 BFS 在第一次到达某个节点时，走的一定是最短路径（在等权图中）。这是 BFS 最重要的性质，也是它的核心优势。

2.2 BFS 的标准实现

// BFS 标准模板（无权图最短路径）
int bfs(Graph graph, int start, int target) {
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
 
    queue.offer(start);
    visited.add(start);
    int steps = 0;  // 记录当前扩展到第几层（即从 start 出发的步数）
 
    while (!queue.isEmpty()) {
        int size = queue.size();  // 当前层的节点数
        // 处理完一整层，再处理下一层
        for (int i = 0; i < size; i++) {
            int cur = queue.poll();
            if (cur == target) return steps;  // 第一次到达目标，即最短路径
 
            for (int neighbor : graph.neighbors(cur)) {
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);  // 入队时立即标记，防止重复入队
                }
            }
        }
        steps++;  // 整层处理完，步数 +1
    }
    return -1;  // target 不可达
}

每一行的设计理由：

• visited.add(start) 在入队时（而非出队时）标记：如果在出队时才标记，同一节点可能被多次入队，浪费内存甚至导致死循环。入队时立即标记是 BFS 的关键实现细节。
• int size = queue.size()：每次循环开始时固定当前层的大小，确保内层 for 循环只处理当前层的节点，而不是下一层入队的节点。这是”感知层数”（层序感知）的技巧。
• queue：BFS 的核心数据结构是队列（FIFO）。队列保证了先入队的节点先被处理，维护了”按层扩展”的顺序。

2.3 BFS 的时间与空间复杂度

设图有 $V$ 个节点，$E$ 条边：

时间复杂度：$O(V+E)$。每个节点最多入队/出队一次，每条边最多检查两次（无向图中每条边 $u-v$ 在处理 $u$ 时检查一次，处理 $v$ 时检查一次）。

空间复杂度：$O(V)$。最坏情况下（如一个星形图），队列中同时存放所有 $V-1$ 个叶节点。

关键推论：BFS 的空间开销正比于”当前层的宽度”。如果状态空间是一棵深度为 $d$、分支因子为 $b$ 的树，那么最宽的层有 $b^d$ 个节点。BFS 的空间复杂度是 $O(b^d)$，在分支因子大或深度深时会非常耗内存。这是 BFS 的主要劣势。

---

第 3 章 DFS：一头扎到底的深度探索

3.1 DFS 的直觉

深度优先搜索（Depth-First Search）的行为类似于一个迷失在迷宫里的探险家——沿着一条路一直走，直到走不通，再原路返回（回溯），尝试其他路。

这种”深入一条路”的特性，使得 DFS 在空间消耗上远比 BFS 高效——只需要记录当前路径（递归栈），而不需要存储所有待处理节点。

3.2 DFS 的两种实现方式

方式一：递归（隐式栈）

// DFS 递归版（图遍历）
void dfs(Graph graph, int cur, Set<Integer> visited) {
    visited.add(cur);  // 标记已访问
 
    for (int neighbor : graph.neighbors(cur)) {
        if (!visited.contains(neighbor)) {
            dfs(graph, neighbor, visited);  // 递归深入
        }
    }
    // 函数返回时，相当于从当前节点"回溯"到父节点
}

方式二：显式栈（迭代）

// DFS 迭代版（显式栈）
void dfs(Graph graph, int start) {
    Deque<Integer> stack = new ArrayDeque<>();
    Set<Integer> visited = new HashSet<>();
 
    stack.push(start);
 
    while (!stack.isEmpty()) {
        int cur = stack.pop();
        if (visited.contains(cur)) continue;  // 注意：用栈实现时，出栈才标记
        visited.add(cur);
 
        for (int neighbor : graph.neighbors(cur)) {
            if (!visited.contains(neighbor)) {
                stack.push(neighbor);  // 入栈时不标记，可能重复入栈
            }
        }
    }
}

生产避坑：递归版与迭代版的标记时机不同

递归版 DFS 在进入递归时标记，迭代版在出栈后标记。这不是笔误——迭代版若在入栈时标记，由于栈的 LIFO 特性，遍历顺序会与递归版不一致，有时无法正确处理（尤其是在需要记录路径的回溯问题中）。面试中推荐使用递归版，更简洁且不易出错。

3.3 DFS 的时间与空间复杂度

时间复杂度：$O(V+E)$，与 BFS 相同。每个节点最多访问一次。

空间复杂度：$O(V)$（visited 集合） + $O(H)$（递归栈深度），其中 $H$ 为树/图的最大深度。

关键推论：DFS 的空间复杂度与”当前路径的深度”成正比，而不是与”当前层的宽度”成正比。对于一棵深度为 $d$、分支因子为 $b$ 的树，DFS 只需要 $O(d)$ 的栈空间，而 BFS 需要 $O(b^d)$。DFS 在深度较大时空间上远优于 BFS。

---

第 4 章 BFS vs DFS：核心差异的本质

4.1 数据结构差异：队列 vs 栈

BFS 和 DFS 的实现差异，表面上是”队列 vs 栈”，本质上是探索顺序的差异：

• BFS（队列，FIFO）：先入队的先处理。所以离起点近的节点先被处理，形成”层次”扩展。
• DFS（栈/递归，LIFO）：后入栈的先处理。所以最近发现的邻居先被探索，形成”深度优先”。

一个有趣的事实：将 BFS 代码中的队列换成栈，就得到了 DFS（的迭代版）。两者的代码框架几乎完全相同，只是数据结构不同。

4.2 “完备性”与”最优性”差异

性质	BFS	DFS
完备性（能否找到解）	✅ 有限图中保证找到（若有解）	✅ 有限图中保证找到（若有解）
最优性（能否找到最短路）	✅ 等权图中保证最短	❌ 不保证，找到的是第一条深入路径
空间复杂度	$O(b^d)$（指数级，当层宽大时很糟）	$O(d)$（线性，与深度成正比）
时间复杂度	$O(b^d)$	$O(b^d)$（最坏相同，但常数更小）

直接推论：

• 需要求最短路径？用 BFS。因为 DFS 找到的第一条路径不是最短的。
• 需要找所有路径或判断连通性？BFS 和 DFS 都可以，DFS 代码更简洁。
• 状态空间层宽很大但深度较浅？BFS 内存压力大，DFS 更节省。
• 状态空间分支因子极大且目标很深？DFS 可能陷入极深的分支，BFS 系统地按层搜索更可靠。

4.3 什么时候非 BFS 不可

一句话判断准则：如果题目要求”最少步数/最短路径/最少操作次数”，且每步代价相同，那就用 BFS。DFS 不能保证最优性。

具体来说，以下场景必须用 BFS（或等价的 Dijkstra）：

1. 无权图最短路径：Word Ladder 中”最少变换次数”
2. 最小跳跃步数：跳跃游戏、骑士最少步数
3. 多源最短路径：从多个起点同时出发，找到达目标的最短距离
4. 层序相关信息：二叉树层序遍历、统计某节点到根的距离

如果题目不需要”最短”，或者明确要找”所有方案”，则 BFS 和 DFS 均可，通常选 DFS（回溯）。

设计哲学：为什么 DFS 找不到最短路径

DFS 的本质是”沿一条路走到底再回头”。它找到目标时，走的路不一定是最短的——可能是绕了一大圈。BFS 则保证：第一次到达某节点时，经过的路径一定最短。这是因为 BFS 是”按距离排序”地扩展，所有距起点为 $k$ 的节点，都在任何距起点为 $k+1$ 的节点被处理之前处理完毕。

---

第 5 章 回溯：DFS 的高频面试变体

5.1 回溯的本质是什么

回溯（Backtracking）是 DFS 在**递归树（搜索树）**上的应用。它不是一个新算法，而是 DFS 在”做选择、探索、撤销选择”这个特定场景下的专用名称。

为什么需要”撤销选择”这一步？因为在递归树的搜索中，同一个节点（同一个选择）可能从不同路径被多次”考虑”，但如果我们不撤销对全局状态的修改，下一条路径的搜索就会被污染。

以”全排列”为例：

输入：[1, 2, 3]，求所有全排列

搜索树：
            []
       /    |    \
     [1]   [2]   [3]
    /   \
  [1,2] [1,3]
  /       \
[1,2,3] [1,3,2]

在探索 [1, 2] 的子树完成后，要回溯到 [1]，再去探索 [1, 3]。“撤销选择”就是把 2 从路径里移除，并把 2 重新标记为”可用”。

5.2 回溯与暴力枚举的区别：剪枝

纯粹的暴力枚举会生成所有可能的”候选解”，再从中过滤出满足条件的。回溯的关键优化是剪枝（Pruning）——在搜索树上，一旦发现当前路径不可能通向有效解，立即停止这条路径的探索，不再向下展开。

剪枝是回溯的核心价值所在。没有剪枝的回溯和暴力枚举在时间复杂度上没有区别。

剪枝的两种主要形式：

1. 可行性剪枝（Feasibility Pruning）：当前状态已经违反约束，不可能得到有效解。例如，在 Sudoku 中，某格填入数字后，同一行/列/宫已有重复，立即回溯。
2. 最优性剪枝（Optimality Pruning）：当前路径的代价已经超过已知最优解，不可能得到更好的结果。常见于求最优解的搜索问题。

5.3 回溯 vs 动态规划

面试中经常遇到这样的困惑：这道题到底是用回溯还是动态规划？

维度	回溯	动态规划
目标	枚举所有满足条件的方案	求最优解（最大/最小/计数）
子问题	有重叠，但通常不利用	有重叠，且利用（记忆化）
状态修改	需要撤销（回溯）	不需要撤销
典型例题	全排列、组合、N 皇后	背包、最长公共子序列

本质规律：如果题目要求”所有方案（枚举）“，用回溯；如果要求”最优解（计数/最值）“，优先考虑动态规划。两者并不互斥——许多 DP 问题（如 Unique Paths）也可以用加了记忆化的 DFS 解决，性能相同。

---

第 6 章 搜索算法的复杂度分析框架

6.1 图搜索的复杂度

对于图上的 BFS/DFS，复杂度分析相对简单：

• 时间：$O(V+E)$，每个节点最多访问一次，每条边最多检查两次
• 空间：$O(V)$（visited 集合），额外 $O(V)$ 对应 BFS 的队列或 DFS 的递归栈

6.2 矩阵搜索的复杂度

对于 $m\times n$ 矩阵上的 BFS/DFS：

• 时间：$O(mn)$，矩阵中最多 $mn$ 个格子
• 空间：$O(mn)$（visited 数组或 BFS 队列）

6.3 回溯的复杂度

回溯的复杂度分析更复杂，需要分析搜索树的大小：

问题类型	搜索树大小	时间复杂度
排列（$n$ 个元素）	$n!$ 个叶节点	$O(n\cdot n!)$
组合（$n$ 选 $k$）	$C(n,k)$ 个叶节点	$O(k\cdot C(n,k))$
子集（$n$ 个元素）	$2^n$ 个叶节点	$O(n\cdot 2^n)$
棋盘放置（$n\times n$）	最坏 $O(n!)$	$O(n!)$（有剪枝时实际更快）

每个叶节点代表一个完整方案，系数（$n$ 或 $k$）是构建/记录这个方案所需的时间。

---

第 7 章 常见面试误区与解题策略

7.1 误区一：BFS 一定能解的问题，DFS 也能解

错误。如果问题要求”最少步数”，DFS 找到第一个解时不保证是最优的。需要继续搜索所有路径，记录最短的，这实际上退化为穷举，失去了 DFS 的优势。

正确做法：等权图上的最短路径问题，必须用 BFS。

7.2 误区二：visited 标记可以在出队时做

错误。在 BFS 中，如果等到出队时才标记 visited，同一个节点可能被多次入队，导致重复处理，时间复杂度退化，甚至在某些场景下死循环。

正确做法：BFS 中，节点入队时立即标记 visited。

7.3 误区三：回溯一定要生成所有方案才能求最优

错误。带剪枝的回溯（Branch and Bound）可以在搜索过程中剪掉不可能更优的分支，高效求最优解。但当问题有明显的子问题重叠结构时，动态规划是更好的选择。

7.4 误区四：DFS 的空间复杂度是 O(1)

错误。DFS 的递归实现依赖调用栈，栈深度等于搜索树的深度 $d$。最坏情况下（链状图），$d=V$，栈空间为 $O(V)$。如果使用大量局部变量或路径记录，空间可能更高。

7.5 面试答题策略

当看到一道搜索题时，建议按以下顺序思考：

1. 定义状态：问题的”状态”是什么？状态空间有多大？
2. 确定转移：从一个状态可以转移到哪些状态？
3. 明确目标：目标是什么？是否需要最短路径？
4. 选择算法：
   • 需要最短路径 → BFS
   • 需要所有方案 → 回溯（DFS）
   • 需要检测连通性 → BFS 或 DFS 均可
5. 考虑剪枝：哪些状态可以提前排除？
6. 分析复杂度：状态总数 × 每个状态的处理时间

---

第 8 章 本章小结：为什么搜索算法是面试的核心考点

搜索算法之所以是面试的高频考点，原因在于它的泛化能力极强——绝大多数算法问题，本质上都是在某个状态空间上做搜索：

• 动态规划是带记忆化的搜索（避免重复子问题）
• 贪心是每步选择局部最优的搜索（不回溯）
• 图论算法是在图这个特定状态空间上做搜索
• 回溯是在搜索树上带撤销的 DFS

理解了 BFS 与 DFS 的本质差异，掌握了状态空间的抽象方法，后续无论面对哪种具体题型，都有清晰的思考框架。

从下一篇文章开始，我们将进入具体题目的深度讲解，首先从 BFS 的经典例题 Word Ladder 开始。

---

扩展阅读

• 二叉树 的层序遍历（BFS）与前序/后序遍历（DFS）是搜索算法在树结构上的特化应用
• 动态规划 与带记忆化搜索的等价性——同一问题的两种描述视角
• Dijkstra 算法：当边有不同权重时，BFS 退化为优先队列版（最小堆），本质还是”按代价从小到大扩展”