图论问题概述
图论是算法面试中极具区分度的模块，它涵盖了矩阵网格（本质是图的特殊形式）、有向图、无向图以及树形结构的扩展。图论题的核心技巧包括：
- DFS / BFS：用于连通性检测、路径搜索、染色标记等。
- 拓扑排序：解决有向图的依赖关系问题，如课程安排。
- 并查集（Union-Find）：高效处理动态连通性问题。
- 前缀树（Trie）：多叉树的特殊应用，用于字符串高效查找。
LeetCode 热门 100 题中有四道图论经典题：200. 岛屿数量（网格 DFS/BFS）、994. 腐烂的橘子（多源 BFS）、207. 课程表（拓扑排序）、208. 实现 Trie（前缀树）（多叉树设计）。下面逐一剖析。
1. 岛屿数量（LeetCode 200）
题目：给定一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格，计算岛屿数量。岛屿被水包围，且水平或垂直相邻的陆地视为同一岛屿。
核心思路：遍历网格，每遇到一个 ‘1’ 就启动 DFS/BFS，将该岛屿所有相邻的 ‘1’ 标记为已访问（变为 ‘0’），岛屿计数加一。
DFS 实现：
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
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++;
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] == '0') 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)，空间 O(mn)（递归栈最坏情况）。
关键点：原地修改 grid 避免 visited 数组；也可以使用 BFS（队列）避免递归深度过大。
2. 腐烂的橘子（LeetCode 994）
题目：给定网格，每个格子可能是新鲜橘子（1）、腐烂橘子（2）或空（0）。每分钟腐烂橘子会将上下左右的新鲜橘子腐烂。求全部腐烂所需的最短分钟数，若无法全部腐烂则返回 -1。
核心思路：多源 BFS。将所有初始腐烂橘子入队，同时统计新鲜橘子总数。BFS 逐层扩展，每扩展一层即增加一分钟。当新鲜橘子数为 0 时返回层数；若 BFS 结束后仍有新鲜橘子则返回 -1。
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
Queue<int[]> q = new LinkedList<>();
int fresh = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) q.offer(new int[]{i, j});
else if (grid[i][j] == 1) fresh++;
}
}
if (fresh == 0) return 0;
int minutes = 0;
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
while (!q.isEmpty() && fresh > 0) {
int size = q.size();
minutes++;
for (int i = 0; i < size; i++) {
int[] cell = q.poll();
for (int[] dir : dirs) {
int x = cell[0] + dir[0];
int y = cell[1] + dir[1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
grid[x][y] = 2;
fresh--;
q.offer(new int[]{x, y});
}
}
}
}
return fresh == 0 ? minutes : -1;
}
复杂度：时间 O(mn)，空间 O(mn)。
关键点：多源 BFS 的层数即为分钟数；用 fresh 计数器提前终止。
3. 课程表（LeetCode 207）
题目：给定课程数量 numCourses 和先修关系数组 prerequisites，其中 prerequisites[i] = [a, b] 表示学 a 前必须先学 b。判断是否可以完成所有课程（即图是否有环）。
核心思路：拓扑排序（Kahn 算法）。构建邻接表和入度数组，将所有入度为 0 的节点入队，依次弹出并减少其邻接节点的入度，若某个节点入度变为 0 则入队。若最终入队节点数等于课程总数则无环，否则有环。
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = new ArrayList[numCourses];
int[] indegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) graph[i] = new ArrayList<>();
for (int[] edge : prerequisites) {
graph[edge[1]].add(edge[0]);
indegree[edge[0]]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) q.offer(i);
int count = 0;
while (!q.isEmpty()) {
int cur = q.poll();
count++;
for (int next : graph[cur]) {
indegree[next]--;
if (indegree[next] == 0) q.offer(next);
}
}
return count == numCourses;
}
复杂度：时间 O(V+E)，空间 O(V+E)。
关键点：拓扑排序是检测有向图环的标准方法；也可用 DFS 三色标记检测环。
4. 实现 Trie（前缀树）（LeetCode 208）
题目：实现 Trie 类，支持插入单词、搜索单词、搜索前缀。
核心思路：Trie 是多叉树，每个节点包含一个长度为 26 的子节点数组和一个布尔标志 isEnd。插入时逐字符创建节点，搜索时逐字符向下查找。
class Trie {
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd;
}
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';
if (node.children[idx] == null) node.children[idx] = new TrieNode();
node = node.children[idx];
}
node.isEnd = true;
}
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private TrieNode searchPrefix(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;
}
}
复杂度：插入和搜索的时间均为 O(L)（L 为单词长度），空间 O(总字符数 * 26)。
关键点：Trie 本质上是一个多叉树，它是处理字符串集合的高效结构，常用于自动补全、单词搜索等。
四题对比与总结
| 题目 | 图类型 | 核心技巧 | 时间复杂度 | 空间复杂度 | 关键点 |
|---|---|---|---|---|---|
| 岛屿数量 | 网格无向图 | DFS/BFS 标记 | O(mn) | O(mn) | 原地修改染色 |
| 腐烂的橘子 | 网格多源 BFS | 多源 BFS 层数 | O(mn) | O(mn) | 多源同时扩展 |
| 课程表 | 有向图 | 拓扑排序（入度） | O(V+E) | O(V+E) | 检测有环 |
| 前缀树 | 多叉树 | 节点数组 + isEnd | O(L) | O(26×N) | 字符串快速查找 |
共同本质：图论题的核心是 状态传播。DFS/BFS 用于扩散信息（染色、腐烂、依赖传递），拓扑排序处理先后顺序，前缀树本质上是树形结构但常归入图论范畴。
总结心法：
- 遇到网格连通性 → DFS/BFS 标记。
- 遇到多起点均匀扩散 → 多源 BFS。
- 遇到依赖关系 → 拓扑排序（入度队列）。
- 遇到大量字符串查找 → Trie 前缀树。