图与搜索

图与搜索 🔥 核心章节

💡 核心要点

图与搜索这一部分负责训练"状态空间"的思维。二叉树是特殊的图，回溯是特殊的搜索，二分是有序空间上的搜索方式。把这些放在一起学，更容易建立统一的搜索视角。图题的核心不是背算法模板，而是学会建模——把题目翻译成节点、边和搜索策略。

---

什么是图

图是由**节点（Vertex）和边（Edge）**组成的数据结构，用来表示"事物之间的关系"。

一句话理解：树是没有环的连通图，图是有环的、可能不连通的"树"。 树的遍历不需要 visited，图的遍历必须用 visited 防止死循环。

图的分类

分类维度	类型	说明	典型场景
方向	有向图	边有方向，A→B 不等于 B→A	课程依赖、网页链接
方向	无向图	边无方向，A—B 等于 B—A	社交关系、道路网
权重	无权图	边没有代价/距离	岛屿问题、单词接龙
权重	有权图	边有权值（距离、费用、时间）	最短路、网络延迟
连通性	连通图	任意两节点间都有路径	—
连通性	非连通图	存在孤立的子图	岛屿数量
环	DAG（有向无环图）	有向且无环	拓扑排序、编译依赖
形态	显式图	题目给出边列表/邻接表	课程表、网络延迟
形态	隐式图	需要从题意推导节点和边	二维网格、状态空间

图 vs 树 vs 链表

链表：每个节点最多 1 个后继
  A → B → C → D

树：每个节点可有多个子节点，但只有 1 个父节点，无环
       A
      / \
     B   C
    / \
   D   E

图：节点可有任意多个连接，可以有环，可以不连通
  A — B — C
  |       |
  D — E — F

关键区别总结：

• 链表/树遍历：不需要 visited（没有环，不会回到已访问节点）
• 图遍历：必须 visited（有环风险，不标记会死循环）
• 树的 n 个节点恰好 n-1 条边；图没有这个限制

---

图题的通用解题思路

拿到一道图题，不要急着写代码。按以下四步思考：

第一步：建模——识别节点和边

这是图题最关键的一步。很多题看起来不像图，但本质是图：

题目描述	节点是什么	边是什么
二维网格上的连通区域	每个格子 (i,j)	四方向相邻的格子
课程先修关系	每门课	先修→后修
单词接龙	每个单词	只差一个字母的单词对
密码锁	每个四位数状态	转一位数字后的状态
社交网络好友关系	每个人	好友关系

隐式图是难点——题目不会告诉你"这是图"，你需要自己把问题翻译成图语言。方法就是问自己：

1. 什么是"一个状态"？→ 这就是节点
2. 从一个状态能到达哪些状态？→ 这就是边
3. 是单向还是双向？→ 有向 vs 无向

第二步：选择表示方式

表示方式	代码	适合场景	空间
邻接表	List<List<Integer>>	90% 的面试题	O(V+E)
邻接矩阵	boolean[][] 或 int[][]	V 小、需 O(1) 查边、Floyd	O(V²)
隐式图	直接在网格上操作	二维网格题	O(1) 额外

面试中几乎永远选邻接表，除非题目有特殊需求。

第三步：选择搜索/算法

这一步的选择取决于题目问什么：

题目问的是	选什么算法	为什么
最短路径/最少步数（无权）	BFS	第一次到达就是最短
最短路径（有权、非负）	Dijkstra	贪心取最近节点
最短路径（有负权/限步数）	Bellman-Ford	无贪心假设，松弛 V-1 轮
连通块数量/连通性判断	DFS 或 BFS 或 并查集	都可以，DFS 代码最短
是否有环（有向图）	DFS 三色标记 或 拓扑排序	Kahn 算法自然检测环
依赖顺序/拓扑序	拓扑排序（Kahn/DFS 后序）	入度为 0 的先处理
枚举所有路径/方案	DFS + 回溯	回溯天然穷举
排列/组合/子集	回溯	搜索树 + 剪枝
动态连通性（边不断加入）	并查集	高效合并和查询

第四步：处理 visited

图遍历的 visited 策略直接影响正确性：

策略	用法	适合场景
boolean[] visited	进入节点时标记	通用，最安全
修改原数组	grid[i][j] = '0'	网格题，省空间
三色标记 int[] color	0/1/2 = 未访问/访问中/完成	有向图判环
入队时标记（BFS）	visited[x] = true 在 offer 时	BFS，防止重复入队
进入标记 + 退出取消（回溯）	枚举所有路径时	DFS + 回溯

