00 专栏导览

搜索算法专栏导览：BFS 与 DFS 面试通关

专栏定位

本专栏面向有一定编程基础、正在备战技术面试的工程师。讨论范围严格限定于图/矩阵/字符串上的广度优先搜索（BFS）与深度优先搜索（DFS）两大搜索范式，重点聚焦回溯（Backtracking）这一 DFS 的高频面试变体，不涉及动态规划、贪心、树的专题等其他领域。

目标：帮助读者真正理解 BFS 与 DFS 的本质区别与适用边界，而非死记硬背套路模板。每道题的讲解遵循”是什么 → 为什么出现 → 不这样会怎样 → 如何落地 → 边界与反例”的推导链，力求通俗易懂而不失深度。

---

专栏目录

序号	文章标题	核心话题	覆盖 LeetCode 题目
01	BFS 与 DFS 全景导览：搜索算法的本质与适用边界	状态空间树、BFS 与 DFS 的根本差异、队列 vs 递归栈、复杂度分析框架	概念篇，无具体题目
02	BFS 核心框架：层序扩展与单向最短路径	BFS 模板、visited 集合设计、层级感知、图上最短路径	Word Ladder (LeetCode 127)
03	双向 BFS 与路径还原：Word Ladder II 深度解析	双向 BFS 加速原理、前驱图构建、DFS 回溯路径还原	Word Ladder II (LeetCode 126)
04	DFS 与回溯核心框架：状态树的系统性遍历	DFS 递归模板、回溯三要素（选择/路径/结束条件）、剪枝策略分类	概念篇 + Surrounded Regions (LeetCode 130)
05	矩阵 BFS/DFS：连通分量与 Flood Fill	四方向/八方向遍历、并查集对比、原地标记技巧	Surrounded Regions (LeetCode 130)、Number of Islands (LeetCode 200)
06	组合型回溯：Combination Sum 系列	排列与组合的区别、去重的两种策略、剪枝的必要性证明	Combination Sum (LeetCode 39)、Combination Sum II (LeetCode 40)
07	字符串型回溯：分割与括号生成	分割问题的指针模型、合法性前向剪枝、括号配对的状态约束	Palindrome Partitioning (LeetCode 131)、Generate Parentheses (LeetCode 22)、Restore IP Addresses (LeetCode 93)
08	棋盘型回溯：N-Queens 与数独求解	约束传播思想、按列/对角线剪枝的位运算实现、Dancing Links 简介	N-Queens (LeetCode 51)、N-Queens II (LeetCode 52)、Sudoku Solver (LeetCode 37)
09	矩阵深搜：Word Search 与路径问题	DFS 在二维矩阵上的路径搜索、visited 数组 vs 原地标记、Trie 剪枝优化	Word Search (LeetCode 79)、Word Search II (LeetCode 212)、Unique Paths (LeetCode 62)
10	搜索算法面试通关：模式识别与优化策略总结	BFS/DFS 选型决策树、常见错误盘点、记忆化搜索与 DP 的桥梁	综合复习篇

---

专栏阅读建议

1. 第 01 篇必读：理解 BFS 与 DFS 的”性格差异”是后续一切内容的基石。很多人写 DFS 不假思索，但对”为什么这道题用 BFS 不行”说不清楚，这是面试的高频失分点
2. BFS 篇（02-03）：Word Ladder 系列是 BFS 的教科书级例题，从单向到双向 BFS 的演进清晰地展示了算法优化的思考路径
3. DFS/回溯篇（04-09）：回溯是面试频率最高的搜索变体。建议先彻底吃透第 04 篇的通用框架，再去看各类具体题型
4. 本专栏不覆盖：Dijkstra、A* 等带权图最短路算法；动态规划（与 DFS 的联系在第 10 篇简要说明）；树的专项遍历（虽然原理相同，但另有专栏覆盖）

---

搜索算法复杂度速查表

算法	时间复杂度	空间复杂度	典型适用场景
BFS（图）	$O(V+E)$	$O(V)$	无权图最短路径、层序遍历
DFS（图）	$O(V+E)$	$O(V)$（递归栈）	连通性检测、拓扑排序
回溯（排列）	$O(n\cdot n!)$	$O(n)$	全排列、N 皇后
回溯（子集）	$O(n\cdot 2^n)$	$O(n)$	子集枚举、组合问题
BFS（矩阵 $m\times n$）	$O(mn)$	$O(mn)$	Flood Fill、最短路
DFS（矩阵 $m\times n$）	$O(mn)$	$O(mn)$	连通分量、路径搜索
双向 BFS	$O(b^{d/2})$	$O(b^{d/2})$	词梯问题、双端最短路

$b$ = 分支因子，$d$ = 最短路径长度，$V$ = 顶点数，$E$ = 边数

---

回溯算法通用框架（提前预览）

def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.append(路径.copy())
        return
    for 选择 in 选择列表:
        做选择          # 将选择添加到路径
        backtrack(路径, 新的选择列表)
        撤销选择        # 从路径移除，恢复现场

这是整个回溯专题的灵魂。后续每道题的解法都是对这个框架的具体实例化。