图论算法笔记

First Post:

Last Update:

Word Count:
2k

Read Time:
6 min

本文总结图论中的几类经典算法，并补充一些容易混淆的细节。文中默认讨论的是带权图；若无特殊说明，图可以看作无向图或有向图中对应问题的常见版本。

最小生成树

最小生成树（Minimum Spanning Tree, MST）问题只适用于连通无向图：在包含全部顶点的前提下，选出若干条边，使总权值之和最小，且不形成环。

Prim

Prim 是面向点的贪心算法，通常更适合稠密图。它的核心思想是：每次从“已经加入生成树的点集”与“尚未加入的点集”之间，选出一条权值最小的横切边，并将新顶点加入生成树。

流程

  1. 将所有顶点划分为两部分：已加入生成树的集合 ，以及尚未加入的集合 。
  2. 任意选择一个起点，将其加入 。
  3. 在所有连接 和 的边中，选择权值最小的一条边。
  4. 将这条边对应的新顶点加入 ，并把该边加入最小生成树。
  5. 重复第 3、4 步，直到所有顶点都被加入生成树。

复杂度分析

  • 若使用邻接矩阵实现，并通过线性扫描寻找当前最近点，则时间复杂度为 ，空间复杂度为 。
  • 若使用邻接表加最小堆实现，则时间复杂度可优化为 。

因此，Prim 常见的经验结论是：稠密图更适合使用朴素 Prim。

Kruskal

Kruskal 是面向边的贪心算法，通常更适合稀疏图。它的核心思想是：按照边权从小到大依次尝试加入边，只要该边不会与已选边形成环，就将其加入生成树。判断是否成环时，通常使用并查集。

流程

  1. 将图中所有边按权值从小到大排序。
  2. 初始化并查集，使每个顶点各自属于一个独立集合。
  3. 依次遍历排序后的每条边 ：
    • 如果 和 已属于同一集合，说明加入该边会形成环，跳过；
    • 否则，将该边加入最小生成树，并合并两个集合。
  4. 当最小生成树中已有 条边时，算法结束。

复杂度分析

  • 对 条边排序的时间复杂度为 。
  • 并查集的 find 和 union 操作均摊复杂度为 ，实际中近似看作常数。
  • 因此，Kruskal 的总时间复杂度为 ，空间复杂度为 。

对于简单图，，因此也常将其写作 。经验上，稀疏图更适合使用 Kruskal。

最短路径

单源最短路径

Dijkstra

Dijkstra 用于求解单源最短路径，但不能处理含负权边的图。它同样基于贪心：每次确定当前距离源点最近、且尚未确定最短路的点，并用该点去更新其他点的距离。

其正确性依赖于一个关键前提：图中不存在负权边。一旦存在负权边，已经“确定”的最短距离后续仍可能被进一步缩短，算法就会失效。

流程
  1. 初始化距离数组 dist，令源点距离为 ，其余点为无穷大。
  2. 将源点加入优先队列（最小堆）。
  3. 当优先队列非空时，重复以下操作：
    • 取出当前距离最小的点 ；
    • 如果该状态是过期状态（即弹出的距离大于当前 dist[u]），则跳过；
    • 否则，遍历从 出发的所有边，尝试进行松弛：
      • 若 ，则更新 dist[v]，并将新状态加入优先队列。
  4. 队列为空后，dist 即为源点到其余各点的最短距离。
复杂度分析
  • 朴素实现（邻接矩阵 + 线性选点）的时间复杂度为 。
  • 使用邻接表 + 最小堆优化后，时间复杂度为 ，在稀疏图中通常写作 。
  • 空间复杂度通常为 ；若只统计算法附加数据结构，则为 ，再加上堆在最坏情况下可能达到 。

SPFA

SPFA（Shortest Path Faster Algorithm）本质上是 Bellman-Ford 的队列优化实现。两者使用的是同一类“反复松弛边”的思想：如果一条路径允许经过更多边，那么最短距离就可能进一步变小。

从动态规划角度看，可以定义：

从源点到，最多经过条边时的最短距离

则有转移关系：

进一步可以使用滚动更新来压缩dp数组，节约k维度的空间，对于不同轮次数据干扰的问题，对于SPFA来说反而可以加快收敛。但是如果要求限制步数；此时通常需要使用备份数组，避免同一轮中的状态相互污染。

由于一个不含环的最短路径最多经过 条边，因此在不存在负权回路时，经过 轮松弛后结果一定收敛。朴素的 Bellman-Ford 会在每一轮遍历全部边，时间复杂度为 。实践中这种写法使用较少，更常见的是 SPFA：只把“刚刚被更新、后续仍可能继续产生贡献”的点加入队列继续处理。

流程
  1. 初始化距离数组，源点距离设为 ，其余点设为无穷大。
  2. 将源点加入队列，并标记其当前在队列中。
  3. 当队列非空时，重复以下操作：
    • 取出队首节点 ，并取消其“在队列中”标记；
    • 遍历从 出发的所有边 ；
    • 如果 ，则更新 ；
      • 若 当前不在队列中，则将其加入队列。
负权回路判断

SPFA 也可以用于检测负权回路。常见做法是统计每个点被成功松弛后入队的次数：

  • 若某个点入队次数达到 次，则说明存在从源点可达的负权回路。

这里的本质原因是：若不存在负权回路，则任意最短路至多包含 条边，一个点最多入队次数为 。

复杂度分析
  • 朴素 Bellman-Ford 每轮都扫描全部边，时间复杂度为 ，空间复杂度为 。
  • 但 SPFA 的最坏时间复杂度为 。
  • 空间复杂度为 ；若图存储本身不计入，则附加空间为 。

多源最短路径

Floyd-Warshall

Floyd-Warshall 用于求解任意两点之间的最短路径，因此属于多源最短路径算法。它可以处理负权边，但若存在负权回路，则最短路径没有意义。

算法使用动态规划思想。定义：

只允许经过节点集合作为中转点时，的最短距离

转移时只需要考虑两种情况：

  1. 最短路不经过编号为 的点；
  2. 最短路经过编号为 的点作为最后新增的中转点。

于是有：

由于第 轮只依赖第 轮结果，因此可以直接原地滚动更新，最终写成经典的三重循环：

1
2
3
4
for (int k = 1; k <= n; ++k)
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
负权回路判断

如果算法结束后存在某个点满足 ，则说明图中存在负权回路。

复杂度分析
  • 时间复杂度为 。
  • 空间复杂度为 。

因此，Floyd-Warshall 更适合点数较小、但需要一次性求出所有点对最短路的场景。

总结

算法 适用图的大小 边的权值为负数 检测负权回路 有限节点最短路径 源点数 时间复杂度
Dijkstra 朴素版 稠密图 不可以 不可以 不可以 单源 O(V^2)
Dijkstra 堆优化版 稀疏图 不可以 不可以 不可以 单源 O(ElogE)
Bellman-Ford 稠密图 可以 可以 可以 单源 O(V * E)
SPFA 稀疏图 可以 可以 可以 单源 O(K * V) K 为不定值，取决于图的稠密度
Floyd 稠密图 可以 可以 不可以 多源 O(V^3)

Reference

≡