图与搜索

图与搜索这一部分负责训练“状态空间”的思维。二叉树是特殊的图，回溯是特殊的搜索，二分是有序空间上的搜索方式。把这些放在一起学，更容易建立统一的搜索视角。

识别信号

• 元素之间有”连接/依赖/邻接”关系
• 二维网格上的连通性、最短路问题（隐式图）
• 出现”所有排列/组合/子集”（搜索树 + 回溯）
• 出现”最短步数、最少操作”（BFS）
• 出现”先后顺序、依赖关系”（拓扑排序）
• 有序空间上找边界或最优值（二分查找）

反例：如果问题只涉及线性序列上的子数组/子串，优先考虑滑动窗口或前缀和，而非图搜索。

怎么处理

1. 先把题目抽象成节点、边和状态转移。
2. 要最短步数、按层扩展时优先想 BFS。
3. 要深入搜索、枚举所有可能时优先想 DFS 或回溯。
4. 如果答案具有单调性，就从遍历答案改成二分答案。

典型实例

专题	关键差异	先看什么
图建模与遍历	节点/边识别、图表示方式选择	邻接表建图 + 网格遍历模板
BFS 与 DFS	BFS 求最短、DFS 求连通/枚举	visited 策略 + 多源 BFS
拓扑排序	DAG 上的依赖关系排序	Kahn 算法 + 环检测
最短路	带权图最短距离	Dijkstra + Bellman-Ford
回溯	穷举所有方案 + 剪枝	排列/组合/子集三类模板

看到什么就先想到这类

• 出现“最短步数、层级扩展、最少操作次数”。
• 出现“依赖关系、先后顺序、课程安排”。
• 出现“全排列、组合、子集、答案具有单调性”。