1 / 4概念
Graph Algorithms
图算法把“点与点之间怎么走”变成可计算的顺序:先定义状态和边权,再选遍历、最短路或生成树。判断标准不是“算法名字熟不熟”,而是图是否有负权、是否稠密、要单源还是全源、要不要生成树。
1 概念
1.1 一句话定义
图算法是在顶点集合 V 和边集合 E 上,按某种不变量逐步扩展已知信息的算法。最短路维护“从源点到每个点的最小代价”,最小生成树维护“连接所有点的最小总边权”,拓扑排序维护“所有边都从前往后”的线性序。
1.2 它解决什么问题
- 导航与网络:路由、地图、社交关系、依赖解析都建模成图。
- 依赖顺序:构建系统、包管理、任务调度需要拓扑排序发现环。
- 成本最小化:网络布线、聚类、近似算法需要最小生成树。
- 状态搜索:游戏、规划、拼图把状态当点、动作当边,用 BFS/A* 找最短动作序列。
没有图模型,这些问题只能写成针对具体场景的嵌套循环,复用性和正确性都不可控。
1.3 不属于本页的内容
| 主题 | 去哪 |
|---|---|
| 邻接矩阵、邻接表、CSR、并查集 | Graph Structures |
| 渐进记号、递归式、摊还分析 | Complexity Analysis |
| 排序与二分 | Sorting & Searching |
| 堆与优先队列的实现 | Trees & Heaps |
| NP 完全性与不可解性 | Computational Complexity |
1.4 关键术语
| 术语 | 含义 | 容易混淆的点 |
|---|---|---|
| 有向图 / 无向图 | 边是否有方向 | 无向边通常存两条有向边 |
| 权重 | 边上的代价,可为负 | 负权不等于负环 |
| 负环 | 总权为负的环 | 有负环时最短路无下界 |
| 单源 / 全源 | 一个起点 / 所有点对 | 全源可由多次单源得到 |
| 松弛 | 用 dist[u] + w 更新 dist[v] | 松弛顺序决定算法正确性 |
| DAG | 有向无环图 | DAG 上最短路可带负权 |
| 生成树 | 连接所有点的无环子图 | 最小生成树不保证最短路 |
| 割 | 把点集分成两部分的边集合 | 割边不一定唯一 |
| 启发式 | 对剩余代价的估计 | 可采纳不等于一致 |
| 稠密 / 稀疏 | E 接近 V² / E 接近 V | 选择矩阵还是邻接表 |
2 机制
2.1 心智模型
把所有算法看成同一个循环:维护一个“已确定”集合,反复从边界取一个点,用它松弛邻居。BFS 的边界是队列,Dijkstra 的边界是优先队列,Bellman-Ford 的边界是“本轮所有边”,Floyd 的边界是“允许经过的中间点集合”。区别只在取点顺序和是否允许重复松弛。
2.2 机制拆解
- BFS:从源点按层扩展,第一次到达某点就是最少边数。只适用于无权或边权全相等的图。
- DFS:沿一条路走到底再回溯,用颜色标记白/灰/黑;灰边出现即发现环。DFS 的完成顺序反转是拓扑序。
- Dijkstra:每次取出当前距离最小的未确定点,认为它的距离已经最终确定。要求所有边权非负;否则一个已确定的点可能被后来的负边改进。
- Bellman-Ford:对所有边做 V-1 轮松弛;第 V 轮还能松弛说明存在从源点可达的负环。
- Floyd-Warshall:
dp[k][i][j]表示只允许经过前 k 个点时的最短路;滚动掉 k 维后是三重循环。能处理负边,负环表现为某个dist[i][i] < 0。 - A*:优先队列按
f = g + h取点,h是对到终点的剩余代价估计。h可采纳(不高估)才保证最优;一致(三角不等式)才保证每个点最多扩展一次。 - Kruskal:按边权升序取边,用并查集判断是否成环;不成环就加入。适合稀疏图。
- Prim:从一个点出发,每次取连接“树内”和“树外”的最小边;适合稠密图。
- 拓扑排序:Kahn 算法反复取入度为 0 的点;若最后还有点未输出,说明有环。
2.3 完整枚举
| 算法 | 解决的问题 | 图约束 | 时间复杂度 | 空间 | 输出 |
|---|---|---|---|---|---|
| BFS | 无权最短路、连通分量 | 任意图 | O(V + E) | O(V) | 距离 / 父节点 |
| DFS | 连通性、环检测、拓扑序 | 任意图 | O(V + E) | O(V) | 时间戳 / 完成序 |
| Dijkstra | 单源最短路 | 非负边权 | O((V + E) log V) 二叉堆 | O(V + E) | 距离 / 父节点 |
| Bellman-Ford | 单源最短路、负环检测 | 可有负边 | O(VE) | O(V) | 距离 / 负环标记 |
| Floyd-Warshall | 全源最短路 | 可有负边,无负环 | O(V³) | O(V²) | 距离矩阵 |
| A* | 单源到单目标最短路 | 有可采纳启发式 | 显式图 O(E) 量级,隐式状态最坏指数 | O(V) | 路径 |
| Kruskal | 最小生成树 | 无向连通图 | O(E log E) | O(V + E) | 边集合 |
| Prim | 最小生成树 | 无向连通图 | O(E log V) 二叉堆,稠密 O(V²) | O(V + E) | 边集合 |
| Kahn 拓扑排序 | DAG 线性序 | 有向无环图 | O(V + E) | O(V) | 顶点序 |
补充:DAG 上的单源最短路可以按拓扑序松弛一次,O(V + E),且允许负边;全源最短路在稀疏图上可用 Johnson 算法(先 Bellman-Ford 重赋权,再跑 V 次 Dijkstra),O(VE + V² log V)。
2.4 关键数字与复杂度
| 指标 | 量级 | 说明 |
|---|---|---|
| BFS/DFS | O(V + E) | 每条边最多看两次(无向) |
| Dijkstra 二叉堆 | O((V + E) log V) | 每次 push/pop 是 log V |
| Bellman-Ford | O(VE) | V-1 轮,每轮扫全部边 |
| Floyd | O(V³) | V=1000 时约 10⁹ 次操作,偏大 |
| Kruskal | O(E log E) | 瓶颈在排序,不在并查集 |
| Prim 稠密 | O(V²) | 邻接矩阵 + 线性找最小 |
| 并查集 | 近似 O(α(V)) | 路径压缩 + 按秩合并 |
| 拓扑排序 | O(V + E) | 每个点入队/出队一次 |
3 实践
3.1 最小示例
# Dijkstra:非负边权,二叉堆;dist 是最终答案,prev 用来还原路径。
DIJKSTRA(adj, s):
dist[*] = +∞; prev[*] = NIL; dist[s] = 0
pq = MIN_HEAP((0, s))
while pq not empty:
(d, u) = pq.pop_min()
if d > dist[u]: continue # 过期条目,跳过
for (v, w) in adj[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
pq.push((dist[v], v))
return dist, prev
# BFS:无权图的最少边数;dist=-1 表示未访问。
BFS(adj, s):
dist[*] = -1; dist[s] = 0; q = QUEUE([s])
while q not empty:
u = q.pop_front()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.push_back(v)
return dist
3.2 常用操作与参数
| 操作 | 做法 | 说明 |
|---|---|---|
| 建图 | 邻接表 / 邻接矩阵 / CSR | 稀疏用表,稠密用矩阵 |
| 单源无权 | BFS | 队列,O(V+E) |
| 单源非负 | Dijkstra | 优先队列;跳过过期条目 |
| 单源有负边 | Bellman-Ford | V-1 轮;第 V 轮检测负环 |
| 全源 | Floyd / Johnson | 稠密 Floyd,稀疏 Johnson |
| 最小生成树 | Kruskal / Prim | 稀疏 Kruskal,稠密 Prim |
| 依赖排序 | Kahn / DFS | 有环时返回剩余点作为证据 |
| 启发式搜索 | A* | h 可采纳且一致;记录 closed 集合 |
3.3 标准流程
- 明确图类型:有向/无向、加权/无权、是否有负权、是否 DAG。
- 选表示:先看 E 与 V² 的关系,再决定邻接表、矩阵或 CSR。
- 明确输出:只要距离、要路径、要生成树,还是要检测负环/环。
- 选算法;写下不变量(已确定集合、松弛条件、优先队列含义)。
- 处理边界:空图、单点、不连通、平行边、自环、权重溢出。
- 用暴力算法或小图对拍,再上大规模数据;不要只测随机图。
3.4 与相邻技术的组合
- 图结构:算法复杂度的一半由表示决定;CSR 适合静态大图,邻接表适合动态图。
- 堆:Dijkstra/Prim/A* 都依赖优先队列;堆的实现直接决定常数。
- 并查集:Kruskal 的环检测;也用于无向图连通性和动态连通性。
- 排序:Kruskal 先排序;拓扑排序可用入度队列或 DFS 完成序。
- 复杂度分析:同一个算法在稠密/稀疏图上的最优实现不同,必须带 V/E 一起说。
3.5 选型维度
| 维度 | 取值 | 影响 |
|---|---|---|
| 边权 | 无权 / 非负 / 可负 | BFS / Dijkstra / Bellman-Ford |
| 源点 | 单源 / 全源 | Dijkstra / Floyd 或 Johnson |
| 图密度 | 稀疏 / 稠密 | 邻接表 / 矩阵;Kruskal / Prim |
| 输出 | 距离 / 路径 / 生成树 / 拓扑序 | 决定算法与额外数组 |
| 负环 | 有 / 无 / 未知 | 必须 Bellman-Ford 或 Floyd 检测 |
| 状态空间 | 显式图 / 隐式搜索 | A* 的启发式是否值得 |
3.6 决策规则
- 无权最短路:BFS,不要用 Dijkstra 增加 log 因子。
- 非负加权单源:Dijkstra;稀疏图用二叉堆,稠密图可用 O(V²) 数组实现。
- 有负边单源:Bellman-Ford;先检测负环,再谈距离。
- 全源且 V 不大:Floyd;V 大且稀疏:Johnson 或多次 Dijkstra(非负)。
- DAG 最短路:拓扑序 + 一次松弛,允许负边。
- 最小生成树:稀疏 Kruskal,稠密 Prim;两者都基于割/环性质。
- 只要拓扑序:Kahn 更容易报告环,DFS 更适合顺带做其他后序处理。
3.7 替代方案对比
| 方案 | 优势 | 代价 | 适用 |
|---|---|---|---|
| BFS | 线性、实现简单 | 只处理无权 | 迷宫、社交跳数 |
| Dijkstra | 非负图最优、实践快 | 负边失效、需要堆 | 路由、地图 |
| Bellman-Ford | 支持负边、能检负环 | O(VE) 慢 | 金融套利、含负边图 |
| Floyd | 全源、代码短 | O(V³)、O(V²) 空间 | 小图、传递闭包 |
| A* | 有启发式时显著剪枝 | 启发式设计难、最坏指数 | 游戏、路径规划 |
| Kruskal | 稀疏图快、易并行排序 | 需要并查集、稠密图排序贵 | 网络布线 |
| Prim | 稠密图 O(V²) 友好 | 稀疏图不如 Kruskal | 密集网络 |
| 拓扑排序 | 线性、能发现环 | 只适用于 DAG | 构建、依赖解析 |
3.8 何时不该用
- 图有负边却用 Dijkstra:结果可能错,且不会报错;必须换 Bellman-Ford。
- 无权图用 Bellman-Ford/Floyd:复杂度白白放大。
- 只求连通性却跑最短路:BFS/DFS 就够。
- 隐式状态空间没有可采纳启发式却用 A*:可能退化成全图搜索。
- 图会频繁增删边却用 CSR:静态结构每次重建代价高,改用邻接表。
4 边界
4.1 典型故障
| 症状 | 根因 | 处理 |
|---|---|---|
| Dijkstra 结果比真实最短路大 | 图里有负边,已确定点被错误固定 | 改 Bellman-Ford 或 Johnson |
| BFS 算出的“最短路”权重不是最小 | 边权不等却按层数计算 | 改 Dijkstra / 0-1 BFS |
| A* 找到的路径不是最优 | 启发式高估(不可采纳) | 换可采纳且一致的 h |
| 拓扑排序输出少几个点 | 图中有环,Kahn 无法入队 | 输出剩余点定位环,或先做环检测 |
| 最小生成树少连通一块 | 图不连通,算法只得到森林 | 明确要森林还是补虚拟边 |
| Floyd 出现负的对角线 | 存在负环 | 报告负环,最短路无定义 |
| 大权值相加溢出 | 32 位整数不够 | 用 64 位或饱和加法 |
| Dijkstra 变慢且结果抖动 | 优先队列里有过期条目未跳过 | if d > dist[u] continue |
| DFS 在深图上崩溃 | 递归深度超过栈 | 改显式栈迭代 |
4.2 反模式
| 做法 | 后果 | 替代 |
|---|---|---|
| 用 Dijkstra 处理负权“试试看” | 静默给出错误答案 | 先判断边权符号 |
| 每次查询都重建全图 | O(VE) 变成 O(QVE) | 缓存图结构或增量算法 |
| 用 Floyd 处理百万点图 | 内存和时间都爆 | 稀疏图用 Johnson / 多次 Dijkstra |
| 忽略平行边和自环 | 距离或环检测错误 | 建图时去重/保留最小边 |
| 只测随机图 | 对抗结构(链、星、负环)漏测 | 加链、星、环、二部图用例 |
4.3 可观测信号
距离数组是否还有 +∞、松弛次数、优先队列大小、负环检测返回值、拓扑排序剩余点数。工程上还要看单次查询的 P99、图规模 V/E、内存占用和边权分布。
4.4 安全 / 性能 / 一致性边界
- 正确性:Dijkstra 的非负边权前提不能省;A* 的可采纳性不能靠“感觉”。
- 性能:稠密图用邻接矩阵 + O(V²) Prim 可能比堆更快;不要只看渐进阶。
- 一致性:负环存在时“最短路”没有有限答案,必须显式报告,不能返回一个数。
- 资源:Floyd 的 O(V²) 空间在 V 较大时先爆内存;CSR 适合静态大图但不利于频繁改边。