算法面试突击手册 —— 图（BFS/DFS/拓扑排序/并查集）
一、概念与特点
大白话 + 类比
图 = 城市之间的交通网
- 节点 = 城市，边 = 道路
- DFS：你开车从 A 出发，一条路走到尽头（不撞南墙不回头），再倒车回来换一条路
- BFS：你从 A 放出一群侦察兵，同时向所有相邻城市前进，一圈一圈扩散
- 拓扑排序：大学选课——先修课必须在前面，把依赖关系排成一条合法的学习路径
- 并查集：家族认亲——两个人分别往上查族谱，看是否属于同一个祖先
遍历选择策略——选错会走弯路
| 场景 | 选 DFS | 选 BFS | 原因 |
|---|---|---|---|
| 找所有连通分量 | ✅ | ✅ | 两者都能遍历整个连通区域 |
| 最短路径（无权图） | ❌ | ✅ | BFS 按层扩散，首次到达即最短 |
| 拓扑排序 | ✅ | ✅ | DFS 后序 / BFS Kahn 都可 |
| 判断连通性 | ✅ | ✅ | 遍历完看是否全覆盖 |
| 多源扩散 | ❌ | ✅ | BFS 多起点同时入队，自然按层扩散 |
识别信号词
- “岛屿”、“区域”、“矩阵中的连通块” → DFS/BFS 沉岛
- “课程表”、“先修课”、“依赖关系”、“能否完成” → 拓扑排序
- “朋友”、“连通”、“集合合并” → 并查集
- “腐烂”、“扩散”、“最短时间”、“感染” → 多源 BFS
- “Trie”、“前缀树”、“自动补全” → 特殊多叉树
- “除法求值”、“变量关系” → 带权图 BFS
四种核心代码模板
// 1. DFS 沉岛（二维网格）
void dfs(char[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length
|| grid[i][j] != '1') return;
grid[i][j] = '0'; // "沉掉"当前位置，防止重复访问
dfs(grid, i+1, j); dfs(grid, i-1, j);
dfs(grid, i, j+1); dfs(grid, i, j-1);
}
// 2. BFS 队列 —— 适合求最短距离
Queue<int[]> q = new LinkedList<>();
q.offer(start);
while (!q.isEmpty()) {
int size = q.size(); // 当前层节点数
for (int i = 0; i < size; i++) { /* 处理一层 */ }
}
// 3. 拓扑排序（BFS Kahn 算法）
int[] indegree = new int[n];
for (int[] edge : edges) indegree[edge[1]]++;
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) if (indegree[i] == 0) q.offer(i);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj[u]) if (--indegree[v] == 0) q.offer(v);
}
// 4. 并查集
class UnionFind {
int[] parent, rank;
// 查找（路径压缩）
int find(int x) {
return parent[x] == x ? x : (parent[x] = find(parent[x]));
}
// 合并（按秩合并）
void union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
if (rank[rx] < rank[ry]) parent[rx] = ry;
else if (rank[rx] > rank[ry]) parent[ry] = rx;
else { parent[ry] = rx; rank[rx]++; }
}
}二、Hot 100 精讲题目
200. Number of Islands 岛屿数量
📌 二维网格中，‘1’ 是陆地，‘0’ 是水。水平和垂直方向相连的陆地组成岛屿。计算岛屿数量。如
[["1","1","0"],["1","0","1"],["0","0","1"]]→ 3
🔍 解题分析
为什么用 DFS
这是经典的”连通分量计数”问题。DFS 可以一次性遍历完整个岛屿（所有相连的 ‘1’），然后我们把遍历过的陆地”沉掉”（改成 ‘0’），避免重复计数。
核心思路（步骤化）
- 遍历每个格子
- 遇到 ‘1’ → count++（发现新岛屿）→ 调用 dfs 把整个岛沉掉
- DFS 内部：四方向递归扩散，每到一个 ‘1’ 就改成 ‘0’
- 遍历结束，返回 count
“沉岛”的含义：遇到一个 ‘1’ 说明发现了陆地。用 DFS 遍历它的上下左右相邻陆地，全部改成 ‘0’（沉入水中）。这样后续遍历就不会再把同一岛的陆地重复计数。
关键边界条件/易错点
| 易错点 | 说明 |
|---|---|
| 越界检查必须在最前面 | 先判断 i/j 是否合法，再判断 grid[i][j] |
| 沉岛时机 | 必须在递归前沉，不能递归后沉——否则会无限递归 |
| 四方向 vs 八方向 | 题目说”相邻”默认只有上下左右（4 方向），不是对角线 |
✅ 完整 Java 实现
public int numIslands(char[][] grid) {
int m = grid.length, n = grid[0].length;
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 发现新大陆！
if (grid[i][j] == '1') {
count++; // 岛屿数 +1
dfs(grid, i, j); // 把整座岛沉入水中
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
// 越界或遇到水 → 停止扩散
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length
|| grid[i][j] != '1') {
return;
}
// 沉岛：将当前陆地标记为水，表示已访问
grid[i][j] = '0';
// 向四个方向扩散，继续吞噬相连的陆地
dfs(grid, i + 1, j); // 下
dfs(grid, i - 1, j); // 上
dfs(grid, i, j + 1); // 右
dfs(grid, i, j - 1); // 左
}⏱ 复杂度分析
- 时间复杂度：O(mn) —— 每个格子最多被访问两次（一次外层遍历，一次 DFS）
- 空间复杂度：O(mn) —— 递归栈最坏情况（全为 ‘1’ 的矩阵），等于格子总数
💡 记忆口诀
“遇 1 加一，DFS 四向沉岛；沉过的永远不会再被数到”
695. Max Area of Island 岛屿的最大面积
📌 找最大岛屿的面积（岛屿中 ‘1’ 的数量）。网格只含 0 和 1。如
[[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],...]→ 6
🔍 解题分析
与 200 题完全相同的模板，区别在于：
- 输入是
int[][]（不是char[][]），判断grid[i][j] != 1 - DFS 需要返回面积：
1 + dfs(上) + dfs(下) + dfs(左) + dfs(右)
DFS 返回值设计：每个格子返回它自己（1）加上四个方向能探索到的陆地面积之和。递归自动汇总了整块岛屿的面积。
关键边界条件/易错点
| 易错点 | 说明 |
|---|---|
| 返回值在沉岛之后 | 先沉掉当前格子（标记为已访问），再累加面积。return 1 + dfs() + dfs()... |
| 空网格 | 如果网格全 0，maxArea 保持 0，逻辑正确 |
| int vs char | 这题是 int[][]，判断用 != 1；200 题是 char[][]，判断用 != '1' |
✅ 完整 Java 实现
public int maxAreaOfIsland(int[][] grid) {
int m = grid.length, n = grid[0].length;
int maxArea = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
// 计算当前岛屿的面积，并更新最大值
int area = dfs(grid, i, j);
maxArea = Math.max(maxArea, area);
}
}
}
return maxArea;
}
// 返回从 (i,j) 开始能探索到的岛屿面积
private int dfs(int[][] grid, int i, int j) {
// 越界 或 不是陆地 → 贡献面积为 0
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length
|| grid[i][j] != 1) {
return 0;
}
// 沉岛：标记为已访问
grid[i][j] = 0;
// 当前格子面积 1 + 四个方向各自探索的面积
return 1 + dfs(grid, i + 1, j) // 下
+ dfs(grid, i - 1, j) // 上
+ dfs(grid, i, j + 1) // 右
+ dfs(grid, i, j - 1); // 左
}⏱ 复杂度分析
- 时间复杂度：O(mn) —— 每个格子最多访问两次
- 空间复杂度：O(mn) —— 递归栈最坏情况
💡 记忆口诀
“沉岛时数格子，1 + 四方向和——递归自动汇总整块面积”
207. Course Schedule 课程表
📌 numCourses 门课，
prerequisites[i] = [a, b]表示必须先修 b 才能修 a。判断能否完成所有课程（= 有向图无环）。如numCourses=2, prerequisites=[[1,0]]→ true
🔍 解题分析
为什么是拓扑排序
课程依赖关系天然形成有向图：b → a（b 是 a 的先修课）。如果这个图里有环（A 依赖 B，B 依赖 A），就不可能完成所有课程。拓扑排序正好用来判断有向图是否有环。
BFS Kahn 算法（步骤化）
- 构建邻接表
adj（b → a 的方向）和入度数组indegree - 所有入度为 0 的节点入队（没有先修依赖的课可以直接学）
- 每次从队列取出一个节点（学一门课），将它的所有后继节点的入度减 1
- 如果某个后继节点入度变为 0，入队（它的所有先修课都学完了）
- 最终看能不能学完所有节点（count == n）
类比：想象修课就像拆积木，入度为 0 就是”没有压在它上面的积木”。每次取一块能直接拿起来的（入度 0），拿了之后压在它下面的积木的依赖就少了一层。
关键边界条件/易错点
| 易错点 | 说明 |
|---|---|
| 边方向 | [a, b] 是 b→a（先修 b 才能修 a），入度加在 a 上 |
| 有环的判断 | 最终 count < n 说明有环（部分节点入度永远不会变为 0） |
| 单门课 | 没有任何先修要求，入度全是 0，直接返回 true |
✅ 完整 Java 实现
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 1. 构建邻接表 + 入度数组
// adj[i] = 学完课程 i 之后能学的课的列表
List<Integer>[] adj = new List[numCourses];
for (int i = 0; i < numCourses; i++) {
adj[i] = new ArrayList<>();
}
int[] indegree = new int[numCourses]; // indegree[i] = 课程 i 的先修课数量
for (int[] pre : prerequisites) {
int course = pre[0]; // 要学的课
int prereq = pre[1]; // 先修课
adj[prereq].add(course); // 学完 prereq 才能学 course
indegree[course]++; // course 的入度 +1（多了一门先修课）
}
// 2. 入度为 0 的课入队（没有先修依赖，可以直接学）
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
// 3. BFS：逐门学习
int learned = 0; // 已学课程数
while (!queue.isEmpty()) {
int course = queue.poll();
learned++; // 学完这门课
// 把这门课的所有后继课的入度减 1
for (int next : adj[course]) {
indegree[next]--;
// 后继课的先修条件全部满足了 → 可以学了
if (indegree[next] == 0) {
queue.offer(next);
}
}
}
// 4. 学完了所有课 → 无环；否则有环
return learned == numCourses;
}手算验证：numCourses=4, prerequisites=[[1,0],[2,1],[3,2],[1,3]]（存在环 1→2→3→1）
| 初始入度 | 0:0, 1:2, 2:1, 3:1 | | 入队 | [0] | | 学 0 | learned=1，0 的后继 1 入度减为 1 | | 队列空 | learned=1 ≠ 4 → false（有环） ✓ |
⏱ 复杂度分析
- 时间复杂度：O(V + E) —— V 是课程数，E 是依赖关系数
- 空间复杂度：O(V + E) —— 邻接表 + 入度数组 + 队列
💡 记忆口诀
“入度为零的课先学，学完降低依赖课入度，全学完无环”
208. Implement Trie (Prefix Tree) 实现 Trie（前缀树）
📌 实现前缀树，支持
insert(word),search(word),startsWith(prefix)操作。
🔍 解题分析
Trie 是什么
Trie 是一棵 26 叉树，每个节点有 26 个可能的子节点（对应 a-z）。从根到某个节点的路径代表一个前缀。如果该节点被标记为 isEnd = true，说明这个前缀是一个完整的单词。
操作分解：
- insert(“cat”)：从根开始，沿 c→a→t 建路径，在 t 节点标记
isEnd=true - search(“cat”)：沿 c→a→t 走，如果路径存在且 t 节点的 isEnd 是 true→找到
- search(“ca”)：沿 c→a 走，路径存在但 a 的 isEnd 是 false→只是前缀，不是单词
- startsWith(“ca”)：沿 c→a 走，路径存在→是前缀
类比：Trie 就像一个电子词典的索引。输入 “app”，它不需要遍历整个词典，而是直接沿着 a→p→p 的路径走，路径上的节点告诉你”这是前缀还是完整单词”。
关键边界条件/易错点
| 易错点 | 说明 |
|---|---|
| search 需要 isEnd | search 必须检查 isEnd，否则 “app” 没插入时 “app” 也能搜到（如果有 “apple”） |
| startsWith 不需要 isEnd | 只要路径通就行 |
| 字符转下标 | c - 'a' 映射到 0~25 |
✅ 完整 Java 实现
class Trie {
// 内部节点类
private static class TrieNode {
TrieNode[] children = new TrieNode[26]; // 26 个子节点
boolean isEnd = false; // 标记：当前节点是否是一个完整单词的结尾
}
private TrieNode root; // 根节点（空节点）
public Trie() {
root = new TrieNode();
}
// 插入单词
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int idx = c - 'a'; // a→0, b→1, ..., z→25
// 如果这个字母对应的子节点不存在，创建一个
if (node.children[idx] == null) {
node.children[idx] = new TrieNode();
}
node = node.children[idx]; // 沿路径往下走
}
// 在最后一个字符的节点上打标记
node.isEnd = true;
}
// 搜索完整单词
public boolean search(String word) {
TrieNode node = findNode(word);
// 路径存在 且 该节点是单词结尾
return node != null && node.isEnd;
}
// 搜索前缀
public boolean startsWith(String prefix) {
// 只要能走到最后一个字符就行，不要求 isEnd
return findNode(prefix) != null;
}
// 辅助方法：沿着 prefix 走，返回最后一个节点
// 如果路径中途断了，返回 null
private TrieNode findNode(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
return null; // 路径断了
}
node = node.children[idx];
}
return node; // 走到了 prefix 的最后一个字符
}
}⏱ 复杂度分析
- 时间复杂度：O(L) —— L 为单词/前缀长度，每次操作只遍历 L 步
- 空间复杂度：O(N × 26) —— N 为插入的所有单词的总字符数
💡 记忆口诀
“26 个孩子一个妈（根节点），字母是路径，isEnd 标记完整单词”
399. Evaluate Division 除法求值
📌 给定除法等式
a / b = value，回答任意两个变量的除法结果。若无法确定返回 -1.0。如equations=[["a","b"],["b","c"]], values=[2.0,3.0], queries=[["a","c"]]→[6.0]
🔍 解题分析
为什么是图
除法关系构成带权有向图。a / b = 2.0 意味着：
- 边
a → b权重 2.0 - 边
b → a权重 1/2.0（倒数）
要从 a 求 c，只需找到 a 到 c 的一条路径，路径上权重的乘积就是答案。a → b (×2.0) → c (×3.0) = 6.0。
核心思路（步骤化）
- 建图：
Map<String, Map<String, Double>>—— 节点 → {邻居节点, 边权重} - 对每个 equation，插入两条边（正向 + 反向）
- 对每个 query，BFS/DFS 从 start 走到 end，路径权重连乘
- 如果 start 或 end 不在图中，或路径不连通，返回 -1.0
为什么 BFS：找两点间的路径，BFS 和 DFS 都可以。BFS 找到的第一条路径就是最短路径，但这里任意路径都行。
关键边界条件/易错点
| 易错点 | 说明 |
|---|---|
| 双向边 | 必须同时存 a→b (权重 v) 和 b→a (权重 1/v) |
| start == end | 如果 start 和 end 相同且在图中，返回 1.0 |
| 节点不在图中 | 返回 -1.0 |
| 用 Pair 或自定义类 | Java 标准库有 AbstractMap.SimpleEntry 可以临时用 |
| 除法链 | 路径上权重是连乘，不是累加 |
✅ 完整 Java 实现
public double[] calcEquation(List<List<String>> equations, double[] values,
List<List<String>> queries) {
// 1. 建图：节点 → {邻居节点 → 边权重}
Map<String, Map<String, Double>> graph = new HashMap<>();
for (int i = 0; i < equations.size(); i++) {
String a = equations.get(i).get(0); // 被除数
String b = equations.get(i).get(1); // 除数
double v = values[i]; // a / b = v
// 正向边：a → b，权重 v
graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, v);
// 反向边：b → a，权重 1/v
graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / v);
}
// 2. 逐个回答查询
double[] result = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
String start = queries.get(i).get(0);
String end = queries.get(i).get(1);
result[i] = bfs(graph, start, end);
}
return result;
}
// BFS 寻找 start → end 的路径权重乘积
private double bfs(Map<String, Map<String, Double>> graph,
String start, String end) {
// 节点不在图中 → 无法计算
if (!graph.containsKey(start) || !graph.containsKey(end)) {
return -1.0;
}
// 同一个节点 → 结果是 1.0（a / a = 1.0）
if (start.equals(end)) {
return 1.0;
}
// BFS：队列存 (当前节点, 从 start 到当前节点的累积乘积)
Queue<AbstractMap.SimpleEntry<String, Double>> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer(new AbstractMap.SimpleEntry<>(start, 1.0));
visited.add(start);
while (!queue.isEmpty()) {
AbstractMap.SimpleEntry<String, Double> pair = queue.poll();
String node = pair.getKey();
double curVal = pair.getValue(); // start → node 的累积乘积
// 遍历当前节点的所有邻居
for (Map.Entry<String, Double> edge : graph.get(node).entrySet()) {
String neighbor = edge.getKey();
double weight = edge.getValue();
double newVal = curVal * weight; // 累积乘积
// 到达终点！
if (neighbor.equals(end)) {
return newVal;
}
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(new AbstractMap.SimpleEntry<>(neighbor, newVal));
}
}
}
// 不连通 → 无法计算
return -1.0;
}⏱ 复杂度分析
- 时间复杂度：O(Q × (V + E)) —— 每个查询做一次 BFS
- 空间复杂度：O(V + E) —— 图存储
💡 记忆口诀
“除法即带权边，正反两条路（互为倒数），BFS 沿路连乘”
994. Rotting Oranges 腐烂的橘子
📌 网格：0 空，1 新鲜橘子，2 腐烂橘子。每分钟烂橘子会感染上下左右相邻的新鲜橘子。求全部腐烂的最少分钟数。若不可能全烂返回 -1。
🔍 解题分析
为什么是多源 BFS
多个初始烂橘子同时开始扩散。BFS 天然支持多起点同时入队，一层一层扩散。每扩散一层 = 经过一分钟。
核心思路（步骤化）
- 第一遍扫描网格：
- 收集所有初始烂橘子（值为 2）的位置入队
- 统计新鲜橘子数量
freshCount
- 如果 freshCount == 0，返回 0（没有需要腐烂的）
- BFS 扩散：每轮处理队列中当前层的所有烂橘子
- 向四个方向扩散
- 感染到的新鲜橘子变成烂橘子并入队
- freshCount—
- 每完成一层扩散，minutes++
- BFS 结束后：freshCount > 0 → 有橘子永远烂不了，返回 -1；否则返回 minutes-1
为什么返回 minutes-1：最后一层扩散完后 minutes 又加了一次，但实际上不需要这额外的一分钟。
关键边界条件/易错点
| 易错点 | 说明 |
|---|---|
| 初始无新鲜橘子 | 直接返回 0 |
| 分钟数的计算 | BFS 结束后返回 minutes - 1（最后一轮扩散后不再需要时间） |
| 队列为空且 freshCount > 0 | 说明被隔离的新鲜橘子永远烂不了 |
✅ 完整 Java 实现
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int freshCount = 0; // 新鲜橘子数量
// 第一遍扫描：收集烂橘子 + 统计新鲜橘子
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
queue.offer(new int[]{i, j}); // 腐烂源入队
} else if (grid[i][j] == 1) {
freshCount++; // 统计新鲜橘子
}
}
}
// 没有需要感染的目标
if (freshCount == 0) return 0;
int minutes = 0;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四个方向
// 多源 BFS
while (!queue.isEmpty()) {
int size = queue.size(); // 当前分钟需要处理的腐烂源数量
minutes++; // 进入新的一分钟
for (int i = 0; i < size; i++) {
int[] cur = queue.poll(); // 取出一个腐烂源
int r = cur[0], c = cur[1];
// 向四个方向扩散感染
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
// 在网格内 且 是新鲜橘子 → 感染它
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& grid[nr][nc] == 1) {
grid[nr][nc] = 2; // 感染！
freshCount--; // 新鲜橘子-1
queue.offer(new int[]{nr, nc}); // 下一轮的腐烂源
}
}
}
}
// freshCount > 0 说明有橘子永远烂不了（被隔离了）
return freshCount == 0 ? minutes - 1 : -1;
}手算验证：grid = [[2,1,1],[1,1,0],[0,1,1]]
| 分钟 | 队列中的烂橘子 | 本轮感染 | freshCount |
|---|---|---|---|
| 0 | (0,0) | — | 5 |
| 1 | (0,0) | (1,0), (0,1) | 3 |
| 2 | (1,0), (0,1) | (1,1), (0,2) | 1 |
| 3 | (1,1), (0,2) | (2,1) | 0 |
分钟数 = 4-1 = 3？实际需要 3 分钟，minutes-1=3 ✓（最后一轮后 freshCount=0）
⏱ 复杂度分析
- 时间复杂度：O(mn) —— 每个格子最多入队一次
- 空间复杂度：O(mn) —— 队列最多存 mn 个位置
💡 记忆口诀
“烂橘子一起入队，每轮扩散一圈加一分钟；最后检查有没有烂不到的”