图论题型：解题思路与方法
图论题在面试中出现频率中等，但一旦出现就是硬考。和 DP 不同，图论题的套路更固定，模板更明确，一旦掌握骨架就很难出错。
图的表示
邻接表（最常用）
每个节点存一个列表，记录它直接连接的节点。
links = [[0,1],[1,2]]
adj = {0: [1], 1: [0,2], 2: [1]}
建表代码：
const adj: Record<number, number[]> = {}
for (let i = 0; i < n; i++) adj[i] = []
for (const [a, b] of links) {
adj[a].push(b) // 无向图要加两次
adj[b].push(a)
}适用场景：稀疏图（边数远小于 n²），大部分面试题。
邻接矩阵
用 n×n 的二维数组，matrix[i][j] = 1 表示 i 和 j 之间有边。
适用场景：稠密图，或需要快速判断”两个节点是否直接相连”。
边列表
就是题目给的 links = [[0,1],[1,2]] 本身。通常需要转成邻接表再用。
两种遍历方式
DFS（深度优先搜索）
一路走到底，走不通了回溯。
const visited = new Set<number>()
function dfs(node: number) {
visited.add(node)
for (const neighbor of adj[node]) {
if (!visited.has(neighbor)) {
dfs(neighbor)
}
}
}特点：递归实现，代码简洁。适合连通分量、环检测、拓扑排序。
BFS（广度优先搜索）
一层一层扩展，用队列。
const visited = new Set<number>()
const queue: number[] = [start]
while (queue.length > 0) {
const node = queue.shift()!
visited.add(node)
for (const neighbor of adj[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor)
queue.push(neighbor)
}
}
}特点：迭代实现，没有递归栈溢出风险。适合最短路径、层序遍历。
DFS vs BFS 选择
| 场景 | 选哪个 |
|---|---|
| 连通分量 | 都行，DFS 更简洁 |
| 最短路径（无权图） | BFS |
| 最短路径（带权图） | Dijkstra |
| 环检测 | DFS |
| 拓扑排序 | DFS 或 BFS（Kahn 算法） |
| 层序遍历 | BFS |
常见图论题型
| 题型 | 特征 | 解法 | 典型题 |
|---|---|---|---|
| 连通分量 | ”有几组/几个连通块” | DFS/BFS + 计数 | 第 21 题 |
| 最短路径（无权） | “最少几步到达” | BFS | 迷宫最短路 |
| 最短路径（带权） | “最短/最少成本” | Dijkstra | 网络延迟 |
| 环检测 | ”是否有环” | DFS + 三色标记 | 课程表 |
| 拓扑排序 | ”依赖关系/执行顺序” | DFS 或 Kahn | 课程表 II |
| 并查集 | ”合并集合/判断连通” | Union-Find | 朋友圈、冗余连接 |
| 网格图 | 二维矩阵当成图 | DFS/BFS + 四方向遍历 | 岛屿数量 |
识别信号
题目出现这些词，往图论想：
- “连通/连通分量/连通块”
- “路径/最短路径/最少步数”
- “网络/节点/边/链路”
- “邻居/相邻/周围”
- “网格/矩阵/岛屿”
- “依赖/前置条件/执行顺序”（拓扑排序）
- “合并集合/是否同一组”（并查集）
解题流程速查卡
1. 读题 → 识别"节点"和"边"是什么
2. 建邻接表（无向图加两次，有向图加一次）
3. 选 DFS 还是 BFS（看问题类型）
4. 写 visited 集合防重复访问
5. 遍历 + 计数/记录路径
6. 检查边界：空图、单节点、全连通、全孤立
并查集（Union-Find）
并查集是图论的另一种解法，专门处理”动态合并集合”的问题。
class UnionFind {
parent: number[]
constructor(n: number) {
this.parent = Array(n).fill(0).map((_, i) => i)
}
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]) // 路径压缩
}
return this.parent[x]
}
union(x: number, y: number): void {
const px = this.find(x)
const py = this.find(y)
if (px !== py) this.parent[px] = py
}
count(): number {
return new Set(this.parent.map((_, i) => this.find(i))).size
}
}适用场景：不需要遍历整个图，只需要判断”两个节点是否属于同一组”或”合并两个组”。比 DFS 更适合动态增减边的场景。
常见坑
- 无向图建表加两次：
adj[a].push(b)和adj[b].push(a)，只加一次会变成有向图。 - 忘记 visited：图可能有环，不标记 visited 会死循环。
- visited 时机错误：BFS 里要在入队时标记 visited，不是出队时。出队时标记可能导致重复入队。
- 网格图忘记边界检查：遍历四个方向时要检查是否越界（row >= 0 && row < rows && col >= 0 && col < cols）。
- 递归栈溢出：节点数很大时 DFS 可能栈溢出，改用 BFS（迭代）。
已做过的图论题
- 21. Count Connected Components in Network — 连通分量，DFS + 邻接表