图论 解题模板

适用场景

岛屿问题、拓扑排序、并查集、有向/无向图遍历

通用模板

网格 DFS（岛屿问题）

 
def dfs(grid, i, j):
 
    if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
 
        return
 
    grid[i][j] = '0'  # 标记已访问
 
    for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]:
 
        dfs(grid, i+di, j+dj)
 

拓扑排序（课程表）

 
# BFS（Kahn）
 
indeg = [0] * n
 
graph = [[] for _ in range(n)]
 
for u, v in edges:
 
    graph[v].append(u)  # 前驱→后继
 
    indeg[u] += 1
 
q = deque([i for i in range(n) if indeg[i] == 0])
 
res = []
 
while q:
 
    node = q.popleft()
 
    res.append(node)
 
    for nei in graph[node]:
 
        indeg[nei] -= 1
 
        if indeg[nei] == 0: q.append(nei)
 
return res if len(res) == n else []
 

并查集

 
parent = list(range(n))
 
def find(x):
 
    while parent[x] != x:
 
        parent[x] = parent[parent[x]]  # 路径压缩
 
        x = parent[x]
 
    return x
 
def union(x, y):
 
    rx, ry = find(x), find(y)
 
    if rx == ry: return False
 
    parent[ry] = rx
 
    return True
 

复杂度总结

模式	时间	空间	典型题
DFS/BFS	O(m×n)	O(m×n)	岛屿数量、腐烂橘子
拓扑排序	O(V+E)	O(V+E)	课程表
并查集	O(α(n))	O(n)	冗余连接、省份数量

关键要点

• 网格 DFS 注意边界检查顺序

• 拓扑排序 = 有向无环图的线性排序

• 并查集路径压缩 + 按秩合并

→ 查看该分类题目：LeetCode学习路线图 > 十二、图论

---

相似题对比

易混题对	关键区别	解法差异
200岛屿数量 vs 695岛屿最大面积	计数 vs 求最大	695 DFS返回面积，取max
207课程表 vs 210课程表II	判环 vs 输出拓扑序	207返回bool；210输出order
547省份数量 vs 684冗余连接	无向图连通分量 vs 找环边	DFS计数 vs 并查集union失败
200岛屿数量 vs 994腐烂橘子	遍历一次 vs 多源BFS分层	DFS染色 vs BFS逐分钟扩散

---

测试用例模板

 
# 基础功能
 
assert numIslands([
 
    ["1","1","1","1","0"],
 
    ["1","1","0","1","0"],
 
    ["1","1","0","0","0"],
 
    ["0","0","0","0","0"]
 
]) == 1
 
# 边界
 
assert numIslands([]) == 0                # 空网格
 
assert numIslands([["1"]]) == 1           # 单格
 
# 特殊
 
assert numIslands([["0"]]) == 0
 

---

关联题型

关联题型	常见结合方式	典型题目
回溯	DFS回溯	200岛屿数量, 79单词搜索
堆	Dijkstra最小堆	743网络延迟时间
队列	BFS队列	994腐烂橘子, 127单词接龙