数据结构-图
一句话概括
图(Graph) 是由「顶点集合」和「边集合」组成的数学模型,用来描述任意两个对象之间都可能存在关系的场景:社交网络的好友关系、地图上的道路、课程之间的先修依赖、网页之间的超链接。
本篇覆盖:图的两种存储方式、BFS/DFS 两大遍历框架、连通性、环检测、拓扑排序(Topological Sort)、最短路径(BFS / Dijkstra / Floyd)、最小生成树(Minimum Spanning Tree, MST)、二分图染色、强连通分量(Strongly Connected Component, SCC)、欧拉回路与哈密顿路径。
所有算法都给出可直接运行的 Python 实现,并逐步说明状态如何变化。
是什么
图的数学定义
一个图写作 :
- 是顶点(Vertex / Node)的集合, 记作
- 是边(Edge)的集合, 记作
- 每条边连接一对顶点,写成
图与树的根本区别:树是"无环连通图"这一特例(且 ),而图允许环、允许不连通、允许任意多的边(最多约 条)。
术语表
| 术语 | 含义 | 例子 |
|---|---|---|
| 有向图(Directed Graph) | 边有方向, 表示 ,与 不同 | 微博关注、课程先修 |
| 无向图(Undirected Graph) | 边无方向, 等价于 | 微信好友、无向道路 |
| 加权图(Weighted Graph) | 每条边带权值(距离、代价、时间) | 地图导航 |
| 度(Degree) | 无向图中与顶点相连的边数;有向图分「入度 in-degree」与「出度 out-degree」 | 好友数量、粉丝数 |
| 路径(Path) | 顶点序列 ,相邻两点间都有边 | 换乘路线 |
| 简单路径 | 顶点不重复的路径 | — |
| 环(Cycle) | 起点等于终点的路径 | 循环依赖 |
| 自环(Self-loop) | 的边 | 自己关注自己 |
| 重边(Multi-edge) | 两顶点间多条边 | 两条不同的路 |
| 连通(Connected) | 无向图中两顶点间存在路径 | — |
| 连通分量(Connected Component) | 无向图的极大连通子图 | 社交网络中的孤立圈子 |
| 强连通(Strongly Connected) | 有向图中 能到 且 能到 | — |
| 强连通分量(SCC) | 有向图的极大强连通子图 | 循环依赖的一组模块 |
| 稠密图 / 稀疏图 | 接近 / 接近 | 完全图 / 稀疏路网 |
| 二分图(Bipartite Graph) | 顶点可分成两个集合,所有边的两端分属不同集合 | 男女配对、课程-教室 |
握手引理
无向图中所有顶点的度数之和等于边数的两倍:。
推论:度数为奇数的顶点一定是偶数个(这条常出现在图论证明题里)。
有向图中,入度之和 = 出度之和 = 。
为什么需要它
很多现实问题用「线性结构」表达不出来:
| 现实问题 | 图的建模方式 | 用到的算法 |
|---|---|---|
| 从 A 到 B 的最快路线 | 路口 = 顶点,道路 = 加权边 | Dijkstra |
| 修路让所有城市连通且总造价最低 | 城市 = 顶点,造价 = 权 | Kruskal / Prim |
| 课程安排是否可行 | 课程 = 顶点,先修 = 有向边 | 拓扑排序 + 环检测 |
| 两人是否属于同一个社交圈 | 人 = 顶点,好友 = 无向边 | 并查集 / BFS |
| 任务能否拆成两组互不冲突 | 冲突 = 边 | 二分图染色 |
| 编译器的循环依赖检测 | 模块 = 顶点,依赖 = 有向边 | Tarjan SCC |
关键动机:图算法把「无法枚举的指数级搜索空间」压缩成「对每个顶点和每条边只访问常数次」,从而把 的问题降到 或 。
核心内容
一、两种表示法
邻接矩阵(Adjacency Matrix)
用 的二维数组 g[u][v] 存放边:
- 无权图:
g[u][v] = 1表示有边,0表示无边 - 加权图:
g[u][v] = w表示边权,无边用INF(正无穷)
邻接表(Adjacency List)
每个顶点维护一个列表,存放它的所有邻居:
g[u] = [(v, w), ...],加权图存(邻居, 权重)二元组
同一张图的两种存储示例
取图:顶点 ,无向边 ,其中 权重为 7。
0
/ \
1---2 --7-- 3
邻接矩阵(INF 表示无边,对角线为 0):
0 1 2 3
0 [ 0, 1, 1, INF ]
1 [ 1, 0, 1, INF ]
2 [ 1, 1, 0, 7 ]
3 [ INF, INF, 7, 0 ]
邻接表:
0 -> [(1,1), (2,1)]
1 -> [(0,1), (2,1)]
2 -> [(0,1), (1,1), (3,7)]
3 -> [(2,7)]
对比表
| 维度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间复杂度 | ||
| 判断 是否有边 | ,最坏 | |
| 遍历某顶点的所有邻居 | ||
| 遍历整张图(BFS/DFS) | ||
| 加边 | ||
| 删边 | ||
| 适合的图 | 稠密图()、需要频繁查边 | 稀疏图(),绝大多数真实场景 |
| 额外好处 | 矩阵乘法可求路径条数、可做 Floyd | 省内存,能存重边 |
怎么选
先看 : 且需要 Floyd 或频繁询问两点是否有边 → 邻接矩阵; → 一律邻接表。
现实的图几乎都是稀疏的(社交网络平均好友数远小于总人数),所以邻接表是默认选择。
"""图的两种表示法:邻接矩阵与邻接表,以及它们之间的转换。"""
INF = float("inf")
class GraphMatrix:
"""邻接矩阵实现,适合稠密图与需要 O(1) 查边的场景。"""
def __init__(self, n):
self.n = n
# 对角线为 0:顶点到自己的距离是 0,这一点在 Floyd 中很关键
self.g = [[INF] * n for _ in range(n)]
for i in range(n):
self.g[i][i] = 0
def add_edge(self, u, v, w=1, directed=False):
self.g[u][v] = w
if not directed:
self.g[v][u] = w # 无向图两个方向都要写
def has_edge(self, u, v):
return self.g[u][v] != INF
def neighbors(self, u):
return [(v, self.g[u][v]) for v in range(self.n) if u != v and self.g[u][v] != INF]
class GraphList:
"""邻接表实现,适合稀疏图,是竞赛与工程中的默认选择。"""
def __init__(self, n):
self.n = n
self.g = [[] for _ in range(n)] # g[u] 存 (邻居, 权重)
def add_edge(self, u, v, w=1, directed=False):
self.g[u].append((v, w))
if not directed:
self.g[v].append((u, w))
def neighbors(self, u):
return self.g[u]
def degree(self, u):
return len(self.g[u])
def build_demo():
"""用同一张图构造两种存储,验证结果一致。"""
edges = [(0, 1, 1), (0, 2, 1), (1, 2, 1), (2, 3, 7)]
gm = GraphMatrix(4)
gl = GraphList(4)
for u, v, w in edges:
gm.add_edge(u, v, w)
gl.add_edge(u, v, w)
print("邻接矩阵 2 的邻居:", sorted(gm.neighbors(2))) # [(0,1),(1,1),(3,7)]
print("邻接表 2 的邻居:", sorted(gl.neighbors(2))) # [(0,1),(1,1),(3,7)]
assert sorted(gm.neighbors(2)) == sorted(gl.neighbors(2))
# 握手引理验证:度数和 = 2 * 边数
assert sum(gl.degree(u) for u in range(4)) == 2 * len(edges)
print("两种表示一致,握手引理成立")
if __name__ == "__main__":
build_demo()
二、BFS 与 DFS
两种遍历是所有图算法的骨架。它们都要解决同一个问题:如何不重复地访问到所有可达顶点。区别只在「先访问谁」。
BFS(Breadth-First Search,广度优先搜索)
用队列(Queue):先访问起点,再把起点的所有邻居入队,按「距起点层数」逐层扩散。
- 关键性质:在无权图中,BFS 首次到达某点的距离就是最短距离
- 复杂度:,每个顶点入队一次、每条边被检查一次
状态变化示例:从 0 出发,图 0-1, 0-2, 1-2, 2-3
| 步骤 | 出队 | 队列内容 | dist |
|---|---|---|---|
| 初始 | — | [0] | [0, ∞, ∞, ∞] |
| 1 | 0 | [1, 2] | [0, 1, 1, ∞] |
| 2 | 1 | [2](2 已访问,跳过) | [0, 1, 1, ∞] |
| 3 | 2 | [3] | [0, 1, 1, 2] |
| 4 | 3 | [] | [0, 1, 1, 2] |
DFS(Depth-First Search,深度优先搜索)
用栈(Stack)或递归:一路走到底,走不动再回退。
- 关键性质:能天然给出「进入时间 / 离开时间」,是环检测、拓扑排序、割点桥、SCC 的基础
- 复杂度:
- 递归实现简洁但有栈溢出风险, 的链状图应改用显式栈
两者对比
| 维度 | BFS | DFS |
|---|---|---|
| 数据结构 | 队列(FIFO) | 栈 / 递归(LIFO) |
| 时间复杂度 | ||
| 空间复杂度 | (最坏队列存一整层) | (最坏递归深度 ) |
| 无权最短路 | 能(首次到达即最短) | 不能直接给 |
| 环检测 / 拓扑排序 | 可以(Kahn) | 可以(三色 / 逆后序) |
| 割点与桥 | 不常用 | 主力 |
| 二分图染色 | 可以 | 可以 |
| 典型用途 | 最短步数、层序遍历、多源扩散 | 枚举路径、连通分量、回溯剪枝 |
"""BFS 与 DFS 的完整实现(邻接表,无向无权图)。
包含:
1. 单源 BFS 求最短距离与路径
2. 多源 BFS(求每个点到最近源点的距离)
3. 递归 DFS 与迭代 DFS
"""
from collections import deque
def build_adj(n, edges, directed=False):
"""把边列表转成邻接表。"""
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
if not directed:
g[v].append(u)
return g
def bfs(g, src):
"""单源 BFS。
返回 (dist, parent):
dist[v] = src 到 v 的最短边数,不可达为 -1
parent[v] = v 在 BFS 树上的父节点,用于回溯路径
复杂度 O(V+E):每个顶点最多入队一次,每条边最多被检查两次(无向图)。
"""
n = len(g)
dist = [-1] * n
parent = [-1] * n
dist[src] = 0
q = deque([src]) # 队列初始化:只有源点
while q:
u = q.popleft() # 出队:按入队顺序处理,保证按层扩散
for v in g[u]:
if dist[v] != -1:
continue # 已访问过就跳过,这是 BFS 不重复的关键
dist[v] = dist[u] + 1
parent[v] = u
q.append(v) # 入队:新发现的顶点排到队尾
return dist, parent
def restore_path(parent, src, dst):
"""从 parent 数组回溯出 src -> dst 的具体路径。"""
if parent[dst] == -1 and src != dst:
return [] # 不可达
path = []
cur = dst
while cur != -1:
path.append(cur)
cur = parent[cur]
return path[::-1]
def multi_source_bfs(g, sources):
"""多源 BFS:把所有源点先入队,一次遍历求出每个点到最近源点的距离。
典型场景:地图上多个便利店,求每个小区到最近便利店的距离(等价于加一个
虚拟超级源点连向所有源点)。
"""
dist = [-1] * len(g)
q = deque()
for s in sources:
dist[s] = 0
q.append(s) # 所有源点同时入队,层数从 0 开始一起扩散
while q:
u = q.popleft()
for v in g[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)
return dist
def dfs_recursive(g, u, visited, order=None, parent=None):
"""递归 DFS:记录首次访问顺序。"""
visited[u] = True
if order is not None:
order.append(u)
for v in g[u]:
if not visited[v]:
if parent is not None:
parent[v] = u
dfs_recursive(g, v, visited, order, parent)
def dfs_iterative(g, src):
"""迭代 DFS:用显式栈,避免深图递归爆栈。
注意:为了与递归版得到相同的访问顺序,这里把邻居逆序压栈,
因为栈是后进先出,最后压入的会最先被弹出。
"""
visited = [False] * len(g)
order = []
stack = [src]
while stack:
u = stack.pop()
if visited[u]:
continue # 可能在压栈后被别的路径访问过,需要二次检查
visited[u] = True
order.append(u)
for v in reversed(g[u]):
if not visited[v]:
stack.append(v)
return order
if __name__ == "__main__":
edges = [(0, 1), (0, 2), (1, 2), (2, 3), (4, 5)]
g = build_adj(7, edges)
dist, parent = bfs(g, 0)
print("从 0 出发的 dist:", dist) # [0, 1, 1, 2, -1, -1, -1]
print("0 -> 3 的路径:", restore_path(parent, 0, 3)) # [0, 2, 3]
print("多源 BFS(源点 0 和 5):", multi_source_bfs(g, [0, 5]))
# [0, 1, 1, 2, 1, 0, -1]
# 注意下标 4:它离源点 5 只有 1 步(边 4-5),而不是离 0 的 3 步
# 6 号点是孤立点,所有源点都到不了,所以是 -1
visited = [False] * 7
order = []
dfs_recursive(g, 0, visited, order)
print("递归 DFS 顺序:", order)
print("迭代 DFS 顺序:", dfs_iterative(g, 0))
三、连通性与割点桥
求无向图的连通分量
对每个未访问顶点做一次 BFS/DFS,计数器就是连通分量个数。复杂度 。
def count_components(n, edges):
"""返回无向图的连通分量个数以及每个点所属的分量编号。"""
g = build_adj(n, edges)
comp = [-1] * n
cid = 0
for s in range(n):
if comp[s] != -1:
continue
# 从 s 出发 flood fill 整个分量
stack = [s]
comp[s] = cid
while stack:
u = stack.pop()
for v in g[u]:
if comp[v] == -1:
comp[v] = cid
stack.append(v)
cid += 1
return cid, comp
割点与桥
- 割点(Articulation Point / Cut Vertex):删掉它之后,连通分量数量增加
- 桥(Bridge / Cut Edge):删掉它之后,连通分量数量增加
它们的意义是网络的薄弱环节:路由器布局中,割点就是单点故障。
判定思路(Tarjan 的 dfn / low 算法):
- DFS 一遍,记录每个点的访问时间
dfn[u](第几个被访问) low[u]= 从 出发,经过至多一条回边能到达的最小dfn- 对树边 :
- 若
low[v] > dfn[u],则 是桥 - 若
low[v] >= dfn[u]且 不是根,则 是割点
- 根节点是割点 它有 个 DFS 子树
def find_bridges_and_cut_vertices(n, edges):
"""Tarjan 求无向图的桥与割点,复杂度 O(V+E)。"""
g = build_adj(n, edges)
dfn = [-1] * n
low = [0] * n
timer = 0
bridges = []
cut = set()
def dfs(u, parent_edge):
nonlocal timer
dfn[u] = low[u] = timer
timer += 1
children = 0
for v in g[u]:
if dfn[v] == -1: # 树边
children += 1
dfs(v, u)
low[u] = min(low[u], low[v])
if low[v] > dfn[u]: # 子树回不到 u 或更早 -> 桥
bridges.append((u, v))
if parent_edge != -1 and low[v] >= dfn[u]:
cut.add(u) # 非根且有子树回不到祖先 -> 割点
elif v != parent_edge: # 回边(跳过指向父节点的边)
low[u] = min(low[u], dfn[v])
if parent_edge == -1 and children >= 2:
cut.add(u) # 根:>=2 棵子树才是割点
for s in range(n):
if dfn[s] == -1:
dfs(s, -1)
return bridges, sorted(cut)
if __name__ == "__main__":
# 0-1-2-3 是一条链,再加一个环 3-4-5-3
n = 6
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 3)]
print(find_bridges_and_cut_vertices(n, edges))
# 桥: [(2,3),(1,2),(0,1)];割点: [1,2,3]
四、环检测
有向图:三色标记法
给每个顶点三种颜色:
| 颜色 | 含义 | 说明 |
|---|---|---|
| 白色(0) | 未访问 | 还没进入过 |
| 灰色(1) | 在递归栈中 | 正在访问它的子树 |
| 黑色(2) | 已完成 | 它的所有后继都处理完了 |
判定规则:DFS 中遇到一个灰色顶点,就说明存在环。 这条边叫回边(back edge),它指向当前递归栈里的祖先,恰好构成一个环。
为什么是灰色而不是黑色
遇到黑色顶点说明那条路已经完全走完,从它出发回不到当前点,不构成环。
只有「还在栈里」的祖先才能和当前点连成一个环。
无向图:并查集(Disjoint Set Union, DSU)
无向图加边时,如果两个端点已经属于同一个集合,这条边就形成了一个环。
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):
# 路径压缩:把沿途所有节点直接挂到根上,后续查询近乎 O(1)
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # 路径减半
x = self.parent[x]
return x
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
self.count -= 1
return True
def has_cycle_undirected(n, edges):
"""无向图环检测(并查集版)。"""
dsu = DSU(n)
for u, v in edges:
if not dsu.union(u, v):
return True, (u, v) # 两端已连通,这条边构成环
return False, None
def has_cycle_directed(n, edges):
"""有向图环检测(三色标记法)。返回 (是否有环, 环上的一条边)。"""
g = build_adj(n, edges, directed=True)
color = [0] * n # 0 白 1 灰 2 黑
def dfs(u):
color[u] = 1 # 进入:染灰,压入递归栈
for v in g[u]:
if color[v] == 1:
return True, (u, v) # 撞到灰色:回边,有环
if color[v] == 0 and dfs(v)[0]:
return True, (u, v)
color[u] = 2 # 离开:染黑,出栈
return False, None
for s in range(n):
if color[s] == 0:
found, edge = dfs(s)
if found:
return True, edge
return False, None
if __name__ == "__main__":
print(has_cycle_undirected(4, [(0, 1), (1, 2), (2, 3)])) # (False, None)
print(has_cycle_undirected(4, [(0, 1), (1, 2), (2, 0)])) # (True, (2, 0))
print(has_cycle_directed(3, [(0, 1), (1, 2), (2, 0)])) # (True, (2, 0))
print(has_cycle_directed(3, [(0, 1), (0, 2), (1, 2)])) # (False, None)
五、拓扑排序
问题:给定有向图,把所有顶点排成一个线性序列,使每条边 中 都排在 前面。
存在条件:图是有向无环图(Directed Acyclic Graph, DAG)。有环就没法排(A 先于 B,B 先于 A 矛盾)。
Kahn 算法(BFS 版)
核心是入度:
- 统计所有点的入度,把入度为 0 的点入队
- 反复出队一个点 ,加入结果序列;把 的所有邻居入度减 1
- 若某邻居入度变成 0,入队
- 结束时若结果长度 ,说明有环
状态变化示例:课程依赖 0->2, 1->2, 2->3
| 步骤 | 入度数组 | 队列 | 结果 |
|---|---|---|---|
| 初始 | [0,0,2,1] | [0,1] | [] |
| 出队 0 | [0,0,1,1] | [1] | [0] |
| 出队 1 | [0,0,0,1] | [2] | [0,1] |
| 出队 2 | [0,0,0,0] | [3] | [0,1,2] |
| 出队 3 | [0,0,0,0] | [] | [0,1,2,3] |
DFS 算法
后序遍历(post-order)的逆序就是拓扑序。直觉:一个点被染黑时,它的所有后继都已染黑,所以它在「完成时间」上最早于后继——倒过来刚好满足「前驱在前」。
"""拓扑排序:Kahn 算法与 DFS 两种实现,附带课程表应用题。"""
from collections import deque
def topo_kahn(n, edges):
"""Kahn 算法。返回 (拓扑序, 是否有环)。
复杂度 O(V+E):每条边恰好被松弛一次。
"""
g = build_adj(n, edges, directed=True)
indeg = [0] * n
for u, v in edges:
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 g[u]:
indeg[v] -= 1 # 前驱 u 已完成,v 的约束少一个
if indeg[v] == 0:
q.append(v) # v 的所有前驱都完成了,可以做
return (order, True) if len(order) == n else (order, False)
def topo_dfs(n, edges):
"""DFS 版拓扑排序:后序逆序。顺便用三色法判环。"""
g = build_adj(n, edges, directed=True)
color = [0] * n
order = []
ok = True
def dfs(u):
nonlocal ok
color[u] = 1
for v in g[u]:
if color[v] == 1:
ok = False # 回边 -> 有环,拓扑序无意义
return
if color[v] == 0:
dfs(v)
color[u] = 2
order.append(u) # 后序:所有后继都已完成
for s in range(n):
if color[s] == 0:
dfs(s)
order.reverse() # 后序的逆序即拓扑序
return order, ok
def can_finish(num_courses, prerequisites):
"""LeetCode 207 课程表:判断能否修完所有课程。
prerequisites[i] = [a, b] 表示修 a 之前必须先修 b,即边 b -> a。
"""
edges = [(b, a) for a, b in prerequisites]
_, ok = topo_kahn(num_courses, edges)
return ok
def find_order(num_courses, prerequisites):
"""LeetCode 210 课程表 II:返回一种可行的修课顺序,不可能则返回 []。"""
edges = [(b, a) for a, b in prerequisites]
order, ok = topo_kahn(num_courses, edges)
return order if ok else []
if __name__ == "__main__":
print(topo_kahn(4, [(0, 2), (1, 2), (2, 3)]))
# ([0, 1, 2, 3], True)
print(topo_dfs(4, [(0, 2), (1, 2), (2, 3)]))
# ([1, 0, 2, 3], True)
# 与 Kahn 的 [0, 1, 2, 3] 不同但同样合法:0 和 1 之间没有约束,谁先都行
print(can_finish(2, [[1, 0]])) # True
print(can_finish(2, [[1, 0], [0, 1]])) # False(互相依赖,成环)
print(find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])) # [0,1,2,3] 或 [0,2,1,3]
拓扑序不唯一
任何时刻有多个入度为 0 的点时,选谁都可以得到合法的拓扑序。
若题目要求「字典序最小」,把队列换成最小堆,复杂度变为 。
六、最短路径
1. BFS:无权图单源最短路
已在遍历一节给出:。只要边权都相等,BFS 就是最优解。
2. Dijkstra:非负权单源最短路
贪心思想:每次从「未确定的点」中取出当前距离最小的点,它的距离就已经是最终答案(因为所有边权非负,绕远路不可能更短)。
- 朴素版:每轮线性扫描找最小值,,适合稠密图
- 堆优化版:用优先队列取最小值,,适合稀疏图
状态变化示例:图为 0-(1)-1, 0-(4)-2, 1-(2)-2, 1-(5)-3, 2-(1)-3
| 步骤 | 确定点 | dist | 优先队列(部分) |
|---|---|---|---|
| 初始 | — | [0, ∞, ∞, ∞] | [(0,0)] |
| 1 | 0 | [0,1,4,∞] | [(1,1),(4,2)] |
| 2 | 1 | [0,1,3,6] | [(3,2),(6,3)] |
| 3 | 2 | [0,1,3,4] | [(4,3)] |
| 4 | 3 | [0,1,3,4] | [] |
Dijkstra 不能处理负权边
反例:
0-(2)-1, 0-(5)-2, 1-(-4)-2。Dijkstra 会先确定dist[2]=5,但真实最短路是 。负权图要用 Bellman-Ford()或 SPFA。
3. Floyd-Warshall:多源最短路
动态规划:设 表示「只允许经过前 个顶点作为中转时, 到 的最短距离」,则
滚动掉第一维后用三重循环原地更新,复杂度 ,空间 。能处理负权边(但不能有负环)。
三种算法对比
| 算法 | 类型 | 时间复杂度 | 空间 | 负权边 | 负环 | 适用场景 |
|---|---|---|---|---|---|---|
| BFS | 单源,无权 | 不适用 | 不适用 | 边权全为 1、求最少步数 | ||
| Dijkstra(朴素) | 单源 | ✗ | ✗ | 稠密图() | ||
| Dijkstra(堆优化) | 单源 | ✗ | ✗ | 稀疏图,最常用 | ||
| Bellman-Ford | 单源 | ✓ | 可检测 | 有负权边、需要判负环 | ||
| Floyd-Warshall | 多源 | ✓ | 可检测(对角线为负) | ,求所有点对距离 |
"""最短路径三件套:Dijkstra(朴素 + 堆优化)与 Floyd-Warshall。"""
import heapq
INF = float("inf")
def dijkstra_naive(n, edges, src):
"""朴素 Dijkstra O(V^2),用邻接矩阵。
适合稠密图:因为没有堆操作的开销,常数比堆优化小。
"""
g = [[INF] * n for _ in range(n)]
for i in range(n):
g[i][i] = 0
for u, v, w in edges:
g[u][v] = min(g[u][v], w) # 有重边时取最小
g[v][u] = min(g[v][u], w)
dist = [INF] * n
used = [False] * n
dist[src] = 0
for _ in range(n):
# 第一步:在未确定的点里找距离最小的
u, best = -1, INF
for i in range(n):
if not used[i] and dist[i] < best:
u, best = i, dist[i]
if u == -1:
break # 剩余点都不可达
used[u] = True # 第二步:确定 u 的最短距离
for v in range(n): # 第三步:用 u 松弛所有邻居
if dist[u] + g[u][v] < dist[v]:
dist[v] = dist[u] + g[u][v]
return dist
def dijkstra_heap(n, edges, src, directed=False):
"""堆优化 Dijkstra O((V+E) log V),用邻接表。"""
g = build_weighted_adj(n, edges, directed)
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 g[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v)) # 允许同一点多次入堆
return dist
def build_weighted_adj(n, edges, directed=False):
g = [[] for _ in range(n)]
for u, v, w in edges:
g[u].append((v, w))
if not directed:
g[v].append((u, w))
return g
def floyd(n, edges, directed=False):
"""Floyd-Warshall O(V^3),返回距离矩阵。"""
d = [[INF] * n for _ in range(n)]
for i in range(n):
d[i][i] = 0
for u, v, w in edges:
d[u][v] = min(d[u][v], w)
if not directed:
d[v][u] = min(d[v][u], w)
for k in range(n): # 中转点必须放最外层!
for i in range(n):
if d[i][k] == INF:
continue # 剪枝:i 到不了 k 就不用试了
for j in range(n):
if d[i][k] + d[k][j] < d[i][j]:
d[i][j] = d[i][k] + d[k][j]
return d
if __name__ == "__main__":
edges = [(0, 1, 1), (0, 2, 4), (1, 2, 2), (1, 3, 5), (2, 3, 1)]
print("朴素 :", dijkstra_naive(4, edges, 0)) # [0, 1, 3, 4]
print("堆优化:", dijkstra_heap(4, edges, 0)) # [0, 1, 3, 4]
for row in floyd(4, edges):
print(["INF" if x == INF else x for x in row])
# [[0,1,3,4],[1,0,2,3],[3,2,0,1],[4,3,1,0]]
七、最小生成树
问题:在带权连通无向图中选出一棵生成树(含全部 个顶点、恰好 条边),使边权总和最小。
切分定理(Cut Property)
把顶点分成两个非空集合 与 (这个划分叫切分)。横跨切分的边中,权值最小的那条一定属于某棵最小生成树。
这条定理是 Kruskal 和 Prim 正确性的共同基础:Kruskal 每次选的是「让两个连通块合并的最小边」,Prim 每次选的是「已选集合与未选集合之间最小的边」。
Kruskal 算法
按边权从小到大排序,依次尝试加入;用并查集判断是否成环,成环就跳过。复杂度 (瓶颈在排序),适合稀疏图。
Prim 算法
从一个点出发,每次把「连接已选集合与未选集合的最小边」加进来,重复 次。堆优化后复杂度 ,适合稠密图(朴素版 )。
对比
| 维度 | Kruskal | Prim |
|---|---|---|
| 思想 | 全局贪心选最小边 + 并查集 | 局部贪心扩展点集 |
| 时间复杂度 | (堆优化)/ (朴素) | |
| 适合图 | 稀疏图 | 稠密图 |
| 是否需要并查集 | 是 | 否 |
| 处理不连通图 | 能自然得到「最小生成森林」 | 只能得到起点所在分量的 MST |
| 实现难度 | 简单 | 中等 |
"""最小生成树:Kruskal 与 Prim。"""
import heapq
def kruskal(n, edges):
"""Kruskal:返回 (总权值, 选中的边列表)。复杂度 O(E log E)。"""
dsu = DSU(n)
mst, total = [], 0
# 按权值排序,之后依次贪心取最小边
for u, v, w in sorted(edges, key=lambda e: e[2]):
if dsu.union(u, v): # 不成环才接受这条边
mst.append((u, v, w))
total += w
if len(mst) == n - 1:
break # 已有 n-1 条边,生成树完成
return (total, mst) if len(mst) == n - 1 else (None, mst) # None 表示不连通
def prim(n, edges, src=0):
"""Prim(堆优化):返回 (总权值, 选中的边列表)。复杂度 O(E log V)。"""
g = build_weighted_adj(n, edges)
used = [False] * n
pq = [(0, src, -1)] # (边权, 目标点, 来向点)
total, mst = 0, []
while pq:
w, u, parent = heapq.heappop(pq)
if used[u]:
continue # 惰性删除:这个点已通过更短的边加入
used[u] = True
total += w
if parent != -1:
mst.append((parent, u, w))
for v, w2 in g[u]: # 把 u 的新边全部压入堆,作为候选
if not used[v]:
heapq.heappush(pq, (w2, v, u))
return (total, mst) if len(mst) == n - 1 else (None, mst)
if __name__ == "__main__":
n = 5
edges = [
(0, 1, 2), (0, 3, 6), (1, 2, 3), (1, 3, 8),
(1, 4, 5), (2, 4, 7), (3, 4, 9),
]
print("Kruskal:", kruskal(n, edges)[0]) # 16
print("Prim :", prim(n, edges)[0]) # 16
八、二分图判定与染色
二分图(Bipartite Graph):顶点能分成两个集合 ,使每条边的两端一个在 、一个在 。
判定方法:黑白染色。任选起点染黑,它的邻居染白,依次 BFS/DFS。若发现某条边的两端颜色相同,就不是二分图。
重要等价命题:
二分图 ⟺ 图中不存在奇环
一个图是二分图,当且仅当它不含长度为奇数的环。因为绕奇环走一圈会要求同一个点既黑又白,矛盾。
这就是 LeetCode 785「判断二分图」的解法基础,也是「能否把学生分成两组且组内无冲突」的判定依据。
def is_bipartite(n, edges):
"""黑白染色判定二分图,并返回一个合法染色。复杂度 O(V+E)。"""
g = build_adj(n, edges)
color = [-1] * n # -1 未染色,0 一种颜色,1 另一种
for s in range(n): # 图可能不连通,每个分量都要染
if color[s] != -1:
continue
color[s] = 0
q = deque([s])
while q:
u = q.popleft()
for v in g[u]:
if color[v] == -1:
color[v] = color[u] ^ 1 # 邻居染相反颜色
q.append(v)
elif color[v] == color[u]:
return False, None # 相邻同色 -> 有奇环 -> 不是二分图
return True, color
if __name__ == "__main__":
# 偶环 0-1-2-3-0 是二分图
print(is_bipartite(4, [(0, 1), (1, 2), (2, 3), (3, 0)])) # (True, [0,1,0,1])
# 三角环 0-1-2-0 不是二分图
print(is_bipartite(3, [(0, 1), (1, 2), (2, 0)])) # (False, None)
九、强连通分量(Tarjan 思路)
强连通分量:有向图中极大的、内部任意两点互相可达的顶点集合。把每个 SCC 缩成一个点后,得到的图一定是 DAG(叫缩点图 / condensation)。
Tarjan 算法用一个 DFS 同时求出所有 SCC:
- 维护
dfn[u](访问时间)与low[u](能回溯到的最小dfn) - 维护一个栈,按 DFS 顺序压入访问过的点
- DFS 完 的所有邻居后,若
low[u] == dfn[u],说明 是它所在 SCC 的「根」——栈中从 到栈顶的所有点构成一个 SCC,全部弹出
复杂度 ,只需一次 DFS,比 Kosaraju 算法(两遍 DFS + 反图)更紧凑。
def tarjan_scc(n, edges):
"""Tarjan 求强连通分量,返回每个点所属的 SCC 编号(缩点后的点号)。"""
g = build_adj(n, edges, directed=True)
dfn = [-1] * n
low = [0] * n
on_stack = [False] * n
stack = []
comp = [-1] * n
timer = 0
cid = 0
def dfs(u):
nonlocal timer, cid
dfn[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = True
for v in g[u]:
if dfn[v] == -1:
dfs(v)
low[u] = min(low[u], low[v]) # 用子树的 low 更新
elif on_stack[v]:
low[u] = min(low[u], dfn[v]) # 后退边:只能连到栈内的点
if low[u] == dfn[u]:
# u 是 SCC 的根,弹出栈中 u 之上的所有点
while True:
x = stack.pop()
on_stack[x] = False
comp[x] = cid
if x == u:
break
cid += 1
for s in range(n):
if dfn[s] == -1:
dfs(s)
return comp, cid
if __name__ == "__main__":
# 0->1->2->0 构成一个 SCC;3 单独;4->5->4 构成另一个
edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 4)]
print(tarjan_scc(6, edges)) # ([0,0,0,1,2,2], 3)
十、欧拉回路与哈密顿路径
这是图论里最容易被混淆的一对概念:
| 概念 | 定义 | 判定 | 复杂度 |
|---|---|---|---|
| 欧拉路径(Eulerian Path) | 经过每条边恰好一次的路径 | 无向图:0 或 2 个奇度点;有向图:至多一个点出度比入度大 1,至多一个点入度比出度大 1 | ,多项式时间可解 |
| 欧拉回路(Eulerian Circuit) | 起点终点相同的欧拉路径 | 所有点度数为偶(无向);所有点入度 = 出度(有向) | ,Hierholzer 算法 |
| 哈密顿路径(Hamiltonian Path) | 经过每个顶点恰好一次的路径 | 无已知的简单充要条件 | NP 完全( 大时无多项式解) |
一句话记住区别
欧拉是「边不重复」,哈密顿是「点不重复」。
前者是好问题(多项式可解,本质是 DFS 找环),后者是难问题(NP 完全,只能暴力 + 状压 DP,)。
这个「看起来很像却一个简单一个极难」的对比,正是 P vs NP 问题最直观的入口(详见 算法-复杂度分析)。
欧拉回路常用 Hierholzer 算法:DFS 走到不能走,回溯时把点压入路径,最后逆序即为答案。
def euler_circuit(n, edges):
"""Hierholzer 求无向图的欧拉回路。返回路径顶点序列,不存在返回 None。"""
g = build_adj(n, edges)
deg = [len(g[i]) for i in range(n)]
# 判定:所有顶点度数为偶,且所有有边的点在同一个连通分量里
for i in range(n):
if deg[i] % 2 == 1:
return None
# 用边的索引做去重,避免重边被误删
used_edge = set()
edge_id = {}
for idx, (u, v) in enumerate(edges):
edge_id.setdefault((u, v), []).append(idx)
edge_id.setdefault((v, u), []).append(idx)
ptr = [0] * n # 当前弧优化:每条边只被扫描一次
path = []
stack = [next((i for i in range(n) if deg[i] > 0), 0)]
while stack:
u = stack[-1]
advanced = False
while ptr[u] < len(g[u]):
v = g[u][ptr[u]]
ptr[u] += 1
# 找一条还没用过的边
eid = next((i for i in edge_id[(u, v)] if i not in used_edge), None)
if eid is None:
continue
used_edge.add(eid)
stack.append(v)
advanced = True
break
if not advanced:
path.append(stack.pop()) # 回溯时记录,最后逆序
return path[::-1]
if __name__ == "__main__":
# 四边形 0-1-2-3-0,每个点度数为 2,存在欧拉回路
print(euler_circuit(4, [(0, 1), (1, 2), (2, 3), (3, 0)])) # [0,3,2,1,0] 之类
# 加分一条悬挂边会让两个点变奇度,不存在欧拉回路
print(euler_circuit(5, [(0, 1), (1, 2), (2, 3), (3, 0), (0, 4)])) # None
一笔画问题的两个前提
除了度数条件,还必须检查所有有边的顶点属于同一连通分量。
一个孤立点不影响判定,但两个分离的环各自度数为偶,却无法一笔画完。
怎么用
场景一:迷宫最短路(BFS 网格图)
网格是最常见的隐式图:每个格子是顶点,上下左右相邻是边。
from collections import deque
def shortest_path_grid(grid, start, goal):
"""在 0/1 网格中求最短步数,1 表示障碍。返回步数,不可达返回 -1。"""
R, C = len(grid), len(grid[0])
dist = [[-1] * C for _ in range(R)]
dist[start[0]][start[1]] = 0
q = deque([start])
while q:
r, c = q.popleft()
if (r, c) == goal:
return dist[r][c] # BFS 首次到达即最短
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 0 and dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))
return -1
if __name__ == "__main__":
grid = [
[0, 0, 0, 0],
[1, 1, 0, 1],
[0, 0, 0, 0],
]
print(shortest_path_grid(grid, (0, 0), (2, 3))) # 5
场景二:判断任务依赖是否可执行
def can_schedule(num_tasks, dependencies):
"""dependencies[i] = (a, b) 表示 a 依赖 b(b 必须先完成)。"""
edges = [(b, a) for a, b in dependencies]
_, ok = topo_kahn(num_tasks, edges)
return ok
def schedule_order(num_tasks, dependencies):
"""给出一个可行的执行顺序。"""
edges = [(b, a) for a, b in dependencies]
order, ok = topo_kahn(num_tasks, edges)
return order if ok else None
注意事项与常见坑
坑 1:Dijkstra 的「惰性删除」漏写
堆优化 Dijkstra 里,同一个点可能被多次入堆(每次距离变短都入堆一次)。出堆时必须加
if d > dist[u]: continue,否则会用到过期的旧距离,结果偏大。
坑 2:Floyd 的中转点循环必须在最外层
写成
for i: for j: for k:就错了。k必须在最外层,因为它代表「阶段」,即 DP 的阶段维度。顺序写错时很多用例仍然能过(尤其是只有 3、4 个点的图),非常隐蔽。
坑 3:无向图 DFS 忘记跳过父节点
在 Tarjan 求割点桥、以及无向图环检测中,必须区分「指向父节点的边」和「真正的回边」。
直接写
elif v != parent在有重边时会误判,严谨做法是传「父边的编号」而不是父节点。
坑 4:递归 DFS 在深图上栈溢出
一条 个点的链会让 Python 递归超出默认的 1000 层限制。要么改用显式栈,
要么
sys.setrecursionlimit(300000)并配合增大线程栈(threading.stack_size)。
坑 5:把拓扑排序当成唯一解
拓扑序通常有多个。若题目要求「编号小的优先」,必须用最小堆替换队列,否则得到的顺序不满足要求。
坑 6:稠密图上用堆优化 Dijkstra
堆里会塞进 个元素, 时反而不如朴素的 。选算法前先估算 。
坑 7:混淆「环」与「自环」
自环 本身就是环。Kahn 算法中自环会让该点入度永远为 1,最终结果长度不足 ,能被正确检出;
但无向图并查集判环时,自环会让
find(u) == find(u),同样能检出——不要以为要特判。
坑 8:多源 BFS 只入队一个源
把所有源点同时入队、距离一起从 0 开始,才等价于超级源点。分多次单源 BFS 是 ,会超时。
练习题
题 1(基础)连通分量计数
给定 个点和 条无向边,输出连通分量个数和每个点所属分量编号。
<details>
<summary>参考思路</summary>
对每个未访问点做一次 DFS/BFS,计数器加一。复杂度 。见「连通性」一节的 count_components。
</details>
题 2(基础)判断有向图是否有环
给定有向图,判断是否存在环。
<details>
<summary>参考思路</summary>
两种做法:三色标记 DFS(撞到灰色即有环)或 Kahn 拓扑排序(结果长度不足 即有环)。都是 。
</details>
题 3(中等)课程表(LeetCode 207 / 210)
numCourses = 4,prerequisites = [[1,0],[2,0],[3,1],[3,2]],判断能否修完并给出一个顺序。
分步解答:
第 1 步:把先修关系转成有向边。
[a, b] 表示修 a 前先修 b,即边 。得到边集:
第 2 步:统计入度。
| 顶点 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 入度 | 0 | 1 | 1 | 2 |
第 3 步:入度为 0 的点入队。 队列 = [0],结果 = []。
第 4 步:循环出队。
| 轮次 | 出队 | 入度变化 | 入队 | 结果 |
|---|---|---|---|---|
| 1 | 0 | 1→0, 2→0 | 1, 2 | [0] |
| 2 | 1 | 3→1 | — | [0,1] |
| 3 | 2 | 3→0 | 3 | [0,1,2] |
| 4 | 3 | — | — | [0,1,2,3] |
第 5 步:判断。 结果长度 4 = 顶点数 4,无环,可以修完。一个合法顺序是 [0,1,2,3]([0,2,1,3] 同样合法)。
def solve():
n, prereq = 4, [[1, 0], [2, 0], [3, 1], [3, 2]]
edges = [(b, a) for a, b in prereq]
order, ok = topo_kahn(n, edges)
return order if ok else []
复杂度:时间 ,空间 。
题 4(中等)网络延迟时间(LeetCode 743)
有 个网络节点,times[i] = (u, v, w) 表示 的传播时间为 。求从节点 出发,信号传遍所有节点所需的最短时间;不可达返回 。
<details>
<summary>参考思路</summary>
这是有向图单源最短路(边权非负):跑堆优化 Dijkstra 得 dist,答案 = max(dist);若有 INF 则返回 。复杂度 。
</details>
题 5(进阶)判定二分图并输出分组
给定 个点和冲突边,判断能否分成两组,使组内没有冲突边;能则输出两组的具体成员。
<details>
<summary>参考思路</summary>
BFS 黑白染色。图可能不连通,每个分量都要单独起一个起点。染色完成后,
color == 0 的归一组,color == 1 的归另一组。复杂度 。
</details>
题 6(进阶)用 Kruskal 求最小生成森林
给定不连通的无向带权图,求每个连通分量的最小生成树,输出总权值。
<details>
<summary>参考思路</summary>
Kruskal 天然支持:边按权排序后逐个尝试,并查集合并成功的就计入。不要以「选够 条边」为退出条件,
而是遍历完所有边,最后检查 dsu.count 是否为分量数。
</details>
常见问题 FAQ
Q1:什么情况下该用邻接矩阵而不是邻接表?
三个信号:① 很小()且图很稠密;② 需要频繁查询「 和 之间有没有边 / 边权多少」(矩阵 ,表要 );③ 要用 Floyd 算法(它天然需要矩阵)。
其他情况一律用邻接表。
Q2:BFS 真的能求最短路吗?为什么加权图不行?
BFS 的层数等于「经过的边数」。无权图中每一步代价都是 1,所以边数最少 = 代价最小。
加权图里一条边权 100、另一条路径 3 条边各权 1,BFS 会错误地选前者。这时要用 Dijkstra。
Q3:Dijkstra 和 Prim 长得几乎一样,区别在哪?
两者都用优先队列、都做「取最小 + 松弛」。
Dijkstra 的键是「源点到该点的累计距离」(累加),
Prim 的键是「该点到已选集合的单条边权」(不累加)。
一行之差,解决的是完全不同的两个问题。
Q4:什么时候必须用 Tarjan 而不是简单 DFS?
只要问题涉及「哪些点/边是关键的」「哪些点互相可达」,就轮到 Tarjan:
割点、桥、强连通分量、双连通分量、2-SAT。
它们都依赖
dfn/low这两个数组携带的结构信息,普通 DFS 拿不到。
Q5:图中顶点编号不是 0 到 n-1 怎么办?
先做离散化(Coordinate Compression):把所有出现过的顶点收集起来排序,用字典映射成 。
例如字符串顶点
{"A":[..], "B":[..]}映射成{"A":0, "B":1},再套用上面的所有模板。
相关笔记
- 算法-图算法:本篇的算法视角补充,含 Bellman-Ford、SPFA、网络流与并查集进阶
- 数据结构-树与堆:树是图的特例,堆是 Dijkstra 与 Prim 的优先队列基础
- 算法-复杂度分析:、 这些结论的推导基础,以及 P vs NP(哈密顿路径为何难)
- 数据结构-哈希表:稀疏图的邻接表常与哈希表结合存放字符串顶点
- 00-索引:全库笔记导航
- 学习路线图:按阶段的学习顺序建议
参考来源
- OI Wiki 图论部分:https://oi-wiki.org/graph/
- OI Wiki 拓扑排序:https://oi-wiki.org/graph/topo/
- OI Wiki 最短路:https://oi-wiki.org/graph/shortest-path/
- OI Wiki 最小生成树:https://oi-wiki.org/graph/mst/
- OI Wiki 强连通分量:https://oi-wiki.org/graph/scc/
- VisuAlgo 图数据结构可视化:https://visualgo.net/en/graphds
- VisuAlgo 单源最短路可视化:https://visualgo.net/en/sssp
- VisuAlgo 最小生成树可视化:https://visualgo.net/en/mst
- MIT OCW 6.006 Introduction to Algorithms:https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- Python 官方文档 collections.deque:https://docs.python.org/3/library/collections.html#collections.deque
- Python 官方文档 heapq:https://docs.python.org/3/library/heapq.html