CHAPTER 07 · 关系网络

图、DFS 与 BFS

把网格、依赖和连通关系统一成图,选择深度或广度优先搜索。

4 个知识小节8 道分层练习6–7 天 建议周期
展开本章目录
  1. 学习之前
  2. 1. 建图、邻接表与 visited
  3. 2. 网格 DFS/BFS 与多源扩散
  4. 3. 拓扑顺序与并查集
  5. 4. 无权 BFS 与 Dijkstra
  6. 延伸阅读
  7. 分层练习
  8. 我的笔记
00

BEFORE LEARNING

先理解为什么学

网格、依赖关系和状态转换都可以统一成图。先明确节点与边,再选择 DFS、BFS、拓扑、并查集或最短路。

开始前应具备

  • 掌握树的 DFS 与 BFS
  • 理解集合和邻接表
  • 能区分有向边与无向边

完成本章后

  • 会建邻接表
  • 正确维护 visited
  • 掌握拓扑排序和最短路的入口
01

CORE LESSONS

知识讲义

01

LESSON

建图、邻接表与 visited

什么时候想到它?

对象之间存在连接、依赖或一次操作可转移到另一个状态时,把问题抽象成图。

邻接表列出每个节点能到达的邻居。visited 应在进入递归或入队时标记,避免同一节点被重复加入搜索边界。

推导步骤

  1. 定义节点和边
  2. 确认边是否有方向和权重
  3. 构建邻接表或动态生成邻居
  4. 选择入队/递归时标记 visited
思维模板 / 伪代码
def dfs(node):
  if node in visited: return
  visited.add(node)
  for neighbor in graph[node]: dfs(neighbor)
02

LESSON

网格 DFS/BFS 与多源扩散

什么时候想到它?

二维网格中按上下左右连通,要求连通块数量、面积或最短扩散时间。

网格无需显式建邻接表,四个方向就是动态生成的边。统计连通块用 DFS/BFS 均可;多个起点同时扩散时,应把所有起点一次性加入 BFS。

推导步骤

  1. 遍历网格寻找未访问起点
  2. 检查边界和可通行条件
  3. 搜索中立即标记
  4. 多源问题把全部源点加入第 0 层
思维模板 / 伪代码
for each cell:
  if is_new_component(cell):
    answer += 1
    flood_fill(cell)
03

LESSON

拓扑顺序与并查集

什么时候想到它?

依赖关系要求先后次序时用拓扑排序;动态合并集合并判断连通性时用并查集。

拓扑排序通过入度或递归状态检测有向环。并查集维护每个连通分量的代表节点,通过路径压缩和按秩合并提高查询效率。

推导步骤

  1. 拓扑:统计入度并把 0 入度节点入队
  2. 每移除一条边就降低后继入度
  3. 并查集:find 找代表,union 合并代表
  4. 用处理节点数或 union 失败判断环
思维模板 / 伪代码
queue = all_zero_indegree_nodes
while queue:
  node = pop()
  for next in graph[node]:
    indegree[next] -= 1
    if indegree[next] == 0: push(next)
04

LESSON

无权 BFS 与 Dijkstra

什么时候想到它?

求最少步数或最小总代价。边权全相等用 BFS,边权非负且不同用 Dijkstra。

Dijkstra 每次确定当前距离最小的未完成节点,并用它松弛邻边。优先队列中的旧距离可能过期,弹出时需要跳过。

推导步骤

  1. 确定起点和距离初值
  2. 从优先队列取最小候选
  3. 跳过比已知距离更大的旧记录
  4. 尝试用当前节点改善邻居距离
思维模板 / 伪代码
dist[start] = 0
heap = [(0, start)]
while heap:
  d, node = pop_min()
  if d != dist[node]: continue
  for next, weight in graph[node]: relax()
02

READING

延伸阅读

先读完本站讲义并尝试练习;遇到推导不清的地方,再回到原始教程深入阅读。

03

PRACTICE LADDER

按作用分层练习

题量由知识点决定,不再固定为 5 道。先完成“入门”和“模板”,再做变式与综合;挑战题可以留到复习阶段。

入门认识结构模板独立复现变式迁移条件综合组合技巧挑战延后突破
01

建图、邻接表与 visited

1 道 · 依次完成

LC 133模板中等

克隆图

Clone Graph

为什么选:用映射同时承担 visited 和克隆节点索引。

图遍历建议 35 分钟
打开 LeetCode ↗
02

3 道 · 依次完成

LC 200入门中等

岛屿数量

Number of Islands

为什么选:标准连通块计数。

网格 DFS建议 30 分钟
打开 LeetCode ↗
LC 695变式中等

岛屿的最大面积

Max Area of Island

为什么选:让搜索返回当前连通块面积。

网格 DFS建议 30 分钟
打开 LeetCode ↗
LC 994综合中等

腐烂的橘子

Rotting Oranges

为什么选:所有腐烂橘子同时作为多源 BFS 起点。

多源 BFS建议 40 分钟
打开 LeetCode ↗
03

拓扑顺序与并查集

3 道 · 依次完成

LC 207模板中等

课程表

Course Schedule

为什么选:用处理节点数判断有向依赖是否成环。

拓扑排序建议 40 分钟
打开 LeetCode ↗
LC 210变式中等

课程表 II

Course Schedule II

为什么选:在环检测基础上输出实际拓扑顺序。

拓扑序列建议 40 分钟
打开 LeetCode ↗
LC 684综合中等

冗余连接

Redundant Connection

为什么选:用 union 失败定位无向图中的冗余边。

并查集建议 40 分钟
打开 LeetCode ↗
04

无权 BFS 与 Dijkstra

1 道 · 依次完成

LC 743挑战中等

网络延迟时间

Network Delay Time

为什么选:完整实现邻接表、最短距离和优先队列松弛。

Dijkstra建议 60 分钟
打开 LeetCode ↗
04

PERSONAL NOTEBOOK

我的学习笔记

我如何识别这个模式?今天卡在哪里?下次需要先检查什么?

笔记保存在当前浏览器