开始前应具备
- 掌握树的 DFS 与 BFS
- 理解集合和邻接表
- 能区分有向边与无向边
CHAPTER 07 · 关系网络
把网格、依赖和连通关系统一成图,选择深度或广度优先搜索。
BEFORE LEARNING
网格、依赖关系和状态转换都可以统一成图。先明确节点与边,再选择 DFS、BFS、拓扑、并查集或最短路。
开始前应具备
完成本章后
CORE LESSONS
LESSON
对象之间存在连接、依赖或一次操作可转移到另一个状态时,把问题抽象成图。
邻接表列出每个节点能到达的邻居。visited 应在进入递归或入队时标记,避免同一节点被重复加入搜索边界。
def dfs(node):
if node in visited: return
visited.add(node)
for neighbor in graph[node]: dfs(neighbor)LESSON
二维网格中按上下左右连通,要求连通块数量、面积或最短扩散时间。
网格无需显式建邻接表,四个方向就是动态生成的边。统计连通块用 DFS/BFS 均可;多个起点同时扩散时,应把所有起点一次性加入 BFS。
for each cell:
if is_new_component(cell):
answer += 1
flood_fill(cell)LESSON
依赖关系要求先后次序时用拓扑排序;动态合并集合并判断连通性时用并查集。
拓扑排序通过入度或递归状态检测有向环。并查集维护每个连通分量的代表节点,通过路径压缩和按秩合并提高查询效率。
queue = all_zero_indegree_nodes
while queue:
node = pop()
for next in graph[node]:
indegree[next] -= 1
if indegree[next] == 0: push(next)LESSON
求最少步数或最小总代价。边权全相等用 BFS,边权非负且不同用 Dijkstra。
Dijkstra 每次确定当前距离最小的未完成节点,并用它松弛邻边。优先队列中的旧距离可能过期,弹出时需要跳过。
dist[start] = 0
heap = [(0, start)]
while heap:
d, node = pop_min()
if d != dist[node]: continue
for next, weight in graph[node]: relax()READING
先读完本站讲义并尝试练习;遇到推导不清的地方,再回到原始教程深入阅读。
PRACTICE LADDER
题量由知识点决定,不再固定为 5 道。先完成“入门”和“模板”,再做变式与综合;挑战题可以留到复习阶段。
1 道 · 依次完成
Clone Graph
为什么选:用映射同时承担 visited 和克隆节点索引。
3 道 · 依次完成
Number of Islands
为什么选:标准连通块计数。
Max Area of Island
为什么选:让搜索返回当前连通块面积。
Rotting Oranges
为什么选:所有腐烂橘子同时作为多源 BFS 起点。
3 道 · 依次完成
Course Schedule
为什么选:用处理节点数判断有向依赖是否成环。
Course Schedule II
为什么选:在环检测基础上输出实际拓扑顺序。
Redundant Connection
为什么选:用 union 失败定位无向图中的冗余边。
1 道 · 依次完成
Network Delay Time
为什么选:完整实现邻接表、最短距离和优先队列松弛。
PERSONAL NOTEBOOK
笔记保存在当前浏览器