算法-图算法
这篇笔记讲什么
图算法是「把现实问题翻译成点和边」之后的一整套工具箱。本篇按问题类型组织:遍历(BFS/DFS)→ 最短路(Dijkstra / Bellman-Ford / Floyd / A\*)→ 连通性(并查集 / Tarjan 强连通分量)→ 生成树(Kruskal / Prim)→ 依赖顺序(拓扑排序)→ 网络流与匹配(Edmonds-Karp / 匈牙利算法),并在最后给出选型速查表。
读完你应该能:拿到一个图论问题先判断它属于哪一类、选对算法、说清每个算法的前提与失效条件(尤其是 Dijkstra 为什么怕负权边),并手写出主要算法的 Python 实现。
一、是什么:图与图算法的分类
图(Graph) 由顶点集 和边集 组成。边可以带方向(有向图)或不带(无向图),可以带权(weight)或不带。
图算法的四大类:
| 类别 | 要回答的问题 | 代表算法 |
|---|---|---|
| 遍历与连通性 | 能不能到?有几块?有没有环?是不是二分图? | BFS、DFS、并查集、Tarjan |
| 最短路径 | 从 到 的最小代价是多少? | Dijkstra、Bellman-Ford、Floyd-Warshall、A\* |
| 生成树 | 用最小总代价把所有点连起来 | Kruskal、Prim |
| 流与匹配 | 最大能同时满足多少约束? | Ford-Fulkerson、Edmonds-Karp、匈牙利算法 |
二、为什么需要它 / 适用条件
图的表示方式决定了算法的复杂度,这是最容易忽略的前置选择:
| 表示 | 空间 | 判断 | 遍历 的邻居 | 适用 |
|---|---|---|---|---|
邻接矩阵 adj[u][v] | 稠密图、、需要快速查边 | |||
邻接表 graph[u] = [...] | 稀疏图、绝大多数场景的默认选择 | |||
边列表 edges = [(u,v,w)] | Kruskal、Bellman-Ford |
读题先看数据范围,再选算法
- :随便写,Floyd 也扛得住。
- 、 接近 (稠密):朴素 Dijkstra 或 Prim 。
- :优先队列 Dijkstra 、Kruskal 。
- 边权可能为负:不能用 Dijkstra,改用 Bellman-Ford / SPFA / Floyd。
- 且要「访问所有点」:状压 DP(见 算法-动态规划与贪心 的 TSP)。
图论建模四步法
图论题的难点 90% 在建模,而不是算法本身。拿到题先回答四个问题:
- 点是什么?(城市、状态、任务、格子、人)
- 边是什么?(能直接到达、依赖关系、冲突关系、可以配对)
- 边权是什么?(距离、时间、代价、容量;没有权就是「经过一条边算一步」)
- 求什么?(可达性 → 遍历;最小代价 → 最短路;最小连通代价 → MST;最大同时满足量 → 最大流/匹配;顺序 → 拓扑排序)
常见建模套路:
| 原问题 | 建图方式 |
|---|---|
| 网格中从起点到终点最少步数 | 每个格子是点,上下左右相邻是边,BFS |
| 单词接龙(每次改一个字母) | 单词是点,只差一个字母的两个单词连边,BFS |
| 课程先修关系能否完成 | 课程是点,先修关系是边,拓扑排序 / 判环 |
| 判断两个人是否是朋友的朋友 | 人是点,朋友关系是边,并查集 |
| 最少需要几门课并行 | 课程是点,依赖是边,拓扑排序 + 分层计数 |
| 状态转移的最少操作次数 | 状态是点,一次操作是边,BFS(隐式图) |
| 任务分配 / 课程与老师配对 | 二分图,左边任务右边资源,匈牙利算法 |
「状态是点」是图论建模最高频的一招
当题目问「从初始状态到目标状态最少需要多少步操作」时,把每个状态当成一个点、一次操作当成一条边,问题立刻变成无权图最短路,直接 BFS。例如「打开转盘锁」「单词接龙」「倒水问题」都属此类。图的规模可能极大(状态数爆炸),此时必须靠剪枝或双向 BFS。
三、核心内容:BFS / DFS 及其典型应用
广度优先搜索(Breadth-First Search, BFS) 按「距离起点的层数」逐层扩展,用队列实现;深度优先搜索(Depth-First Search, DFS) 沿一条路走到底再回退,用栈(递归)实现。
| 维度 | BFS | DFS |
|---|---|---|
| 数据结构 | 队列(FIFO) | 栈 / 递归 |
| 访问顺序 | 按层,距离非递减 | 沿分支深入 |
| 无权图最短路 | ✅ 首次到达即最短 | ❌ 不保证 |
| 空间 | ,最坏 | ,最坏 |
| 天然用途 | 最短路、层序、扩散 | 连通块、环检测、拓扑序、回溯 |
| 实现复杂度 | 稍繁(需队列) | 简单(递归) |
3.1 连通块计数
from collections import deque
def count_components(n, edges):
"""无向图连通块计数(DFS 洪水填充)。O(V + E)"""
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
seen = [False] * n
count = 0
def dfs(start):
stack = [start]
seen[start] = True
while stack: # 显式栈,避免递归深度限制
u = stack.pop()
for v in graph[u]:
if not seen[v]:
seen[v] = True # 入栈时立刻标记,防止重复入栈
stack.append(v)
for i in range(n):
if not seen[i]: # 每发现一个未访问点就是一个新连通块
count += 1
dfs(i)
return count
网格版(LeetCode 200 岛屿数量):把二维网格隐式地看成图,每格与上下左右相邻。连通块计数就是「数有几块陆地」。
def num_islands(grid):
"""LeetCode 200 岛屿数量:网格 DFS 洪水填充。O(mn)"""
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
count = 0
def sink(sr, sc):
"""把与 (sr, sc) 相连的陆地全部「沉掉」,避免重复计数"""
stack = [(sr, sc)]
grid[sr][sc] = "0"
while stack:
r, c = stack.pop()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == "1":
grid[nr][nc] = "0" # 标记已访问,直接改原数组省空间
stack.append((nr, nc))
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
count += 1
sink(i, j)
return count
3.2 无权图最短路径
def bfs_dist(graph, start):
"""无权图单源最短路:BFS 首次访问即最短。返回 {节点: 距离}"""
dist = {start: 0}
q = deque([start])
while q:
u = q.popleft()
for v in graph[u]:
if v not in dist: # 首次到达 = 最短距离已确定
dist[v] = dist[u] + 1
q.append(v)
return dist
为什么 BFS 首次到达就是最短
BFS 出队顺序保证「距离 的节点一定在距离 的节点之前全部出队」。设首次访问 时距离为 ,若存在更短的路径 ,那条路径上的前驱会在更早的层被处理并把 入队,矛盾。这个论证只在边权相等(都为 1)时成立——一旦边权不同,"层" 的概念就不存在了,必须用 Dijkstra。
3.3 环检测
无向图:DFS 时若遇到一个「已访问且不是自己父亲」的邻居,就存在环。有向图不能用这一招(两条不同路径汇合不算环),要用三色标记法。
def has_cycle_undirected(n, edges):
"""无向图环检测:DFS + 记录父亲节点。O(V + E)"""
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
seen = [False] * n
def dfs(u, parent):
seen[u] = True
for v in graph[u]:
if not seen[v]:
if dfs(v, u):
return True
elif v != parent: # 已访问且不是父亲 → 找到了环
return True
return False
return any(not seen[i] and dfs(i, -1) for i in range(n))
def has_cycle_directed(n, edges):
"""有向图环检测:三色标记 DFS。
白色 = 未访问,灰色 = 在当前递归栈上,黑色 = 全部后继已处理完"""
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n
def dfs(u):
color[u] = GRAY
for v in graph[u]:
if color[v] == GRAY: # 指向递归栈上的节点 → 有向环
return True
if color[v] == WHITE and dfs(v):
return True
color[u] = BLACK
return False
return any(color[i] == WHITE and dfs(i) for i in range(n))
无向图环检测的另一个办法:并查集
依次处理每条边 :若
find(u) == find(v),说明 、 早已连通,这条边就构成一个环;否则union(u, v)。这个写法比 DFS 更短,且天然支持动态加边(LeetCode 684 冗余连接就是这一招)。
3.4 二分图判定
二分图(Bipartite Graph):顶点可分成两个集合,使每条边的两个端点分属不同集合。等价于「图中不存在长度为奇数的环」。
def is_bipartite(graph):
"""二分图判定:BFS 二染色。O(V + E)"""
color = {}
for s in range(len(graph)):
if s in color:
continue
color[s] = 0 # 未染色节点任取一色
q = deque([s])
while q:
u = q.popleft()
for v in graph[u]:
if v not in color:
color[v] = color[u] ^ 1 # 染成相反色
q.append(v)
elif color[v] == color[u]:
return False # 相邻同色 → 出现奇环
return True
四、最短路算法
4.1 Dijkstra:单源、非负权
核心思想:贪心。维护一个「已确定最短距离」的集合 ,每轮从 中取出 最小的点 加入 ,并用 松弛它的邻居。正确性依赖边权非负:只有这样,「当前 最小的未确定点,其距离不可能再被后续路径改小」。
(1)朴素实现(邻接矩阵 + 线性找最小):。
def dijkstra_dense(n, adj, src):
"""朴素 Dijkstra(邻接矩阵)。adj[u][v] = 权或 INF。O(V^2),适合稠密图"""
INF = float("inf")
dist = [INF] * n
used = [False] * n
dist[src] = 0
for _ in range(n):
u = -1
for i in range(n): # 线性扫描找未确定的最小 dist
if not used[i] and (u == -1 or dist[i] < dist[u]):
u = i
if u == -1 or dist[u] == INF:
break # 剩余点都不可达,提前结束
used[u] = True # u 的最短距离就此确定
for v in range(n):
if adj[u][v] < INF and dist[u] + adj[u][v] < dist[v]:
dist[v] = dist[u] + adj[u][v]
return dist
(2)优先队列实现(堆优化):。
import heapq
def dijkstra(n, graph, src):
"""堆优化 Dijkstra。graph[u] = [(v, w), ...]。O((V + E) log V)"""
INF = float("inf")
dist = [INF] * n
dist[src] = 0
pq = [(0, src)] # (当前距离, 节点)
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue # 过期条目(懒惰删除),跳过
for v, w in graph[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v)) # 同一节点允许多次入队
return dist
分步推演:图有顶点 ,边 权 1, 权 4, 权 1, 权 1。求从 0 出发的最短路。
| 轮次 | 出堆 | dist | 说明 |
|---|---|---|---|
| 初始 | — | [0, ∞, ∞, ∞] | 起点入堆 |
| 1 | [0, 1, 4, ∞] | 松弛 、 | |
| 2 | [0, 1, 2, ∞] | 走 比 更短,更新为 2 | |
| 3 | [0, 1, 2, 3] | 松弛 | |
| 4 | [0, 1, 2, 3] | 无出边 |
Dijkstra 为什么不能处理负权边
Dijkstra 的正确性建立在一条贪心断言上:「当前 最小的未确定点,其距离已经不可能再变小」。这条断言要求「后续任何路径的代价都不会减少」——即边权非负。一旦有负权边,绕远路反而可能更便宜,断言失效。
反例:三个顶点 ,边 权 , 权 , 权 。
- Dijkstra 的执行:从 0 出发,、;堆中最小的是 ,于是把顶点 1 标记为已确定(此后不再更新它)。接着处理顶点 2,发现 ,但顶点 1 已被「确定」,更新被跳过。
- 结果:Dijkstra 返回 ,而真实最短距离是 。
修法:改用 Bellman-Ford / SPFA(能处理负权,还能判负环);或先用 Johnson 算法做势能重标定(reweighting)把所有边权变成非负,再跑 Dijkstra。
变体:边权只有 0 和 1 时用 0-1 BFS
若边权只有 0 与 1,把队列换成双端队列(deque):权为 0 的边把邻居压入队首、权为 1 的压入队尾,即可在 内求出最短路,比堆优化的 更快。
4.2 Bellman-Ford:允许负权,且能判负环
核心思想:不再贪心,而是暴力地反复松弛所有边。松弛 轮的理由是:
从 到任意点的最短路径一定是简单路径(若含环,去掉环只会更短或不变——负环除外),所以最多包含 条边。第 轮松弛后,所有「最多用 条边」的最短路都已确定。因此 轮后,所有最短路都已被确定。
判负环:若第 轮还能松弛成功,说明存在一条含 条边却更短的路径,即路径中必有环且该环权为负——存在从源点可达的负环(此时最短距离无定义,为 )。
def bellman_ford(n, edges, src):
"""Bellman-Ford:返回 (dist, 是否存在可达负环)。edges = [(u, v, w)]。O(VE)"""
INF = float("inf")
dist = [INF] * n
dist[src] = 0
for _ in range(n - 1): # 最多松弛 n-1 轮
updated = False
for u, v, w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
updated = True
if not updated: # 本轮无任何更新 → 已收敛
break
# 第 n 轮仍能松弛 ⇒ 存在从 src 可达的负环
for u, v, w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
return dist, True
return dist, False
SPFA(Shortest Path Faster Algorithm) 是 Bellman-Ford 的队列优化版:只有「距离被更新过的点」才有必要去松弛它的邻居,因此用队列维护待松弛的点。
def spfa(n, graph, src):
"""SPFA:队列优化的 Bellman-Ford。平均 O(E),最坏 O(VE)。
graph[u] = [(v, w), ...]。返回 dist;检测到负环返回 None"""
INF = float("inf")
dist = [INF] * n
in_queue = [False] * n
enter_count = [0] * n # 每个点的入队次数,用于判负环
dist[src] = 0
q = deque([src])
in_queue[src] = True
enter_count[src] = 1
while q:
u = q.popleft()
in_queue[u] = False
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
if not in_queue[v]:
q.append(v)
in_queue[v] = True
enter_count[v] += 1
if enter_count[v] >= n: # 入队 >= n 次 ⇒ 存在负环
return None
return dist
SPFA 已经「死」了——什么时候不能用它
SPFA 的最坏复杂度是 ,且这一上界能被构造出来。竞赛中专门有针对 SPFA 的「网格菊花图」数据,可以把 实际跑满,导致超时(这就是「SPFA 已死」说法的由来)。实践建议:
- 边权非负 → 一律用 Dijkstra,正确且稳定 ;
- 需要判负环 → 用朴素 Bellman-Ford(复杂度确定,)或队列 + 计数判环的 SPFA;
- 确实需要 SPFA → 加上 SLF / LLL 优化,并做好被卡的心理准备。
另外,负环判定要注意「可达性」:只有从源点可达的负环才会让
dist无意义。若图不连通,需要对每个未访问的连通块单独跑一次,或加一个虚拟超级源点连向所有点。
4.3 Floyd-Warshall:全源最短路
核心思想:区间/阶段 DP。状态 dp[k][i][j] = 「只允许经过前 个顶点作为中转时, 到 的最短距离」。
空间优化:第 轮只依赖第 轮,且 dp[i][k]、dp[k][j] 在第 轮中不会被改小(无负环时 不会变),所以可以原地滚动,把三维压成二维,空间从 降到 。
def floyd(n, adj):
"""Floyd-Warshall 全源最短路。adj 是 n x n 邻接矩阵,无边处为 INF。O(V^3)"""
INF = float("inf")
dist = [row[:] for row in adj] # 原地滚动:直接复用二维数组
for i in range(n):
dist[i][i] = 0 # 自己到自己是 0
for k in range(n): # ★ 中转点 k 必须在最外层
dk = dist[k]
for i in range(n):
dik = dist[i][k]
if dik == INF: # 剪枝:i 到 k 不可达,松弛无意义
continue
di = dist[i]
for j in range(n):
nd = dik + dk[j]
if nd < di[j]:
di[j] = nd
return dist
三重循环的顺序为什么不能颠倒
正确的顺序是 (中转点)→ (起点)→ (终点), 必须在最外层。原因是 DP 的阶段是中转点集合的大小:第 轮结束时,我们只保证「允许用前 个点中转」的答案是正确。
若把 放到最外层,算法就变成「对每个起点 ,枚举中转点 和终点 」——但此时 可能还没有利用 之后的中转点更新过,甚至可能存在「先用 更新了 ,但 之后再被 改小」的情况,导致 用的是过期的 。结果会偏大(漏掉更优路径),而且不会报错——这正是它成为经典陷阱的原因。
记忆法:「中转点是阶段,起点终点是状态」。阶段永远在最外层。
Floyd 的三个常见用途:
| 用途 | 做法 |
|---|---|
| 全源最短路 | 直接跑 |
| 传递闭包(可达性) | 把 min/+ 换成 or/and,布尔矩阵运算 |
| 最小环(无向图) | 在 循环内、更新 dist 之前检查 dist[i][j] + w(i,k) + w(k,j) |
4.4 A\* 启发式搜索
A\* 是「Dijkstra + 目标导向的启发式」。它把优先队列的排序键从 (起点到 的真实代价)换成
其中 是「 到目标代价的估计」,称为估价函数(heuristic)。
| 概念 | 定义 | 作用 |
|---|---|---|
| 可采纳性(admissible) | 真实的 最短距离(绝不高估) | 保证 A\* 找到的是最优解 |
| 一致性 / 单调性(consistent) | 且 | 保证每个点只被扩展一次,效率更高 |
| 完全不估计 | A\* 退化为 Dijkstra | |
| 高估 | 不可采纳 | 变成贪心最优搜索,可能返回次优解 |
def astar(n, graph, start, goal, heuristic):
"""A* 搜索。graph[u] = [(v, w), ...],heuristic(u) 是到 goal 的估计代价(必须可采纳)。
返回从 start 到 goal 的最短距离;不可达返回 inf"""
INF = float("inf")
g = [INF] * n
g[start] = 0
pq = [(heuristic(start), start)] # 按 f = g + h 排序
closed = [False] * n
while pq:
_, u = heapq.heappop(pq)
if u == goal:
return g[u] # 首次弹出 goal 即为最优(依赖可采纳性)
if closed[u]:
continue # 同一节点可能有多个过期条目
closed[u] = True
for v, w in graph[u]:
ng = g[u] + w
if ng < g[v]:
g[v] = ng
heapq.heappush(pq, (ng + heuristic(v), v))
return INF
def manhattan(a, b):
"""网格地图上常用的可采纳启发式:曼哈顿距离(只允许四方向移动时)"""
return abs(a[0] - b[0]) + abs(a[1] - b[1])
分步推演(直观对比):在网格地图上从左上角走到右下角,障碍物很少。
| 算法 | 扩展的节点形态 | 扩展数量 |
|---|---|---|
| BFS | 以起点为中心的同心方环 | 全部可达格 |
| Dijkstra | 以起点为中心的同心圆(等代价扩散) | 全部可达格 |
| A\*(曼哈顿启发式) | 一条朝目标方向拉长的椭圆带 | 通常远少于前两者 |
**A\* 什么时候会退化甚至出错**
- 高估(例如在有障碍的网格里仍用曼哈顿距离,但允许八方向移动时曼哈顿距离会高估)→ 失去最优性保证。
- 恒为 0 → 退化成 Dijkstra,只是白写了启发式。
- 地图有大量「陷阱」结构(目标被墙围住只剩一个小口)→ 启发式会把搜索拉向墙,扩展量可能超过 Dijkstra。这是 A\* 在实际寻路中需要配合「跳点搜索(JPS)」「分层寻路」的原因。
五、并查集(Disjoint Set Union, DSU)
是什么:维护一组不相交集合的数据结构,支持两个操作——find(x) 查询 属于哪个集合,union(a, b) 合并两个集合。
为什么需要它:处理「动态连通性」问题。BFS/DFS 只能在静态图上求连通块,一旦边是逐条加入的,重复跑 BFS 就太慢;并查集能在几乎 的时间内维护连通性。
两个关键优化:
| 优化 | 做法 | 单独使用的复杂度 |
|---|---|---|
| 路径压缩(Path Compression) | find 时把路径上所有点直接挂到根上 | 均摊 |
| 按秩合并(Union by Rank) | 把矮树接到高树上,避免退化成链 | 均摊 |
| 两者结合 | — | 均摊 |
是什么量级
是反阿克曼函数(inverse Ackermann function),增长极其缓慢:。也就是说,对任何能写进宇宙的 ,单次操作的均摊代价都不超过 5 次基本操作——可以当作 使用。这个结论由 Tarjan 与 van Leeuwen 证明(路径压缩 + 按秩合并的均摊界为 );注意它是均摊而非最坏,单次
find最坏仍可能走 步。
class DSU:
"""并查集:路径压缩 + 按秩合并,单次操作均摊 O(alpha(n)) ≈ O(1)"""
def __init__(self, n):
self.parent = list(range(n)) # 初始时每个点自成一个集合
self.rank = [0] * n # 秩 = 树高的上界
self.count = n # 当前连通块个数
def find(self, x):
root = x
while self.parent[root] != root: # 第一步:找到根
root = self.parent[root]
while self.parent[x] != root: # 第二步:路径压缩(迭代实现,无递归风险)
self.parent[x], x = root, self.parent[x]
return root
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # 已在同一集合(可用于判环)
if self.rank[ra] < self.rank[rb]: # 矮树接高树,控制树高
ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1 # 两棵同高树合并,高度 +1
self.count -= 1
return True
def connected(self, a, b):
return self.find(a) == self.find(b)
朋友圈问题(LeetCode 547 省份数量):把每个人看成点,互为朋友的两个点合并,最后连通块个数就是省份数。
def find_circle_num(is_connected):
"""LeetCode 547 省份数量:并查集统计连通块。O(n^2 * alpha(n))"""
n = len(is_connected)
dsu = DSU(n)
for i in range(n):
for j in range(i + 1, n):
if is_connected[i][j] == 1:
dsu.union(i, j)
return dsu.count
并查集判环(无向图):依次处理每条边 ;若 find(u) == find(v),说明这条边连接的两个点已经连通,加入它必然成环。
def find_redundant_connection(edges):
"""LeetCode 684 冗余连接:找出使图成环的那条边。O(n * alpha(n))"""
n = len(edges)
dsu = DSU(n + 1) # 题目顶点编号是 1..n
for u, v in edges:
if not dsu.union(u, v): # 合并失败 ⇒ u、v 本就连通 ⇒ 这条边多余
return [u, v]
return []
六、最小生成树(Minimum Spanning Tree, MST)
是什么:在连通无向带权图中选出一棵包含全部 个顶点、恰好 条边的树,使边权总和最小。
理论基础——切分定理(Cut Property):把顶点集任意划分成 与 两部分(称为一个切分/cut),横跨该切分的权值最小的边一定属于某棵最小生成树。
切分定理如何同时支撑 Kruskal 与 Prim
- Kruskal 每次取的边,都是「当前连通块集合」与「其余点」这个切分中最小的边(因为边已按权排序)→ 由切分定理,它必在某棵 MST 中。
- Prim 每次取的边,都是「已选顶点集 」与「」这个切分中最小的边 → 同样由切分定理保证正确。
两者的差别只是切分的构造方式不同:Kruskal 是全局从小到大扫边(切分由并查集隐式决定),Prim 是从一个点开始向外生长(切分是显式的已选集合)。
6.1 Kruskal:按边贪心 + 并查集
1. 把所有边按权值升序排序
2. 依次考虑每条边 (u, v, w):若 u 与 v 尚未连通(并查集判环),就加入这条边
3. 直到选满 V-1 条边
def kruskal(n, edges):
"""Kruskal 最小生成树。edges = [(w, u, v), ...]。
返回 (总权重, 选中的边列表);图不连通时选不满 n-1 条边。O(E log E)"""
dsu = DSU(n)
total = 0
chosen = []
for w, u, v in sorted(edges): # 按边权升序(元组排序先比 w)
if dsu.union(u, v): # 不构成环才加入
total += w
chosen.append((u, v, w))
if len(chosen) == n - 1: # 已够 n-1 条边 ⇒ MST 完成
break
return total, chosen
6.2 Prim:按点贪心 + 优先队列
1. 任选一个点作为起点加入集合 S
2. 用优先队列维护「从 S 出发能到达 S 外各点的最小边权」
3. 每轮取出最小的一条跨越边,把对应点加入 S
4. 重复 V-1 次
def prim(n, graph, start=0):
"""Prim 最小生成树(堆优化)。graph[u] = [(v, w), ...]。O(E log E)"""
used = [False] * n
total = 0
pq = [(0, start)] # (边权, 顶点)
while pq:
w, u = heapq.heappop(pq)
if used[u]:
continue # 该点已通过更小的边加入过
used[u] = True
total += w # 起点那次的 w 是 0,不影响结果
for v, nw in graph[u]:
if not used[v]:
heapq.heappush(pq, (nw, v))
return total
6.3 稠密图与稀疏图选型
| 维度 | Kruskal | Prim(堆优化) | Prim(朴素邻接矩阵) |
|---|---|---|---|
| 复杂度 | |||
| 适合 | 稀疏图() | 稀疏图,略快于 Kruskal | 稠密图() |
| 依赖结构 | 并查集 | 优先队列 | 邻接矩阵 |
| 能否处理不连通图 | 能,直接得到最小生成森林 | 需对每个连通块分别跑 | 同左 |
| 特殊优势 | 天然支持「边已排序」或「动态加边」的场景 | 不需要预先知道所有边(可流式读入) | 常数小, 时最实用 |
怎么选
一句话:边少用 Kruskal,点少边多用朴素 Prim。 竞赛中 的稀疏图基本都用 Kruskal(写起来短、不用建图)。若边权是「点之间的欧氏距离」(完全图,,例如 LeetCode 1584 连接所有点的最小费用),则必须用 Prim,否则光是枚举 条边就已经是上限。
七、拓扑排序:处理依赖关系
是什么:对有向无环图(DAG)的顶点排出一个线性序列,使每条边 中 都排在 之前。存在拓扑序 ⟺ 图中无环。
Kahn 算法(BFS 版):反复取出入度为 0 的点,并「删除」它的出边(把邻居入度减 1)。
def topological_sort(n, edges):
"""Kahn 算法拓扑排序。edges = [(u, v)] 表示 u 必须先于 v。
返回拓扑序;若存在环则返回 None。O(V + E)"""
graph = [[] for _ in range(n)]
indeg = [0] * n
for u, v in edges:
graph[u].append(v)
indeg[v] += 1
q = deque(i for i in range(n) if indeg[i] == 0) # 入度 0 ⇒ 没有前置依赖
order = []
while q:
u = q.popleft()
order.append(u)
for v in graph[u]:
indeg[v] -= 1 # 相当于删掉边 u -> v
if indeg[v] == 0:
q.append(v)
return order if len(order) == n else None # 输出不全 ⇒ 有环
DFS 版:后序遍历的逆序就是拓扑序(因为一个点的所有后继都先于它完成)。
def topo_sort_dfs(n, graph):
"""DFS 拓扑排序:后序逆序。返回拓扑序,有环返回 None"""
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n
order = []
ok = True
def dfs(u):
nonlocal ok
color[u] = GRAY
for v in graph[u]:
if color[v] == GRAY: # 反向边 ⇒ 有环
ok = False
return
if color[v] == WHITE:
dfs(v)
color[u] = BLACK
order.append(u) # 后序位置:所有后继都已入列
for i in range(n):
if color[i] == WHITE:
dfs(i)
order.reverse() # 后序逆序 = 拓扑序
return order if ok else None
典型应用:
| 场景 | 建模方式 |
|---|---|
| 课程表 / 编译顺序 | 课程或模块是点,先修依赖是边;拓扑序给出可行学习/编译顺序,判环即「无法完成」 |
| 任务调度最短工期 | 拓扑序 + DP:dp[v] = max(dp[v], dp[u] + time[u]),答案取 max |
| 并行任务的最少轮数 | Kahn 算法按层计数(每轮取出当前所有入度 0 的点) |
| 字典序最小的拓扑序 | 把队列换成最小堆(LeetCode 1203 项目管理即此类) |
| 表达式求值 / 电子表格依赖 | 单元格是点,公式引用是边,拓扑序保证先算被依赖者 |
def min_semesters(n, relations):
"""并行修课的最少学期数:Kahn 按层推进。O(V + E)"""
graph = [[] for _ in range(n)]
indeg = [0] * n
for u, v in relations:
graph[u].append(v)
indeg[v] += 1
q = deque(i for i in range(n) if indeg[i] == 0)
semesters = 0
done = 0
while q:
semesters += 1 # 这一层可以并行修完
for _ in range(len(q)): # 只处理当前层的点
u = q.popleft()
done += 1
for v in graph[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return semesters if done == n else -1 # 有环 ⇒ 无法全部完成
八、强连通分量(Tarjan 算法)
是什么:有向图的强连通分量(Strongly Connected Component, SCC) 是极大的顶点集合,其中任意两点互相可达。
为什么需要它:SCC 是把有向图「压缩成 DAG」的工具。缩点之后,原图变成一个 DAG,于是拓扑排序、DAG 上 DP 等工具全都能用了。典型应用:2-SAT 判定、受欢迎的牛、缩点后求最长路。
Tarjan 算法的核心:一次 DFS,用两个数组维护信息:
index[u]: 被访问的时间戳(第几个被访问);low[u]:从 出发,能追溯到的最小时间戳(沿 DFS 树边与指向栈内节点的边)。
当 low[u] == index[u] 时, 就是当前 SCC 的「根」,从栈顶弹出到 为止的所有点构成一个 SCC。
import sys
def tarjan_scc(n, graph):
"""Tarjan 求有向图强连通分量。graph[u] = [v, ...](有向)。
返回分量列表,每个分量是顶点列表。O(V + E)"""
sys.setrecursionlimit(max(1000, 2 * n + 10))
index = [0] * n # 0 表示尚未访问
low = [0] * n
on_stack = [False] * n
stack = []
counter = 0
sccs = []
def dfs(u):
nonlocal counter
counter += 1
index[u] = low[u] = counter
stack.append(u)
on_stack[u] = True
for v in graph[u]:
if index[v] == 0: # 树边:递归后回传 low
dfs(v)
low[u] = min(low[u], low[v])
elif on_stack[v]: # 指向栈内节点 → 可追溯(横叉边不算)
low[u] = min(low[u], index[v])
if low[u] == index[u]: # u 是本 SCC 的根
comp = []
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u:
break
sccs.append(comp)
for i in range(n):
if index[i] == 0:
dfs(i)
return sccs
Tarjan 的两个易错点
1.
elif on_stack[v]这个条件不能省:若 已访问但不在栈上,说明 属于一个已经结算完的 SCC,它是「横叉边」的目标,不能用index[v]更新low[u],否则会把两个不相干的 SCC 错误地合并。这是 Tarjan 最常见的错误。2. 递归深度:链状图会让 DFS 深度达到 。 时必须调大递归上限,或改写成迭代版 Tarjan(实践上更多人改用 Kosaraju 的两遍 DFS,或直接写法相对好懂的迭代实现)。
另一种实现:Kosaraju 算法——做两遍 DFS:第一遍在原图上求「完成时间」的逆序,第二遍在反图上按该逆序 DFS,每次 DFS 得到的点集就是一个 SCC。它比 Tarjan 好懂,但需要同时存原图和反图。
九、网络流:最大流简介
是什么:在一个有向图中,每条边有容量 ,源点 无限出水、汇点 无限收水,求从 到 的最大流量。约束有两条:
- 容量限制:;
- 流量守恒:除 、 外,每个点流入量 = 流出量。
核心定理——最小割最大流定理(Max-Flow Min-Cut Theorem):
即最大流的值等于最小割的容量。它把「求最大流」与「求最小代价切断」这两个看似不同的问题统一起来,是网络流所有应用的基石。
Ford-Fulkerson 方法:只要残量网络中还存在 的路径(增广路),就沿它推流,并建立反向边允许「撤销」之前的决策。
反向边为什么必须存在
反向边是 Ford-Fulkerson 正确性的关键:它让算法能够「反悔」。若某次推流占用了本可以更优使用的边,反向边提供了一条把流量退回去的通道。没有反向边,贪心推流会卡在局部最优。 实现上,正向边与反向边成对存储(编号
e与e^1),推流时正向减、反向加。
| 算法 | 找增广路的方式 | 复杂度 | 备注 |
|---|---|---|---|
| Ford-Fulkerson(DFS) | 任意路径 | 容量为无理数时可能不终止 | |
| Edmonds-Karp | BFS 找最短增广路 | 与容量数值无关,稳定可靠 | |
| Dinic | BFS 分层 + DFS 阻塞流 | 实践中远快于此,竞赛首选 | |
| 最小费用最大流 | SPFA/Bellman-Ford 找最小代价增广路 | 边上再加「单位费用」 |
class MaxFlow:
"""Edmonds-Karp 最大流:每轮 BFS 找最短增广路。O(V * E^2)"""
def __init__(self, n):
self.n = n
self.graph = [[] for _ in range(n)] # 每个点存出边编号
self.to = [] # 第 e 条边指向的点
self.cap = [] # 第 e 条边的剩余容量
def add_edge(self, u, v, c):
"""加一条 u->v 容量 c 的边,同时建立容量 0 的反向边(成对出现)"""
self.graph[u].append(len(self.to))
self.to.append(v)
self.cap.append(c)
self.graph[v].append(len(self.to))
self.to.append(u)
self.cap.append(0) # 反向边初始容量为 0
def _bfs(self, s, t, prev_edge):
"""BFS 找一条增广路,prev_edge[v] = 到达 v 用的边编号"""
prev_edge[:] = [-1] * self.n
prev_edge[s] = -2 # 起点哨兵
q = deque([s])
while q:
u = q.popleft()
for eid in self.graph[u]:
v = self.to[eid]
if self.cap[eid] > 0 and prev_edge[v] == -1:
prev_edge[v] = eid
if v == t:
return True # 找到汇点即可停止
q.append(v)
return False
def max_flow(self, s, t):
flow = 0
prev_edge = [-1] * self.n
while self._bfs(s, t, prev_edge):
# 第一步:沿增广路求瓶颈容量
bottleneck = float("inf")
v = t
while v != s:
eid = prev_edge[v]
bottleneck = min(bottleneck, self.cap[eid])
v = self.to[eid ^ 1] # 反向边的终点就是原来的 u
# 第二步:更新残量网络(正向减、反向加)
v = t
while v != s:
eid = prev_edge[v]
self.cap[eid] -= bottleneck
self.cap[eid ^ 1] += bottleneck
v = self.to[eid ^ 1]
flow += bottleneck
return flow
def min_cut(self, s):
"""返回最小割的 S 侧点集:残量网络中从 s 可达的点"""
seen = [False] * self.n
seen[s] = True
q = deque([s])
while q:
u = q.popleft()
for eid in self.graph[u]:
v = self.to[eid]
if self.cap[eid] > 0 and not seen[v]:
seen[v] = True
q.append(v)
return seen
最大流的常见建模(都可以归约到最大流/最小割):
| 原问题 | 建模 |
|---|---|
| 二分图最大匹配 | 源点 → 左部(容量 1),左部 → 右部(容量 1),右部 → 汇点(容量 1) |
| 项目选择 / 最大权闭合子图 | 源点连正权点,负权点连汇点,答案 = 正权和 − 最小割 |
| 图像分割 / 二值标记 | 源汇分别代表两类,边权为「分错类的代价」 |
| 多重匹配 / 容量约束的分配 | 边的容量设为可服务的次数 |
十、二分图匹配:匈牙利算法
是什么:在二分图中选出尽可能多的边,使任意两条边不共享端点,这就是最大匹配(Maximum Matching)。
核心思想——增广路(Augmenting Path):从某个未匹配的左部点出发,交替走「非匹配边 → 匹配边 → 非匹配边 → …」,若终点是一个未匹配的右部点,则把这条路径上的匹配状态翻转,匹配数就 。若找不到这样的路径,则该点无法再增加匹配。
增广路定理
匹配 是最大匹配 当且仅当 不存在关于 的增广路(Berge 定理)。匈牙利算法的每一轮就是在为新的左部点寻找增广路——这本质上是一次 DFS,与最大流的「找增广路」是同一件事(二分图匹配是最大流的特例)。
def hungarian(n_left, n_right, adj):
"""匈牙利算法求二分图最大匹配。adj[u] = 左部点 u 能连的右部点列表。
返回 (最大匹配数, match_left, match_right)。O(V * E)"""
match_left = [-1] * n_left
match_right = [-1] * n_right
def try_kuhn(u, visited):
for v in adj[u]:
if visited[v]:
continue # 本轮已经尝试过 v,跳过避免死循环
visited[v] = True
# v 还没被匹配,或者 v 的原配能找到别的右部点 → 让位
if match_right[v] == -1 or try_kuhn(match_right[v], visited):
match_left[u] = v
match_right[v] = u
return True
return False
result = 0
for u in range(n_left):
if try_kuhn(u, [False] * n_right): # 每轮为 u 找一条增广路
result += 1
return result, match_left, match_right
分步推演:左部 、右部 ,边为 、、。
| 轮次 | 处理 | visited 与递归过程 | 结果 |
|---|---|---|---|
| 1 | 试 :未匹配 → 直接配 | 0-a | |
| 2 | 试 :已配给 0 → 递归让 0 换 | 0 改试 (未匹配,成功) |
最终匹配数 2:0-b、1-a。可以看到「让位」是匈牙利算法能找到最优匹配的关键——没有递归让位,第 2 轮就会失败。
匈牙利算法的复杂度与限制
复杂度是 ,其中每轮
try_kuhn是一次 DFS,最坏 。注意:- 递归深度可能达到 ,稠密二分图上要留意栈深度;
- 它求的是最大基数匹配(边数最多);若边带权求「最大权匹配」,需要 KM 算法或最小费用最大流;
- 二分图必须已确认是二分图(先用二染色验证),否则结果无意义。
十一、图算法选型速查表
| 问题 | 首选算法 | 时间复杂度 | 前提 / 注意 |
|---|---|---|---|
| 无权图单源最短路 | BFS | 边权必须相等 | |
| 边权只有 0/1 的最短路 | 0-1 BFS(双端队列) | 比堆优化 Dijkstra 更快 | |
| 非负权单源最短路 | Dijkstra(堆优化) | 边权不能为负 | |
| 非负权稠密图单源最短路 | Dijkstra(朴素) | 时优于堆优化 | |
| 含负权单源最短路 | Bellman-Ford | 可判负环;SPFA 最坏同阶 | |
| 含负权 + 必须判负环 | Bellman-Ford | 队列 + 入队计数亦可 | |
| 全源最短路 | Floyd-Warshall | 可含负权,不能有负环; | |
| 启发式/带地图的寻路 | A\* | 取决于 | 必须可采纳(不高估) |
| 动态连通性 / 判环 / 朋友圈 | 并查集 | 均摊 | 只能合并,不能删除 |
| 最小生成树(稀疏图) | Kruskal | 需要并查集 | |
| 最小生成树(稠密图) | Prim(朴素) | 需要邻接矩阵 | |
| 依赖顺序 / 判有向环 | 拓扑排序(Kahn) | 只适用于 DAG | |
| 有向图强连通分量 / 缩点 | Tarjan | 注意 on_stack 判断 | |
| 最大流 | Edmonds-Karp / Dinic | / | 需要建反向边 |
| 最小割 | 转最大流后取残量可达集 | 同最大流 | 最小割最大流定理 |
| 二分图最大匹配 | 匈牙利算法 | 图必须确实是二分图 | |
| 二分图最大权匹配 | KM 算法 / 最小费用最大流 | 匈牙利算法不处理边权 | |
| 状态空间上的最短路 | BFS / Dijkstra(隐式图) | 视状态数 | 状态可能爆炸,需剪枝 |
| 访问所有点的最短路() | 状压 DP(Held-Karp) | 见 [[算法-动态规划与贪心]] |
十二、注意事项与常见坑
什么时候不能用这些算法
- Dijkstra 不能用于负权边(哪怕只有一条负权边)。见 4.1 的反例。若必须用,请先用 Johnson 重标定把边权变非负。
- Dijkstra / Bellman-Ford 都不能处理负环:负环存在时「最短路」无定义(可以无限绕圈)。Bellman-Ford 的作用是检测它,而不是求解。
- BFS 只适用于无权图(或边权全相等)。边权不同必须换 Dijkstra。
- Floyd 不能用于 大的图: 时 ,直接超时。
- 并查集只能合并不能拆分:涉及「删边」的连通性问题(如动态图连通性、离线删边)需要倒序处理操作把删边变成加边,或使用 Link-Cut Tree 等高级结构。
- 拓扑排序只适用于 DAG:有环的图没有拓扑序,但「检测出有环」本身就是有用信息(例如循环依赖报错)。
- **A\* 的启发式绝不能高估**:否则返回的可能不是最短路径。
- 二分图匹配要求图确实是二分图:奇环存在时匈牙利算法的结果没有意义。
- 最大流的 Ford-Fulkerson(DFS 任意增广)在容量为无理数时可能不终止:实现时请用 BFS(Edmonds-Karp)或 Dinic。
其他高频坑
1. 无向图建边只加了一遍:邻接表里无向边必须
graph[u].append(v)与graph[v].append(u)都写。2. Floyd 的三重循环顺序写错:中转点 必须最外层(见 4.3)。
3. Dijkstra 忘记跳过过期堆条目:
if d > dist[u]: continue少了它结果仍然正确,但会把复杂度推高一个量级。4. BFS 在出队时才标记访问:应在入队时标记,否则同一节点可能被多次入队,队列体积爆炸。
5. 递归 DFS 在链状图上爆栈: 的链会超过 Python 默认递归上限,改用显式栈。
6. Tarjan 漏掉
on_stack判断:会把不同的 SCC 合并(见第八节)。7. 网络流忘记建反向边或反向边容量写错:正确做法是正向容量 、反向容量 ,成对存储并用
eid ^ 1互相索引。8. Bellman-Ford 判负环时忘了检查可达性:
dist[u] != INF这个前置条件不能省,否则不可达点会误报负环。9. 网格 BFS 越界:四个方向扩展前一定要判断
0 <= nr < m and 0 <= nc < n。
十三、练习题
练习 1(Dijkstra,给出完整解题过程)
LeetCode 743 网络延迟时间:有 个网络节点,
times[i] = (u, v, w)表示 到 的传信时间为 。从节点 发出一条信号,求所有节点都收到信号的最短时间;若有节点收不到返回 。
第一步:建模。节点是点,传输关系是有向边,传递时间是边权。题目求「从 到所有点的最短路中的最大值」——因为信号同时发出,最后一个收到的时间就是答案。
第二步:选算法。边权为正(传输时间),、边数 ,是稀疏图 → 堆优化 Dijkstra,。( 这么小,Floyd 也完全可行,可以作为对照实现。)
第三步:实现。
def network_delay_time(times, n, k):
"""LeetCode 743 网络延迟时间:单源最短路的最大值。O((V+E) log V)"""
graph = [[] for _ in range(n + 1)] # 节点编号 1..n
for u, v, w in times:
graph[u].append((v, w))
INF = float("inf")
dist = [INF] * (n + 1)
dist[k] = 0
pq = [(0, k)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue # 过期条目
for v, w in graph[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
ans = max(dist[1:]) # 取所有点的最短路最大值
return -1 if ans == INF else ans
第四步:分步推演。times = [[2,1,1],[2,3,1],[3,4,1]],n = 4,k = 2。
| 轮次 | 出堆 | dist[1] | dist[2] | dist[3] | dist[4] | 说明 |
|---|---|---|---|---|---|---|
| 初始 | — | ∞ | 0 | ∞ | ∞ | 起点 2 入堆 |
| 1 | 1 | 0 | 1 | ∞ | 松弛 、 | |
| 2 | 1 | 0 | 1 | ∞ | 节点 1 无出边 | |
| 3 | 1 | 0 | 1 | 2 | 松弛 | |
| 4 | 1 | 0 | 1 | 2 | 无出边 |
答案 。
第五步:边界检查。存在不可达节点 → max 会取到 INF,返回 。k 超出范围时 dist[k] 会 IndexError,实际题目保证 。注意 dist[1:] 切片是为了跳过下标 0(不存在的节点)。
练习 2(拓扑排序)
LeetCode 207 课程表:共
numCourses门课,prerequisites[i] = [a, b]表示修 a 之前必须先修 b。判断能否修完所有课程。
提示:课程是点,先修关系 是有向边。能修完 ⟺ 图中无环。用 Kahn 算法跑拓扑排序,若输出的点数等于 numCourses 则返回 True;也可用三色标记 DFS 判环。
练习 3(稠密图上的 Prim)
LeetCode 1584 连接所有点的最小费用:给定 个点的坐标,连接点 与 的费用是曼哈顿距离 ,求把所有点连起来的最小费用。
提示:这是完全图(), 意味着 接近 。用朴素 Prim ,每次线性扫描找「距离已选集合最近的点」,不要预先构造所有边(否则光是建图就要 空间且常数很大)。
练习 4(Bellman-Ford 的变体)
LeetCode 787 K 站中转内最便宜的航班:求从
src到dst最多经过k站中转的最低票价,不可达返回 。
提示:Bellman-Ford 的「松弛 轮」正好对应「最多经过 条边」——把轮数改成 轮( 站中转 = 条边)即可。关键细节:每轮必须用上一轮的 dist 快照来更新,否则同一轮内会串联松弛出「超过 条边」的路径,答案偏小。
练习 5(并查集 / 环检测)
LeetCode 684 冗余连接:在一棵树上加一条边形成的有向无环图中,找出那条可以删掉的边,使剩余部分是一棵树(若有多个答案,返回输入中最后出现的那条)。
提示:依次遍历边,用并查集合并;第一次 union 返回 False 的边就是答案(见第五节代码)。注意题目要求「最后出现的那条」,因此按输入顺序遍历、返回第一个失败者即可,因为形成环的那条边在输入顺序上就是使环闭合的那条。
十四、常见问题 FAQ
Dijkstra、Bellman-Ford、Floyd 三个最短路算法该怎么记?
按两个维度记:单源还是全源、能否处理负权。
- Dijkstra:单源、非负权、,贪心;
- Bellman-Ford:单源、可负权、,暴力松弛 + 判负环;
- Floyd:全源、可负权、,区间 DP。
一句话选择法:非负权就用 Dijkstra;有负权且单源用 Bellman-Ford; 很小且要所有点对用 Floyd。 A\* 是 Dijkstra 加上启发式,只在「有明确目标点 + 有好的启发函数」时才更快。
为什么 BFS 求最短路不需要「松弛」操作?
因为无权图(或边权全相等)中,路径长度就等于边数。BFS 按层扩展天然保证「第一次到达某点时用的边数最少」,不存在「先到但更贵」的可能,所以不需要像 Dijkstra 那样回头修正。一旦边权不等,「层」的概念就失效了——先到的路径可能更贵,于是必须用优先队列按代价排序,这就是 Dijkstra。
并查集真的可以当作 吗?
在「路径压缩 + 按秩合并」同时使用时, 次操作的总代价是 ,均摊到每次是 ,而 对一切实际可能的 成立,因此工程上完全可以当 。但要记住这是均摊界:单次
find的最坏代价仍是 ,在需要严格最坏时间保证的实时系统里要留意。
最大流为什么要建反向边?不建会怎样?
反向边让算法能「反悔」。举个最小例子:(容量 1)、(容量 1)、(容量 1)、(容量 1)、(容量 1)。若第一次错误地沿 推了 1 单位流,则 这条边就废了,最大流只能到 1;但有反向边时,算法可以沿 (其中 是 的反向边)推流,把之前的决策撤销,最终得到正确的最大流 2。反向边本质上是在残量网络上「退还」流量。
相关笔记
- 数据结构-图:图的存储结构(邻接矩阵 / 邻接表 / 边列表)与遍历基础
- 算法-动态规划与贪心:Dijkstra 与 Bellman-Ford 是「最短路上的 DP」,Floyd 是区间 DP 的近亲,状压 DP 解决 TSP
- 算法-查找与分治:二分答案常与最短路/生成树结合(如「最小化最大边权」)
- 算法-复杂度分析:、、 的推导与均摊分析
- 数据结构-树与堆:优先队列是 Dijkstra / Prim / A\* / 哈夫曼的共同基础设施
- 数据结构-哈希表:哈希表实现「隐式图」的状态去重(BFS 访问标记)
- 00-索引 / 学习路线图:回到总导航安排学习顺序
参考来源
- OI Wiki · BFS(广搜):BFS 的双端队列优化与最短路应用
- OI Wiki · DFS(深搜):DFS 的遍历序、时间戳与树边/后向边分类
- OI Wiki · 最短路(Dijkstra):堆优化实现与正确性条件
- OI Wiki · 最短路(Bellman-Ford / SPFA):松弛轮数原理、负环判定与 SPFA 退化
- OI Wiki · 最短路(Floyd):三重循环顺序与传递闭包
- OI Wiki · A\* 搜索:估价函数的可采纳性与一致性
- OI Wiki · 最小生成树:Kruskal、Prim 与切分定理
- OI Wiki · 拓扑排序:Kahn 算法与字典序最小拓扑序
- OI Wiki · 强连通分量:Tarjan 与 Kosaraju 算法
- OI Wiki · 网络流:最大流、最小割最大流定理与 Dinic
- OI Wiki · 二分图:匈牙利算法与二分图匹配
- OI Wiki · 并查集:路径压缩、按秩合并与复杂度证明
- cp-algorithms · Dijkstra · Bellman-Ford · Floyd-Warshall · Edmonds-Karp:英文推导与实现细节
- Red Blob Games · Introduction to A\:A\ 与 Dijkstra 关系的交互式可视化讲解
- LeetCode 743 网络延迟时间 · 207 课程表 · 210 课程表 II · 547 省份数量 · 684 冗余连接 · 785 判断二分图 · 787 K 站中转内最便宜的航班 · 1584 连接所有点的最小费用