⚠️ BFS 的 visited 时机

BFS 必须在入队时标记 visited，不能在出队时。否则同一节点会被多次入队，导致时间和空间浪费。这是面试最常问的 BFS 细节。

---

图题的解题技巧与直觉培养

技巧一：网格题 = 隐式图

二维网格是图题中最常见的形态。关键模式：

int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}}; // 四方向

// 遍历邻居
for (int[] d : dirs) {
    int ni = i + d[0], nj = j + d[1];
    if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]) {
        // 处理 (ni, nj)
    }
}

题感：看到二维矩阵 + "连通/区域/路径/扩散" → 立刻想到网格上的 DFS/BFS。

技巧二：多源 BFS

普通 BFS 从一个起点出发，多源 BFS 从多个起点同时出发。等价于加一个虚拟超级源点连接所有真实源点。

识别信号：题目有多个"源头"同时向外扩散（腐烂的橘子、01 矩阵）。

实现要点：初始化时把所有源点全部入队，后面和普通 BFS 完全一样。

技巧三：状态空间搜索

有些题表面上没有"图"，但可以把状态当节点、状态转换当边：

题目	状态（节点）	转换（边）
单词接龙	每个单词	改一个字母
密码锁	四位数	某位 ±1
滑动谜题	棋盘排列	空格和相邻交换

这类题通常求"最少操作次数" → BFS。

技巧四：并查集解连通性

当题目涉及动态地添加边并反复查询"两个节点是否连通"时，并查集（Union-Find）比 DFS/BFS 更高效：

• 每次 union 和 find 几乎 O(1)（路径压缩 + 按秩合并后）
• 不需要重新遍历整张图

识别信号：

• "判断两点是否在同一连通分量"
• "合并两个集合"
• "边不断加入，动态判断连通性"

技巧五：拓扑排序 = DAG 上的 BFS

拓扑排序（Kahn 算法）本质就是一种特殊的 BFS：

• 普通 BFS 从"距离最近"的节点开始
• Kahn 从"入度为 0"（没有前置依赖）的节点开始

每处理一个节点，就把它的后继的入度减一。如果后继入度变为 0，就入队。

额外能力：处理完后如果节点数 < 总数，说明有环。

技巧六：图题的调试方法

1. 画小图：3-5 个节点的小例子，手动跑一遍算法
2. 打印 visited 数组：确认哪些节点被访问了
3. 打印 dist 数组（最短路）：确认每个节点的距离是否正确
4. 检查边方向：有向图最容易出错的地方——a→b 还是 b→a？
5. 检查是否遗漏非连通分量：别忘了图可能不连通，需要对每个未访问节点都启动遍历

---

算法选型决策树

拿到一道图题，按以下路径选算法：

题目有"图/网格/连接/依赖"特征？
├── 是 →
│   ├── 问最短路/最少步数？
│   │   ├── 无权图 → BFS
│   │   ├── 有权（非负）→ Dijkstra
│   │   ├── 有负权/限步数 → Bellman-Ford
│   │   └── 全源最短路 → Floyd
│   ├── 问依赖顺序/能否完成？→ 拓扑排序
│   ├── 问连通块数量/连通性？
│   │   ├── 静态图 → DFS/BFS
│   │   └── 动态加边 → 并查集
│   ├── 问所有路径/方案？→ DFS + 回溯
│   ├── 问排列/组合/子集？→ 回溯
│   └── 问是否有环？
│       ├── 有向图 → 三色 DFS / 拓扑排序
│       └── 无向图 → DFS 检查是否访问到非父节点
└── 不是 → 可能不是图题

---

常见错误与调试方法

错误	症状	调试方法
图遍历没用 visited	有环时死循环/栈溢出	加 visited 数组，进入节点时标记
无向图只加了单向边	从某些节点出发找不到邻居	建图时 graph[u].add(v) 和 graph[v].add(u)
BFS 在出队时标记 visited	同一节点多次入队，超时	改为入队时标记
有向图判环只用 boolean	已完成节点被误判为"环上节点"	改用三色标记（0/1/2）
边方向搞反（拓扑排序）	入度统计全错，顺序完全反	画小图验证边方向
网格边界检查顺序错	ArrayIndexOutOfBounds	先检查 i >= 0 && i < m，再访问 grid[i][j]
忘记处理非连通分量	只遍历了一部分节点	外层循环对所有未访问节点启动遍历
Dijkstra 用于负权图	结果错误但不报错	有负权边必须用 Bellman-Ford

