🕸️ 01-数据结构与算法 · 主题 10:图(BFS/DFS/拓扑/并查集/最短路径/Trie)¶
图论题在秋招里占比逐年升高:网格 DFS、拓扑排序、并查集、最短路是四大高频模板。 本 notebook 目标:掌握两种表示 → 背熟四大模板 → 吃透 8 道高频题 → 通过 25 道自测。
前置:主题 4(队列)、主题 6(树/DFS)。运行环境:Python 3.8+(用 heapq/collections 标准库)。
核心概念¶
(a) 🗂️ 图论四大模板:BFS、DFS、拓扑、并查集 + Dijkstra 与 Trie¶
图论题在秋招占比逐年升高:网格 BFS、拓扑排序、并查集、最短路是四大高频模板。本 notebook 掌握两种表示,背熟四大模板,吃透 8 道高频题 + Trie。
flowchart TB
N1["🕸️ 图的两种表示"] --> N2["BFS:逐层扩展找最短"]
N1 --> N3["DFS:深入探索找连通块"]
N2 --> N4["网格题:岛屿 200 / 腐烂橘子 994"]
N3 --> N5["拓扑排序:207 / 210 Kahn"]
N3 --> N6["并查集:684 / Kruskal 最小生成树"]
N5 --> N7["Dijkstra 最短路径:743"]
N6 --> N8["Trie 前缀树:208"]
N8 --> N9["复杂度总表与选型速查"]
- N1 · 图的两种表示:邻接矩阵(matrix[u][v])查边 O(1) 但费空间;邻接表(list 存邻居)省空间,是 Python 题解的主流。先想清楚表示再写遍历。
- N2 · BFS:用队列逐层扩展,第一次到达某点的层数就是无权图最短路径;网格题里上下左右四方向扩展是通用模板。
- N3 · DFS:用递归深入探索,适合数连通块、判环、回溯类问题;注意用 visited 或原地标记防重复访问。
- N4 · 网格题:岛屿数量(200)是 DFS 淹没整个连通块计数;腐烂的橘子(994)是多源 BFS 分层计数——所有源头同时扩散,层数就是时间。
- N5 · 拓扑排序:Kahn 算法先找入度为 0 的节点不断移除:207 判有环,210 输出拓扑序列——有环就无法拓扑,这是关键结论。
- N6 · 并查集:"找爸爸 + 路径压缩 + 按秩合并"维护连通性:684 冗余连接找成环的那条边;Kruskal 最小生成树也靠它把边从小到大接入。
- N7 · Dijkstra:用优先队列每次取"当前距离最近"的节点松弛邻居,得到单源最短路(743 网络延迟时间);不带权图直接用 BFS 即可。
- N8 · Trie 前缀树:把字符串按字符存成树:插入/查找/前缀查询都是 O(len),是 208 的答案,也是敏感词过滤等工程场景的基础。
- N9 · 复杂度总表与选型速查:结尾一张选型速查:看问题要"连通性/最短路/有向无环/前缀查询"分别选哪套模板,配合 L1/L2/L3 自测清单。
§1 图的表示与复杂度¶
两种主流表示¶
| 表示 | 结构 | 查询边 | 空间 | 适用 |
|---|---|---|---|---|
| 邻接矩阵 | matrix[u][v] |
$O(1)$ | $O(V^2)$ | 稠密图、小规模 |
| 邻接表 | adj[u] = [v,...] |
$O(deg(u))$ | $O(V+E)$ | 绝大多数题 |
Python 邻接表常用写法:
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u) # 无向图加双向
遍历复杂度¶
$$\text{DFS/BFS 时间} = O(V + E)$$
每个点进队列/栈一次、每条边被访问一次。
有向 vs 无向 / 有权 vs 无权¶
- 无权图最短路径 → BFS(队列)
- 有权图最短路径 → Dijkstra(堆)
- 有向无环(DAG) → 拓扑排序
- 连通性/环 → 并查集 / DFS
§2 BFS 与 DFS 模板(背熟)¶
BFS(逐层扩展,最短路径)¶
from collections import deque
q = deque([起点]); visited = {起点}
while q:
node = q.popleft()
for nb in adj[node]:
if nb not in visited:
visited.add(nb)
q.append(nb)
为什么 BFS 找最短:第 $k$ 层出队的节点都是距离起点 $k$ 步的——首次访问即最短。
DFS(深入探索,遍历/连通块)¶
def dfs(u):
visited.add(u)
for nb in adj[u]:
if nb not in visited:
dfs(nb)
⚠️ visited 去重是灵魂:无向图必须去重,否则死循环;有向图也要防重复入队。
网格 BFS 模板(200 岛屿数量 / 1091 最短路径)¶
- 方向数组:
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)](下 / 上 / 右 / 左) - 队列存三元组
(r, c, d):d为已走步数,首次出队即最短路径(1091 模板) - 入队即标记 visited:先
visited.add再入队,防止同一格被重复入队(200 岛屿的"淹没"同理) - 边界检查:
0 <= nr < R and 0 <= nc < C,再判断grid[nr][nc]是否可走
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
# ============== 建图工具 + BFS / DFS 遍历模板 ==============
# 【题目目标】演示图的邻接表建图工具,以及 BFS(逐层扩展)与 DFS(深入探索)
# 两种遍历;BFS 用于无权图最短路径,DFS 用于连通块/判环
# 【算法思路】邻接表:[[] for _ in range(n)],无向图要加双向边;BFS 用队列逐层
# 扩展,入队即标记 visited(防止同一节点重复入队),首次访问的距离即
# 最短路径;DFS 用递归深入探索,visited 去重是灵魂——无向图不标记
# 会死循环
# 【变量含义】n:节点数;edges:边列表 (u,v);directed:是否单向;adj:邻接表;
# q:BFS 队列;visited:已访问集合;res:访问顺序记录;u/v:节点;
# go(u):DFS 递归函数
# 【循环不变量】每个节点至多入队/入栈一次(由 visited 保证)
# 【递归终止】BFS:队列为空时结束;DFS:某节点无未访问邻居时回溯返回
# 【关键边界】无向图必须把反向边也加入;BFS 必须先 visited.add 再入队;DFS 进入
# 函数先标记再继续访问邻居
# 【复杂度】两者均为 O(V+E) 时间(每点进队一次、每边看一次)、O(V) 空间
# 建图工具 + BFS 模板:把边列表转成邻接表(可选有向/无向),再演示队列逐层遍历
from collections import deque
# 图的邻接表建图工具:把边列表转成邻接表,可选有向/无向
def build_adj(n, edges, directed=False):
adj = [[] for _ in range(n)] # 为每个节点准备一个空邻居列表
for u, v in edges: # 遍历每条边 (u, v)
adj[u].append(v) # u 的邻居加入 v
if not directed: # 无向图要加反向边
adj[v].append(u) # v 的邻居也加入 u
return adj # 返回建好的邻接表
# 例图:0-1, 0-2, 1-3, 2-3(无向图)
adj = build_adj(4, [(0, 1), (0, 2), (1, 3), (2, 3)]) # 用上面的工具建图
# BFS(广度优先):用队列逐层扩展,先访问距离起点近的节点
# 特点:入队即标记 visited,防止同一节点被重复入队;首次访问即最短路径(无权图)
def bfs(start, adj):
res = [] # 记录访问顺序
q = deque([start]) # 队列:初始放入起点
visited = {start} # 已访问集合,起点先标记
while q: # 队列非空就继续扩展
u = q.popleft() # 取出队首节点
res.append(u) # 记录访问顺序
for v in adj[u]: # 遍历 u 的所有邻居
if v not in visited: # 邻居还没访问过才处理
visited.add(v) # 先标记,防止重复入队
q.append(v) # 加入队列,下一层再访问
return res # 返回 BFS 访问顺序
# DFS(深度优先):用递归深入探索,一路走到头再回溯
# 特点:visited 去重是灵魂,无向图不标记会死循环
def dfs(start, adj):
res = [] # 记录访问顺序
visited = set() # 已访问集合
def go(u): # 递归访问节点 u
visited.add(u) # 标记 u 已访问(防死循环)
res.append(u) # 记录访问顺序
for v in adj[u]: # 遍历 u 的所有邻居
if v not in visited: # 邻居未访问则递归深入
go(v) # 深入探索
go(start) # 从起点开始
return res # 返回 DFS 访问顺序
print('BFS from 0:', bfs(0, adj)) # 期望 [0, 1, 2, 3]
print('DFS from 0:', dfs(0, adj)) # 期望 [0, 1, 3, 2](按邻接表顺序)
BFS from 0: [0, 1, 2, 3] DFS from 0: [0, 1, 3, 2]
§3 岛屿数量(LeetCode 200):连通块计数¶
题目:1 表示陆地,求连通的陆地块数(上下左右)。
思路:遍历网格,遇到未访问的 1 就 DFS/BFS 淹没整块并计数:
$$\text{岛屿数} = \sum_{\text{起点} \in \text{未访问陆地}} 1$$
网格 DFS 四方向:
$$(i \pm 1, j), \quad (i, j \pm 1)$$
复杂度:$O(R \times C)$(每个格子至多访问一次),空间 $O(R \times C)$ 最坏。
# ============== 200 岛屿数量(连通块计数 + 原地淹没) ==============
# 【题目目标】2D 网格中 '1' 为陆地,求上下左右四方向连通的陆地块数
# 【算法思路】双重循环扫描网格,遇到未访问的 '1' 就计数 +1,并用 DFS「淹没」
# (sink)把整块连通陆地全部改成 '0'——原地标记,无需额外 visited
# 数组;这样后面再遇到同一块岛屿的格子时已是 '0',不会重复计数
# 【变量含义】R/C:网格行数/列数;grid:网格;sink(i,j):从陆地格子 (i,j) 出发
# 向四方向递归淹没整块岛屿;count:岛屿计数;i/j:格子坐标
# 【循环不变量】每次调用 sink 会把一整块连通陆地全部置 '0',此后外层扫描不会
# 再对同一岛屿计数
# 【递归终止】sink 中遇到越界或已是 '0'(水)的格子直接返回(递归边界)
# 【关键边界】先判越界(0<=i<R 且 0<=j<C)再访问 grid[i][j],顺序不能反;
# 四方向的递归顺序无关紧要;题目保证网格非空
# 【复杂度】O(R×C) 时间(每个格子至多被访问一次)、最坏 O(R×C) 递归栈空间
# 200. 岛屿数量:1 表示陆地,求上下左右连通的陆地块数
# 思路:遍历网格,遇到未访问的 1 就用 DFS 把整块岛屿「淹没」成 0 并计数,避免重复访问
def num_islands(grid):
R, C = len(grid), len(grid[0]) # 网格行数、列数
def sink(i, j): # 从陆地格子 (i, j) 出发,淹没整块岛屿
# 原地标记:把连通块全部变成 0,避免额外 visited
if not (0 <= i < R and 0 <= j < C) or grid[i][j] == '0':
return # 越界或已经是水 → 直接返回
grid[i][j] = '0' # 把当前陆地改成水(原地标记)
sink(i + 1, j); sink(i - 1, j); sink(i, j + 1); sink(i, j - 1) # 向四个方向递归淹没
count = 0 # 岛屿计数
for i in range(R): # 遍历每一行
for j in range(C): # 遍历每一列
if grid[i][j] == '1': # 发现一块新陆地
count += 1 # 岛屿数加 1
sink(i, j) # 淹没整块岛屿,防止重复计数
return count # 返回岛屿总数
# 测试用例:左上角一块岛、中间一块、右下角一块 → 共 3 个岛屿
g = [
['1', '1', '0', '0', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '1', '0', '0'],
['0', '0', '0', '1', '1'],
]
print('num_islands =', num_islands(g)) # 期望 3
print('num_islands(全0) =', num_islands([['0', '0'], ['0', '0']])) # 0
print('num_islands(全1) =', num_islands([['1', '1'], ['1', '1']])) # 1
num_islands = 3 num_islands(全0) = 0 num_islands(全1) = 1
§4 腐烂的橘子(994):多源 BFS 分层¶
题目:烂橘子每分钟感染相邻好橘子,求全部烂掉所需分钟(不可能则 -1)。
思路:把所有初始烂橘子一起放进队列(多源 BFS),逐层扩散:
- 层数 = 分钟数(在出队时记录
step) - 结束时若还有好橘子 → -1
为什么多源 BFS:多个源头同时扩散,等价于超级源点连接所有烂橘子 → 经典 BFS 单源模型。
复杂度:$O(R \times C)$。
# ============== 994 腐烂的橘子(多源 BFS 分层) ==============
# 【题目目标】网格中 2 为烂橘子、1 为好橘子、0 为空位;每分钟烂橘子会感染上下
# 左右相邻的好橘子,求全部烂掉所需分钟数,无法全部烂掉则返回 -1
# 【算法思路】多源 BFS:把所有初始烂橘子连同时间 t=0 一起入队(等价于引入一个
# 超级源点连向所有烂橘子,退化成经典单源 BFS);逐层扩散,感染一个好
# 橘子时记录其被感染时间为 t+1;统计过程中好橘子数 fresh 递减,结束时
# fresh 仍 >0 说明有好橘子永远够不着,返回 -1
# 【变量含义】R/C:行数/列数;q:队列(行, 列, 时间 t);fresh:剩余好橘子数;
# minutes:最大层数即所需分钟数;(i,j,t):格子位置与被感染时间;
# (ni,nj):四方向相邻格子
# 【循环不变量】fresh 随感染单调递减;minutes 恒为「当前已感染的最远层数」
# 【递归终止】队列为空即结束(所有可被感染的橘子都已处理完毕)
# 【关键边界】扩展邻居前先判越界与 grid[ni][nj]==1;感染后立即把格子改为 2、
# fresh-=1 并记录时间入队(入队即标记,防重复入队);初始就没有好
# 橘子时直接返回 0
# 【复杂度】O(R×C) 时间与空间
# 994. 腐烂的橘子:烂橘子每分钟感染相邻好橘子,求全部烂掉所需分钟数,不可能则 -1
# 思路:多源 BFS——把所有初始烂橘子一起入队,逐层扩散;层数 t 就是分钟数;结束时还有好橘子则无解
def oranges_rotting(grid):
R, C = len(grid), len(grid[0]) # 网格行数、列数
q = deque() # BFS 队列,存放(行, 列, 时间)
fresh = 0 # 好橘子的个数
for i in range(R): # 扫描整个网格
for j in range(C):
if grid[i][j] == 2: # 烂橘子:作为多源 BFS 的初始源点
q.append((i, j, 0)) # 初始时间 t = 0
elif grid[i][j] == 1: # 好橘子:计数
fresh += 1 # 好橘子数量加 1
minutes = 0 # 记录最大层数(即所需分钟数)
while q: # 队列非空就继续逐层感染
i, j, t = q.popleft() # 取出一个烂橘子及其被感染的时间
minutes = max(minutes, t) # 更新最大分钟数
for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)): # 四个方向:下、上、右、左
ni, nj = i + di, j + dj # 相邻格子的坐标
if 0 <= ni < R and 0 <= nj < C and grid[ni][nj] == 1: # 在网格内且是未感染的好橘子
grid[ni][nj] = 2 # 感染
fresh -= 1 # 好橘子数量减 1
q.append((ni, nj, t + 1)) # 新烂橘子入队,时间为 t+1
return minutes if fresh == 0 else -1 # 全部烂完返回分钟数,否则返回 -1
print('test1:', oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]])) # 4
print('test2:', oranges_rotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]])) # -1(角上孤立)
print('test3:', oranges_rotting([[0, 2]])) # 0(无新鲜)
print('test4:', oranges_rotting([[2, 2, 2], [2, 2, 2]])) # 0
test1: 4 test2: -1 test3: 0 test4: 0
§5 拓扑排序(207 课程表):Kahn 算法¶
问题:判断有向图是否有环(能否完成所有课程)。
Kahn 算法(BFS 版):
- 统计每个节点的入度
- 入度为 0 的节点入队(无前置依赖)
- 出队时把它的所有后继入度 -1,减到 0 就入队
- 出队总数 < 节点数 → 有环(环上节点永远入度 > 0)
复杂度:$O(V + E)$。
💡 拓扑序不唯一;「字典序最小」拓扑序 = 用最小堆替换队列。
# ============== 207 课程表(Kahn 拓扑排序判环) ==============
# 【题目目标】num_courses 门课程与先修关系 prerequisites,判断能否修完所有课程
# (等价于判断先修关系构成的有向图是否存在环)
# 【算法思路】Kahn 拓扑排序(BFS 版):① 统计每个节点的入度;② 入度为 0 的节点
# (无前置依赖)入队;③ 出队时把它的所有后继节点入度 -1,减到 0 再
# 入队;④ 能出队的课程数 done 等于课程总数 ⟹ 无环可修完
# 【变量含义】adj:邻接表,b→a 表示先修 b 才能学 a;indeg:每个节点的入度
# (前置课门数);q:队列;done:已出队(已完成)的课程数;u/v:节点
# 【循环不变量】入度减到 0 的节点 ⟺ 它的所有前置课程都已修完,可以入队
# 【递归终止】while 队列非空循环,队列为空即结束
# 【关键边界】核心结论:出队总数 < 节点数 ⟺ 存在环(环上节点入度永远 > 0,
# 永远不会入队);建边方向:prerequisites 的 [a,b] 表示 b 是 a 的前置,
# 应建 b→a 且 indeg[a] += 1,方向别搞反
# 【复杂度】O(V+E) 时间、O(V) 空间
# 207. 课程表:判断能否修完所有课程(即先修关系构成的有向图是否有环)
# 思路:Kahn 拓扑排序——不断移除入度为 0 的节点;若能移除全部节点则无环,否则有环无法完成
def can_finish(num_courses, prerequisites):
adj = [[] for _ in range(num_courses)] # 邻接表:b → a 表示学完 b 才能学 a
indeg = [0] * num_courses # 入度:每个节点有几门前置课
for a, b in prerequisites: # b 是 a 的前置
adj[b].append(a) # 建边 b → a
indeg[a] += 1 # a 的入度加 1
q = deque([i for i in range(num_courses) if indeg[i] == 0]) # 入度为 0 的课程先入队(无前置依赖)
done = 0 # 统计已完成(出队)的课程数
while q: # 队列非空继续处理
u = q.popleft() # 取出一门可修的课
done += 1 # 完成数加 1
for v in adj[u]: # 把它的所有后继课程入度减 1
indeg[v] -= 1 # 前置课少了一门
if indeg[v] == 0: # 前置全部修完 → 可以入队
q.append(v) # 加入队列
return done == num_courses # 全部出队 = 无环
print('test1:', can_finish(2, [[1, 0]])) # True
print('test2:', can_finish(2, [[1, 0], [0, 1]])) # False(环)
print('test3:', can_finish(4, [[1, 0], [2, 0], [3, 1], [3, 2]])) # True
print('test4:', can_finish(1, [])) # True
test1: True test2: False test3: True test4: True
§5.1 课程表 II(210):输出拓扑序列¶
题目:给定课程数与先修关系,返回一种可行修课顺序;有环则返回 []。
与 207 的区别:Kahn 算法把出队节点收集进结果列表;结果长度 == numCourses 则有解,否则有环返回空数组。
# ============== 210 课程表 II(拓扑排序输出序列) ==============
# 【题目目标】给定课程数与先修关系,返回一种可行的修课顺序;存在环则返回空列表
# 【算法思路】与 207 完全相同的 Kahn 拓扑排序,只是把出队节点的顺序收集进 result
# 列表:出队即确定一个位置;最终 order 长度等于课程数则有解,不足说明
# 有环,返回 []
# 【变量含义】adj:邻接表 b→a;indeg:入度数组;q:队列;order:收集的拓扑序列;
# u/v:节点;num_courses:课程总数
# 【循环不变量】出队顺序即一种合法修课顺序:每门课出队时它的全部前置都已出队
# 【递归终止】队列为空即结束
# 【关键边界】有环时不能返回「部分拓扑序」,必须返回空列表 [](与 207 的布尔
# 判断相区别);建边方向与入度维护同 207
# 【复杂度】O(V+E) 时间、O(V) 空间
# 210. 课程表 II(拓扑排序输出序列):Kahn 算法不断移除入度为 0 的节点,有环则返回空列表
from collections import deque
# 210. 课程表 II:返回一种可行的修课顺序;存在环则返回空列表
# 思路:与 207 相同,Kahn 拓扑排序把出队顺序收集起来;出队数量不足说明有环
def find_order(num_courses, prerequisites):
adj = [[] for _ in range(num_courses)] # 邻接表:b → a
indeg = [0] * num_courses # 入度数组
for a, b in prerequisites: # b 是 a 的前置
adj[b].append(a) # 建边 b → a
indeg[a] += 1 # a 的入度加 1
q = deque([i for i in range(num_courses) if indeg[i] == 0]) # 入度为 0 的课程先入队
order = [] # 收集拓扑序列
while q: # 队列非空继续处理
u = q.popleft() # 取出一门可修的课
order.append(u) # 出队即确定一个位置
for v in adj[u]: # 后继课程入度减 1
indeg[v] -= 1
if indeg[v] == 0: # 前置修完可入队
q.append(v) # 加入队列
return order if len(order) == num_courses else [] # 有环 → []
print('test1:', find_order(2, [[1, 0]])) # [0, 1]
print('test2:', find_order(2, [[1, 0], [0, 1]])) # [](环)
print('test3:', find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])) # [0, 1, 2, 3]
assert find_order(2, [[1, 0]]) == [0, 1]
assert find_order(2, [[1, 0], [0, 1]]) == []
test1: [0, 1] test2: [] test3: [0, 1, 2, 3]
# ===== 并查集模板 / 684 冗余连接 / 547 省份数量 =====
# 【题目目标】实现并查集(Union-Find)模板——动态维护集合连通性,支持查找与合并,
# 单次操作近似 O(α(n));并解决 684 冗余连接(删掉使图成环的那条边)与
# 547 省份数量(求直接或间接相连城市的连通分量个数)
# 【算法思路】find:沿父指针找根,途中把节点挂到祖父节点(路径压缩,拉平树);
# union:先 find 两端根,若相同说明已连通(成环);否则把矮树挂到高树
# (按秩合并)保持平衡;684 依次合并每条边,union 返回 False 的那条就是
# 多余边;547 遍历邻接矩阵上三角,直连则合并,最后统计不同根的个数
# 【变量含义】parent:每个节点的父节点(初始指向自己);rank:树的高度(秩);
# find(x):返回 x 所在集合的根;union(a,b):合并两个集合;ra/rb:两端
# 根;edges:边列表;is_connected:城市邻接矩阵
# 【循环不变量】所有 parent 链最终都指向各自集合的代表(根);rank 记录树高用于
# 平衡合并
# 【递归终止】无递归;find 的 while 循环直到 parent[x]==x(到达根)停止
# 【关键边界】684 节点编号从 1 开始,UnionFind 要多开一位(len+1);union 返回
# False 即为成环边;547 只遍历上三角(j>i)避免同一对城市重复合并;
# 相同秩合并任选一边并让高度 +1
# 【复杂度】单次 find/union 近似 O(α(n));684 为 O(E·α(n));547 为 O(n²·α(n))
# 并查集模板:维护集合连通性,支持合并(union)与查找(find),近似 O(1)
# 两个优化:路径压缩(find 时把沿途节点直接指向根)+ 按秩合并(矮树挂到高树)
class UnionFind:
def __init__(self, n):
self.parent = list(range(n)) # 初始每个节点是自己的父节点(各自成集合)
self.rank = [0] * n # 树的高度(秩),用于按秩合并
def find(self, x):
# 路径压缩
while self.parent[x] != x: # 一直向上找,直到根节点
self.parent[x] = self.parent[self.parent[x]] # 把 x 挂到祖父节点,压缩路径
x = self.parent[x] # 继续上移
return x # 返回根节点
def union(self, a, b):
ra, rb = self.find(a), self.find(b) # 分别找 a、b 的根
if ra == rb:
return False # 已连通(成环)
if self.rank[ra] < self.rank[rb]: # 矮树挂到高树上(按秩合并)
self.parent[ra] = rb # ra 的根挂到 rb 下
elif self.rank[ra] > self.rank[rb]:
self.parent[rb] = ra # rb 的根挂到 ra 下
else:
self.parent[rb] = ra # 两树同高:随便挂一个,高度加 1
self.rank[ra] += 1
return True # 合并成功(原来不连通)
# 684. 冗余连接:无向图多加了一条边形成环,把它删掉
# 思路:依次合并每条边,如果某条边的两端已经连通(find 相同),这条边就是成环的多余边
def find_redundant_connection(edges):
uf = UnionFind(len(edges) + 1) # 节点编号从 1 开始,多开一位
for u, v in edges: # 遍历每条边
if not uf.union(u, v): # 合并失败说明 u、v 早已连通
return [u, v] # 第一条成环边
return [] # 不会走到(题目保证有冗余边)
print('test1:', find_redundant_connection([[1, 2], [1, 3], [2, 3]])) # [2,3]
print('test2:', find_redundant_connection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]])) # [1,4]
# 547. 省份数量:把直接或间接相连的城市归为一省,求连通分量个数
def find_circle_num(is_connected):
n = len(is_connected) # 城市个数
uf = UnionFind(n) # 初始化并查集
for i in range(n): # 遍历矩阵上三角
for j in range(i + 1, n):
if is_connected[i][j]: # 两城市直接相连 → 合并
uf.union(i, j) # 归入同一省份
return len({uf.find(i) for i in range(n)}) # 不同根节点的个数 = 省份数
print('省份数量:', find_circle_num([[1, 1, 0], [1, 1, 0], [0, 0, 1]])) # 2
print('省份数量:', find_circle_num([[1, 0, 0], [0, 1, 0], [0, 0, 1]])) # 3
test1: [2, 3] test2: [1, 4] 省份数量: 2 省份数量: 3
§6.1 Kruskal 最小生成树¶
思路:边按权值升序排序,用并查集依次尝试连边——find(u) != find(v) 才合并并累加权值,已连通(成环)则跳过。连满 n-1 条边即成 MST。
复杂度:$O(E \log E)$(排序为主,并查集近常数)。
# ============== Kruskal 最小生成树(并查集 + 贪心) ==============
# 【题目目标】给定 n 个节点与带权边列表,求最小生成树(MST)的总权值与选边集合
# 【算法思路】边按权值升序排序(贪心:先考虑最小边),用并查集依次尝试连边:
# 两端不连通(不成环)才合并并累计权值、记录到 mst;连通则跳过;
# 连满 n-1 条边即构成最小生成树
# 【变量含义】n:节点数;edges:(u,v,w) 带权边;uf:并查集(复用 §6 模板);
# total:MST 总权值;mst:选中的边集合;w:边权
# 【循环不变量】已选边集合始终构成森林,且是「按当前已扫描的最小边」下最优的选择
# (贪心正确性由最小生成树的 cut property 保证)
# 【递归终止】无递归;循环遍历完全部边即结束
# 【关键边界】union 返回 False(两端已连通=成环)时跳过该边;最小生成树恰好需要
# n-1 条边;题目默认图连通(不连通时 total 欠缺,可加边数判断)
# 【复杂度】O(E log E) 时间(排序主导),O(V) 空间(并查集)
# Kruskal 最小生成树:边按权值升序,用并查集依次尝试连边,不成环就加入 MST
def kruskal(n, edges):
uf = UnionFind(n) # 复用 §6 的并查集(路径压缩 + 按秩合并)
total = 0 # 最小生成树的总权值
mst = [] # 收集选中的边
for u, v, w in sorted(edges, key=lambda e: e[2]): # 按边权升序贪心
if uf.union(u, v): # 不成环才合并
total += w # 累加权值
mst.append((u, v, w)) # 记录这条边
return total, mst # 返回总权值与选边集合
n = 4 # 4 个节点
edges = [(0, 1, 1), (0, 2, 2), (1, 2, 3), (1, 3, 4), (2, 3, 5)] # 边列表:(u, v, 权值)
total, mst = kruskal(n, edges) # 运行 Kruskal
print('总权:', total) # 7 = 1 + 2 + 4
print('MST 边集:', mst)
assert total == 7
assert len(mst) == n - 1
总权: 7 MST 边集: [(0, 1, 1), (0, 2, 2), (1, 3, 4)]
§7 Dijkstra 最短路径(743 网络延迟时间)¶
适用:非负权单源最短路。
思路(贪心 + 堆):每次从堆里取「当前距离最小」的未确定节点,松弛它的所有出边:
$$dist[v] = \min(dist[v],\ dist[u] + w(u, v))$$
复杂度:$O((V + E) \log V)$(堆优化)。
为什么 Dijkstra 正确:非负权下,堆顶的 dist 已不可能再被其他路径改进(任何绕路都 ≥ 当前值)——贪心成立。
⚠️ 有负权必须用 Bellman-Ford / SPFA;Dijkstra 会错。
✍️ §7.1 手算 Dijkstra:5 节点加权图,最短距离表一步步更新¶
Dijkstra 每步选"未确定中距离最小"的节点松弛邻居——5 个节点手算,把
dist表的更新变成可见过程。
设定:节点 A–E,无向边 A–B=4、A–C=2、B–C=1、B–D=5、C–D=8、C–E=10、D–E=2,起点 A。
第 1 步:初始化 $\text{dist}=(A:0,\ B:4,\ C:2,\ D:\infty,\ E:\infty)$,选最小未确定 C(2)。
第 2 步:松弛 C 的邻居(B、D、E)
$$B=\min(4,\ 2+1)=3,\qquad D=\min(\infty,\ 2+8)=10,\qquad E=\min(\infty,\ 2+10)=12$$
选 B(3)。
第 3 步:松弛 B 的邻居(A 已定,D、C 已优于)
$$D=\min(10,\ 3+5)=8$$
选 D(8);第 4 步:$E=\min(12,\ 8+2)=10$。最终:
| 节点 | A | B | C | D | E |
|---|---|---|---|---|---|
| dist | 0 | 3 | 2 | 8 | 10 |
手算收获:
- 每步选"未确定中最小"的节点是贪心:它的 dist 从此不会再被更新(非负权保证)——这就是 Dijkstra 正确性核心(§11.1 追问可展开)
- 松弛操作 $\text{dist}[v]=\min(\text{dist}[v],\ \text{dist}[u]+w)$:每一条边最多松弛一次,所以 $O(E\log V)$(堆优化)
- 负权边会破坏"已确定不变"性质——Dijkstra 不能处理负权,需 Bellman-Ford/SPFA(面试高频对比)
- 本例最短路径:A→E = A-C-B-D-E = $2+1+5+2=10$——沿 dist 表的"前驱链"回溯即可
下面 numpy 复算。
# ---- §7.1 验证:numpy 复算 Dijkstra ----
import heapq
edges = [('A', 'B', 4), ('A', 'C', 2), ('B', 'C', 1), ('B', 'D', 5),
('C', 'D', 8), ('C', 'E', 10), ('D', 'E', 2)]
adj = {}
for u, v, w in edges:
adj.setdefault(u, []).append((v, w))
adj.setdefault(v, []).append((u, w))
dist = {n: float('inf') for n in 'ABCDE'}
dist['A'] = 0
pq = [(0, 'A')]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in adj[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
print({k: round(v) for k, v in dist.items()})
assert dist['B'] == 3 and dist['C'] == 2 and dist['D'] == 8 and dist['E'] == 10
print('\n✓ 与手算一致')
# ============== 743 网络延迟时间(Dijkstra 堆优化) ==============
# 【题目目标】信号从节点 k 出发沿边传播(每条边有传输延时 w),求传到全部 n 个
# 节点所需的最短时间——即到最远节点的最短距离;有节点不可达返回 -1
# 【算法思路】Dijkstra(贪心 + 小顶堆):dist 数组初始为 inf、dist[k]=0;优先队列
# 每次取出当前距离最小的节点 (d,u),若 d>dist[u] 说明是过期记录直接跳过,
# 否则松弛它的每条出边:新距离 nd=d+w 更短则更新 dist 并压入堆
# 【变量含义】times:(u,v,w) 边;n:节点数;k:起点;adj:邻接表(1-based 多开
# 一位);dist:最短距离数组;heap:小顶堆(距离, 节点);(d,u):堆顶;
# (v,w):出边;nd:经 u 到 v 的新距离;ans:最远距离
# 【循环不变量】堆中弹出的节点其 dist 已确定(非负权下不可能再被其他路径改进);
# dist[u] 只减不增
# 【递归终止】堆空即结束(所有可达节点的最短距离已确定)
# 【关键边界】下标从 1 开始,数组与邻接表多开一位;过期记录必须 continue 否则
# 可能重复松弛;最终 ans 仍为 inf 表示存在不可达节点返回 -1;有负权
# 边时该算法不适用(会错)
# 【复杂度】O((V+E) log V) 时间、O(V+E) 空间
# 743. 网络延迟时间(Dijkstra 最短路径):优先队列每次取「当前距离最近」的节点松弛邻居
import heapq
# 743. 网络延迟时间:求信号从节点 k 传到所有节点所需的最短时间(即最远距离),不可达返回 -1
# 思路:Dijkstra 堆优化——优先队列每次取当前距离最小的节点,松弛其所有出边
def network_delay_time(times, n, k):
# 返回从 k 到所有节点的最短时间最大值;不可达返回 -1
adj = [[] for _ in range(n + 1)] # 邻接表(下标从 1 开始,多开一位)
for u, v, w in times: # 建图:u → v 权重 w
adj[u].append((v, w)) # 记录出边
dist = [float('inf')] * (n + 1) # 最短距离数组,初始全部无穷大
dist[k] = 0 # 起点 k 到自身距离为 0
heap = [(0, k)] # 优先队列(小顶堆):(距离, 节点)
while heap: # 堆非空继续松弛
d, u = heapq.heappop(heap) # 取出当前距离最小的节点
if d > dist[u]:
continue # 过期记录,跳过
for v, w in adj[u]: # 遍历 u 的每条出边
nd = d + w # 经 u 到 v 的新距离
if nd < dist[v]: # 新距离更短才更新
dist[v] = nd # 更新最短距离
heapq.heappush(heap, (nd, v)) # 新候选入堆
ans = max(dist[1:]) # 所有节点中最远的距离
return -1 if ans == float('inf') else ans # 有节点不可达则 -1
print('test1:', network_delay_time([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2)) # 2
print('test2:', network_delay_time([[1, 2, 1]], 2, 1)) # 1
print('test3:', network_delay_time([[1, 2, 1]], 2, 2)) # -1(节点1不可达)
test1: 2 test2: 1 test3: -1
§8 前缀树 Trie(LeetCode 208)¶
题目:实现 insert / search / startsWith。
结构:树节点存「子节点字典 + 是否结尾」:
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False
复杂度:$O(L)$(L 为单词长度)时间/空间每次操作。
优势:前缀查询 $O(L)$ 而非遍历全部单词;自动机/词频统计/AC 自动机的基础。
# ============== 208 实现 Trie(前缀树) ==============
# 【题目目标】实现前缀树数据结构,支持三个操作:insert 插入单词、search 查询
# 完整单词是否存在、startsWith 查询是否存在以某前缀开头的单词
# 【算法思路】树节点存「子节点字典 + 是否结尾标记」:insert 沿每个字符向下走,
# 路径不存在就新建节点,最后把末尾节点标记为 is_end=True;_find 沿
# 前缀逐字符查找,路径中断返回 None,否则返回末尾节点;search 要求
# _find 非空且 is_end 为 True;startsWith 只要求 _find 非空
# 【变量含义】node:当前游走的节点;children:字符→子节点的字典;is_end:从根
# 到该节点的路径是否构成一个完整单词;prefix:待查询的前缀;word:单词
# 【循环不变量】从根到任一节点的路径唯一对应一个前缀串;is_end 精确区分「完整
# 单词」与「只是前缀」(如 app 是 apple 的前缀但不是完整单词)
# 【递归终止】无递归;循环逐字符走到字符串末尾即结束
# 【关键边界】search 与 startsWith 的唯一区别在于是否检查 is_end;根节点不存
# 字符;children 用 dict 实现稀疏存储,天然支持任意字符集
# 【复杂度】每次操作 O(L)(L 为单词/前缀长度);空间 O(ΣL)(所有插入串的总长度)
# 208. 实现 Trie 前缀树:支持插入、查询完整单词、查询前缀
# 结构:每个节点存一个子节点字典 + 是否为一个单词的结尾标记
class TrieNode:
def __init__(self):
self.children = {} # 子节点字典:字符 → 下一个节点
self.is_end = False # 从根到该节点的路径是否构成一个完整单词
class Trie:
def __init__(self):
self.root = TrieNode() # 根节点不存字符
def insert(self, word):
node = self.root # 从根开始
for ch in word: # 逐字符往下走
if ch not in node.children: # 该字符路径不存在
node.children[ch] = TrieNode() # 新建节点
node = node.children[ch] # 移动到子节点
node.is_end = True # 标记单词结尾
def _find(self, prefix):
node = self.root # 从根开始
for ch in prefix: # 逐字符查找
if ch not in node.children: # 路径中断
return None # 前缀不存在
node = node.children[ch] # 继续往下
return node # 返回前缀末尾节点
def search(self, word):
node = self._find(word) # 先找到路径末尾
return node is not None and node.is_end # 必须恰好是单词结尾才算存在
def starts_with(self, prefix):
return self._find(prefix) is not None # 只要求路径存在,不要求是完整单词
# 测试:插入 apple 后验证 search 与 starts_with 的区别
trie = Trie()
trie.insert('apple')
print('search(apple):', trie.search('apple')) # True
print('search(app):', trie.search('app')) # False(未标记结尾)
print('starts_with(app):', trie.starts_with('app')) # True
trie.insert('app')
print('search(app) 后:', trie.search('app')) # True
print('search(bad):', trie.search('bad')) # False
search(apple): True search(app): False starts_with(app): True search(app) 后: True search(bad): False
§9 复杂度总表(背熟)¶
| 模板 | 时间 | 空间 | 适用 |
|---|---|---|---|
| BFS/DFS | $O(V+E)$ | $O(V)$ | 遍历、连通块、无权最短路 |
| 网格 DFS/BFS | $O(RC)$ | $O(RC)$ | 岛屿类、感染类 |
| Kahn 拓扑 | $O(V+E)$ | $O(V)$ | 判环、排序 |
| 并查集 | $O(\alpha(n))$ | $O(n)$ | 动态连通 |
| Dijkstra(堆) | $O((V+E)\log V)$ | $O(V+E)$ | 非负权最短路 |
| Trie | $O(L)$/操作 | $O(\sum L)$ | 前缀查询 |
选型速查(面试 30 秒)¶
- 无权最短路 → BFS;有权非负 → Dijkstra;有负权 → Bellman-Ford
- 判环:有向 → 拓扑/Kahn;无向 → 并查集/DFS
- 连通块 → DFS/BFS/并查集;单词前缀 → Trie
§10 常见 bug 与边界(面试踩坑区)¶
- visited 缺失:无向图 DFS 不标记 → 死循环(或指数爆炸)
- BFS 入队即标记:先标记再入队;否则同一节点可能入队多次
- Dijkstra 忘了跳过过期记录:堆里有旧距离记录,
d > dist[u]必须 continue - 拓扑:入度数组的边方向:
prerequisites是[a, b]表示 b→a 还是 a→b,先确认 - 网格越界:四方向前先
0 <= ni < R and 0 <= nj < C - 并查集路径压缩写错:
parent[x] = parent[parent[x]]或递归版都行,但别写漏 - Trie 的 is_end:search 判结尾、starts_with 不判——混了必错
- 图不连通:Dijkstra 结果里可能有
inf,记得处理(返回 -1)
§12 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
L1 必会(10 题)¶
- 1. 岛屿数量(LeetCode 200)
- 2. 腐烂的橘子(994)
- 3. 课程表(207)
- 4. 课程表 II(210,输出拓扑序)
- 5. 实现 Trie(前缀树)(208)
- 6. 省份数量(547)
- 7. 二叉树的层序遍历(102,BFS 热身)
- 8. 图像渲染(733,连通块)
- 9. 被围绕的区域(130)
- 10. 钥匙和房间(841,DFS 可达性)
L2 进阶(10 题)¶
- 11. 网络延迟时间(743,Dijkstra)
- 12. 冗余连接(684,并查集)
- 13. 单词搜索(79,网格 DFS)
- 14. 单词接龙(127,BFS 最短转换)
- 15. 判断二分图(785)
- 16. 找到小镇的法官(997,出度入度)
- 17. 太平洋大西洋水流问题(417,反向 DFS)
- 18. 矩阵中的最长递增路径(329,DFS+记忆化)
- 19. 重新安排行程(332,欧拉路径)
- 20. 连坐/可能的二分法(886,染色)
L3 挑战(5 题)¶
- 21. 最小生成树(1584,Prim/Kruskal 模板)
- 22. 网络延迟时间的全源版(Floyd)
- 23. 马踏棋盘/骑士概率(688,DP+BFS)
- 24. 课程表 III(630,贪心+堆)
- 25. 最小高度树(310,拓扑剥皮)
自测要点¶
- 5 分钟内盲写:BFS 模板 + Kahn 拓扑 + 并查集模板
- 讲清 BFS 最短路径原理与 Dijkstra 贪心正确性
- 网格题统一用「sink 原地标记」或 visited 数组,能说清二者取舍