面试中图题的沟通策略

1. 先说建模："这道题我把 XX 看作节点，YY 看作边，是一个无向/有向图"
2. 再说算法选型："因为求最短路且边权非负，我用 Dijkstra"
3. 提到复杂度："时间 O((V+E)logV)，空间 O(V+E)"
4. 提到可能的优化："如果是无权图可以退化为 BFS，更简单"
5. 边界 case：图不连通、空图、自环、重复边

---

图与搜索题型全景图

类型	核心特征	难度	面试频率	详细页面
图建模与遍历	节点/边识别、建图、DFS/BFS 选择	⭐⭐	🔥🔥🔥	图建模与遍历
BFS 与 DFS	最短路(无权)、连通块、层序、多源 BFS	⭐⭐	🔥🔥🔥	BFS 与 DFS
拓扑排序	依赖关系排序、DAG 判环	⭐⭐	🔥🔥🔥	拓扑排序
最短路	Dijkstra、Bellman-Ford、Floyd	⭐⭐⭐	🔥🔥	最短路
回溯	排列/组合/子集、棋盘、剪枝	⭐⭐	🔥🔥🔥	回溯
并查集	动态连通性、集合合并查询	⭐⭐	🔥🔥	并查集
Tarjan 强连通分量（工程）	有向图找环 / 缩点 / Spring 循环依赖检测	⭐⭐⭐	🔥🔥	Tarjan SCC

建议学习顺序

第一阶段（基础，必须掌握）：
  图建模与遍历 → BFS 与 DFS → 回溯

第二阶段（进阶，面试常考）：
  拓扑排序 → 并查集

第三阶段（高阶，锦上添花）：
  最短路（Dijkstra → Bellman-Ford → Floyd）

第一阶段建立图的基本直觉和搜索能力。第二阶段掌握两种特殊场景的高效算法。第三阶段是带权图的处理，难度较大但面试频率也高。

---

总结速查表

算法选型速查

问题类型	首选算法	时间复杂度
无权图最短路	BFS	O(V+E)
有权图最短路（非负）	Dijkstra	O((V+E)logV)
有负权/限步数最短路	Bellman-Ford	O(VE)
全源最短路	Floyd	O(V³)
连通块计数	DFS / BFS / 并查集	O(V+E)
依赖排序/判环	拓扑排序 Kahn	O(V+E)
枚举所有路径/方案	DFS + 回溯	O(指数级)
动态连通性	并查集	O(α(n))≈O(1)

数据结构速查

算法	核心数据结构	初始化要点
BFS	Queue<int[]> + boolean[] visited	源点入队 + 标记
DFS	递归栈（或显式 Stack）	进入时标记 visited
Dijkstra	PriorityQueue<int[]> + int[] dist	dist 初始化 MAX，源点为 0
Bellman-Ford	int[] dist + 边列表	dist 初始化 MAX，源点为 0
拓扑排序	Queue + int[] indegree	入度为 0 的先入队
并查集	int[] parent + int[] rank	parent[i] = i
回溯	递归 + List<> path	path 为空，start=0

模板速查

模板	关键代码行
网格四方向	int[][] dirs = { {0,1},{0,-1},{1,0},{-1,0} };
BFS 层计数	int size = queue.size(); for (int k = 0; k < size; k++) {...}
DFS 回溯	path.add(x); dfs(...); path.remove(path.size()-1);
邻接表建图	graph.get(u).add(v); graph.get(v).add(u);
Dijkstra 跳过过时	if (d > dist[u]) continue;
拓扑排序判环	return order.size() == n;
并查集路径压缩	parent[x] = find(parent[x]);
同层去重	if (i > start && nums[i] == nums[i-1]) continue;

识别信号速查

看到什么	先想到什么
二维网格 + 连通/区域	DFS/BFS 网格遍历
最短路径/最少步数（无权）	BFS
最短路径（有权）	Dijkstra
依赖关系/先后顺序	拓扑排序
所有排列/组合/子集	回溯
两个节点是否连通（动态加边）	并查集
"扩散/感染/传播"从多个源	多源 BFS
状态转换求最少步数	状态空间 BFS
有向图是否有环	三色 DFS / 拓扑排序