6
感谢AC君加精\tiny 感谢AC君加精感谢AC君加精
> UPD 9.28，应评论区大佬建议，增加了关键代码的注释。
本篇文章讲解图论算法，包括最短路、最小生成树、并查集和基础的LCALCALCA
MARKDOWNMARKDOWNMARKDOWN原码5318字，最终展示4000左右。
大家请坐稳，我们马上开始。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
PART 1 最短路算法
最短路算法是图论中最基础的方法，在各大比赛中都有涉及，本篇将会提到4种最短路算法。
一、定义
最短路问题即求一个带权图中两个节点的最短的路径。
二、DIJKSTRADIJKSTRADIJKSTRA算法
1.简介
这是图论中最常用的最短路算法，由荷兰计算机科学家EdsgerW.DijkstraEdsger W. DijkstraEdsgerW.Dijkstra于195619561956年提出，其核心思想是贪心和广度优先搜索。它解决的是单源最短路问题。
2.核心思想
DijkstraDijkstraDijkstra算法的核心在于维护一个 distdistdist 数组， dist[i]dist[i]dist[i] 表示从起点到 iii 号点的最短路。
3.适用范围
非负权图，DijkstraDijkstraDijkstra算法每个点只松弛一次的特性决定了其无法解决负权问题。
4.朴素DIJKSTRADIJKSTRADIJKSTRA算法
* DijkstraDijkstraDijkstra算法将节点分为两类：
1. 已确定节点：已经找到从起点到该节点的最短路径的节点集合。
2. 未确定节点：尚未找到最短路径的节点集合。
* 算法流程：
1. 每次从 “未确定节点” 集合中，选择一个 距离起点最近 的节点。
2. 将其加入 “已确定节点” 集合。
3. 松弛 这个新确定节点的所有邻居。
* 松弛操作（也是该算法最重要的思想）：
检查对于新确定节点 uuu 的每一个邻居 vvv，如果从起点 sss 先到 uuu，再从 uuu 到 vvv 的路径距离，比之前已知的到 vvv 的距离更短，那么就更新 vvv 的距离。
* 核心代码：
* 完整代码：
* 时间复杂度：O(n2+m)O(n^2+m)O(n2+m)（一般写作O(n2)O(n^2)O(n2)）
* 空间复杂度：O(n+m)O(n+m)O(n+m)
5.堆优化DIJKSTRADIJKSTRADIJKSTRA算法
* 区别于朴素做法的枚举每个可能松弛的节点，堆优化算法使用堆找到目前最近（最可能松弛）的节点。
* 代码：
* 时间复杂度：O(mlogn)O(mlogn)O(mlogn)
* 空间复杂度：O(n+m)O(n+m)O(n+m)
* 注意在稠密图中，堆优化算法会退化为O(n2logn),此时应使用朴素算法。\color{red}{注意在稠密图中，堆优化算法会退化为O(n^2logn),此时应使用朴素算法。}注意在稠密图中，堆优化算法会退化为O(n2logn),此时应使用朴素算法。
6.
练习
三、FLOYDFLOYDFLOYD算法
1.简介
FloydFloydFloyd算法是一种基于dpdpdp的思想，是学生们最喜欢的一种基础最短路算法也是最慢的（竞赛中不常用）
2.核心思想
从节点 iii 到节点 jjj 的最短路径，无非有两种可能：
1. 直接从 iii 到 jjj。
2. 从 iii 经过某些中间节点 kkk 再到 jjj。
FloydFloydFloyd算法不断尝试和比较这些可能性，逐步优化最短路径的估计值（这也是该算法较慢的原因）。
3.适用范围
FloydFloydFloyd不适用于存在负权回路的图中。
4.FLOYDFLOYDFLOYD算法实现
* 状态定义：
d[k][i][j]d[k][i][j]d[k][i][j]：表示从节点 iii 到节点 jjj，仅使用 1,2,⋯ ,k1, 2, \cdots, k1,2,⋯,k 号节点作为中间节点的所有可能路径中的最短路径长度。
* 状态转移方程：
对于每一个中间节点 kkk，我们检查对于每一对 (i,j)(i, j)(i,j)，是否存在一条更短的路径：
d[k][i][j]=min(d[k−1][i][j],d[k−1][i][k]+d[k−1][k][j])d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j]) d[k][i][j]=min(d[k−1][i][j],d[k−1][i][k]+d[k−1][k][j])
* 这个方程的含义：
d[k−1][i][j]d[k-1][i][j]d[k−1][i][j]：不使用 kkk 作为中间节点，iii 到 jjj 的最短路径。
d[k−1][i][k]+d[k−1][k][j]d[k-1][i][k] + d[k-1][k][j]d[k−1][i][k]+d[k−1][k][j]：使用 kkk 作为中间节点，路径分解为 iii -> kkk 和 kkk -> jjj 两段，这两段路径只使用前 111 到 k−1k-1k−1 号节点作为中间节点。
* 取这两种情况的最小值。
* 代码（空间优化版）：
* 时间复杂度：O(n3)O(n^3)O(n3)
* 空间复杂度：O(n2)O(n^2)O(n2)
5.
练习
四、BELLMANBELLMANBELLMAN-FORDFORDFORD算法
1.简介
BellmanBellmanBellman-FordFordFord算法是另一种单源最短路算法，价值在于可以解决负权（回路）问题。
2.核心思想
BellmanBellmanBellman-FordFordFord算法的思想非常直接：
最短路径最多经过 n−1n-1n−1 条边。 如果一条从源点 sss 到终点 ttt 的最短路径经过了超过 n−1n-1n−1 条边，那么它必定包含一个环。如果是正环或零环，可以移除它得到更短的路径；如果是负环，则不存在最短路径。
基于这个思想，通过松弛操作对图中的所有边进行 n−1n-1n−1 轮遍历。每一轮遍历都尝试用一条边来更新和优化当前已知的最短距离。经过 n−1n-1n−1 轮后，理论上所有可能的最短路径都已经被找到。这时执行一轮松弛操作，还能有路径被更新，则证明图中存在负权回路。
3.适用范围
BellmanBellmanBellman-FordFordFord算法适用于所有情况
4.BELLMANBELLMANBELLMAN-FORDFORDFORD算法实现
* 初始化：
1. 将dist[s]dist[s]dist[s] 设为 000。
2. 将所有其他节点的 distdistdist 值初始化为 1e91e91e9。
* 进行 n−1n-1n−1 轮松弛：
1. 对每一轮，遍历图中的所有 mmm 条边。
2. 对于每条边 (u,v,w)(u, v, w)(u,v,w)，执行松弛操作：
* 核心代码：
* 如果需要检查负权回路，再额外进行一次对所有边的遍历（即第 nnn 轮松弛），如果发现任何一条边 还能进行松弛操作，就可以得出结论：图中存在从源点 sss 可达的负权回路。
* 注意：每一轮松弛的顺序可能会影响效率，但不影响最终结果的正确性。\color{red}{注意：每一轮松弛的顺序可能会影响效率，但不影响最终结果的正确性。}注意：每一轮松弛的顺序可能会影响效率，但不影响最终结果的正确性。
* 完整代码：
* 时间复杂度：O(nm)O(nm)O(nm)
* 空间复杂度：O(n+m)O(n+m)O(n+m)
5.
练习
五、SPFASPFASPFA算法
1.简介
SPFA（ShortestPathFasterAlgorithm）SPFA（Shortest Path Faster Algorithm）SPFA（ShortestPathFasterAlgorithm）是对于BellmanBellmanBellman-FordFordFord的队列优化版本，在随机图中时间更优，但容易被卡。
2.核心思想
我们发现，BellmanBellmanBellman-FordFordFord算法中，并不是每一次松弛操作都会有效，只有那些在前一轮松弛中成功更新了最短路径值的点，才有可能引领下一次有效的松弛。
SPFASPFASPFA 对此进行了关键优化：
使用一个队列来维护有可能引起松弛操作的点。只有当某个点 uuu 的最短距离 dist[u]dist[u]dist[u] 被更新变小了，才说明它的出边有可能使其邻居 vvv 的 dist[v]dist[v]dist[v] 也变小。这时，我们才将 uuu 放入队列，等待后续用它来松弛它的邻居。
这个过程避免了 BellmanBellmanBellman-FordFordFord中大量无用的松弛尝试，使其在平均情况下的时间复杂度远优于BellmanBellmanBellman-FordFordFord。
3.适用范围
SPFASPFASPFA适用于所有情况
4.SPFASPFASPFA算法实现
* 初始化：
1. 创建 distdistdist 数组，dist[s]=0dist[s] = 0dist[s]=0，其余为 INFINFINF。
2. 创建一个队列 qqq，将源点 sss 入队。
* 创建一个 in_queuein\_queuein_queue数组，标记节点是否已在队列中，防止重复入队。初始时，in_queue[s]=Truein\_queue[s] = Truein_queue[s]=True。
* (可选，用于检测负环) 创建一个 countcountcount 数组，记录每个节点的入队次数，初始为 000。
* 主循环：当队列不为空时
1. 从队首弹出一个节点 uuu，并标记 in_queue[u]=Falsein\_queue[u] = Falsein_queue[u]=False。
2. 遍历 uuu 的所有出边 。
3. 尝试对边 (u,v)(u, v)(u,v) 进行松弛操作。
* 代码：
* 平均时间复杂度：O(km)O(km)O(km) 其中kkk是个很小的常数
* 最坏时间复杂度：O(nm)O(nm)O(nm) 在一些特殊数据，比如网格图中，会退化为BellmanBellmanBellman-FordFordFord
* 空间复杂度：O(n+m)O(n+m)O(n+m)
六、小结
算法 DijkstraDijkstraDijkstra BellmanBellmanBellman-FordFordFord SPFASPFASPFA FloydFloydFloyd 类型 单源最短路径 单源最短路径 单源最短路径 多源最短路径 策略 贪心 动态规划 队列优化 动态规划 时间复杂度 O(mlogn)O(m log n)O(mlogn) O(nm)O(nm)O(nm) O(km)O(km)O(km) O(n3)O(n^3)O(n3) 空间复杂度 O(n+m)O(n+m)O(n+m) O(n+m)O(n+m)O(n+m) O(n+m)O(n+m)O(n+m)
O(n+m)O(n+m)O(n+m) 负权边 ❌ ✅ ✅ ✅ 负环检测 ❌ ✅ ✅ ❌ 适用场景 非负权图 负权图 随机图 n<500n<500n<500 最佳情况 非负权图 负权图 随机图 n<500n<500n<500 最坏情况 无，均可用对应优化 稠密图 特殊图，例如网格图 小数据，大规模查询 实现难度 中等 中等 较难 简单
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
PART 2 并查集
并查集是图论中一种基础算法，是最小生成树等算法的基础，本篇将会提到3种并查集。
一、定义
并查集是一种用于管理元素分组情况的数据结构。
二、朴素版
1.简介
并查集高效地支持以下两种操作：
* 合并：将两个元素所在的集合合并为一个集合。
* 查找：查询某个元素是否在同一集合。
2.核心思想
并查集的核心思想在于用多棵树来表示集合。森林中的每一棵树代表一个集合，树中的每个节点对应一个元素，树的根节点就是这个集合的“代表”。
3.算法流程
* 初始化：
一开始，我们拥有nnn个元素。通常我们用一个数组 parentparentparent 来表示每个元素的父节点。
初始化时，每个元素都是自己的父亲，即每个元素自成一个集合，自己是自己那棵树的根。
* 查找
即查找元素 xxx 所在集合的根节点。方法很简单：不断地通过 parentparentparent 数组向上查找，直到找到那个父节点指向自己的元素（即 parent[x]=xparent[x] = xparent[x]=x），它就是根节点。
* 合并
即将元素 xxx 和元素 yyy 所在的两个集合合并成一个集合，主要有两个步骤：
1. 找到 xxx 的根节点 rootx=find(x)rootx = find(x)rootx=find(x) 和 yyy 的根节点 rooty=find(y)rooty = find(y)rooty=find(y)。
2. 如果 rootx=rootyrootx=rootyrootx=rooty，说明它们本来就在同一个集合里，无需合并。否则将其中一棵树挂到另一棵树的根节点下面。即让 parent[rootx]=rootyparent[rootx] = rootyparent[rootx]=rooty。
4.代码实现
* 单次操作时间复杂度：最坏O(n)O(n)O(n)
* 空间复杂度：O(n)O(n)O(n)
5.
练习
三、按秩合并
1.简介
在朴素算法中，我们不难发现，在特殊数据下，树会退化为一条链，时间会退化为O(n)O(n)O(n)，无法满足需求，于是按秩合并应运而生。
2.核心思想
我们使用一个额外的数组 rankrankrank 来记录每个根节点所代表的树的“高度”的估计值（这就是秩）。
初始时，每个元素都是根节点，自己构成一棵高度为 000 的树，所以 rank[i]=0rank[i] = 0rank[i]=0。
注意：我们只维护根节点的rank值，非根节点的rank值没有意义。\color{red}{注意：我们只维护根节点的 rank 值，非根节点的rank值没有意义。}注意：我们只维护根节点的rank值，非根节点的rank值没有意义。
3.算法流程
* 在合并两个根节点 rootxrootxrootx 和 rootyrootyrooty 时：
1. 比较它们的秩（rank[rootx]rank[rootx]rank[rootx] 和 rank[rooty]rank[rooty]rank[rooty]）。
2. 将秩较小的树挂到秩较大的树下。
* 注意：如果两棵树的秩相等：任意选择一方作为新的根，并将新根的秩加 111。
* 为什么相等时要加 111？
想象两颗高度均为 hhh 的树。当它们合并时，新树的高度至少为 h+1h+1h+1（将一颗树挂到另一颗的根节点下，整个树的高度必然增加 111）。
4.代码实现
这段代码请由各位自行完成(doge)。
5.
还是这道
四、路径压缩
1.简介
路径压缩是并查集中一种非常重要的优化技术，它在查找中实施，可以显著提高并查集的效率。
2.核心思想&算法流程
朴素算法通过递归查找根节点，而路径压缩指的是在递归返回的过程中，将路径上每个节点的父节点直接设置为根节点，这样，整个路径被"压缩"了，所有节点都直接指向根。
3.代码实现
这是朴素的findfindfind
这是路径压缩的findfindfind
完整代码：
5.
还是这道
6.复杂度分析
* 时间复杂度：并查集的时间复杂度分析比较特殊，它不是一个简单的 O(logn)O(log n)O(logn) 或 O(n)O(n)O(n)，路径压缩的时间复杂度是由一个增长极其缓慢的函数——反阿克曼函数 α(n)α(n)α(n) 来描述。至于这个函数有多缓慢呢？在n≤265536n ≤ 2^{65536}n≤265536 时，α(n)≤5α(n) ≤ 5α(n)≤5。所以路径压缩并查集的单次操作一般认为是O(1)O(1)O(1)的。
* 空间复杂度：O(n)O(n)O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
PART 3 最小生成树
最小生成树是图论中一种基础方法，考试中会出现很多变体，本篇将会提到两种最小生成树算法。
一、定义
生成树是一个无向连通图的子图。它必须包含原图的所有顶点，但只包含足够形成一棵树的边，并满足以下三个条件：
* 是连通图：所有顶点都连接在一起。
* 无环：图中不存在任何环路。
* 边数 = 顶点数 - 111。
最小生成树 就是在一个带权连通无向图中，所有可能的生成树里，边的权重之和最小的那一棵（或那几棵）。
二、KRUSKALKRUSKALKRUSKAL算法
1.简介
KeuskalKeuskalKeuskal算法是基于边的一种最小生成树算法，也是竞赛中最常用的一种。
2.核心思想
从小到大选择不会形成环的边，直到连接所有顶点。
3.算法流程
* 排序：将图中所有的边按权重从小到大排序。
* 初始化：创建一个空的集合用于存放最小生成树的边。
* 遍历：按权重从小到大遍历每条边：
* 如果当前边连接的两个顶点不在集合的同一个连通分量中（即加入这条边不会形成环），则将这条边加入集合。
* 如果会形成环，则跳过。
* 终止条件：当集合中的边数等于顶点数减111时，算法结束。
* 如何判断是否成环？
我们通常使用并查集来高效地判断两个顶点是否属于同一个集合以及把两个点的集合合并。
4.代码实现
* 时间复杂度：O(mlogm)O(mlogm)O(mlogm)
* 空间复杂度：O(n+m)O(n+m)O(n+m)
5.
练习
三、PRIMPRIMPRIM算法
1.简介
不同于KruskalKruskalKruskal算法，PrimPrimPrim算法是基于点的一种最小生成树算法，比较慢。
2.核心思想
从一个顶点开始，每次选择与当前树相连的权重最小的边，并扩展这棵树。
3.算法流程
* 初始化：
1. 随机选择一个顶点作为起点，加入最小生成树集合。
2. 维护一个数组 keykeykey，记录每个顶点到当前最小生成树的最小权重，初始值为无穷大（起点为000）。
3. 维护一个数组 parentparentparent，记录每个顶点是由哪条边连接进来的。
* 循环扩展：
1. 从未被选择的顶点中，选择一个 keykeykey 值最小的顶点 uuu，将其加入树中。
2. 遍历顶点 uuu 的所有邻接顶点 vvv，如果边 (u,v)(u,v)(u,v) 的权重小于 vvv 当前的 keykeykey 值，则更新 vvv 的 keykeykey 值为这个权重，并记录 parent[v]=uparent[v] = uparent[v]=u。
* 终止条件：所有顶点都被加入树中后，算法结束。parentparentparent 数组就定义了最小生成树的结构。
4.代码实现
* 时间复杂度：O(mlogn)O(mlogn)O(mlogn)（不用优先队列的朴素版是O(n2)O(n^2)O(n2)）
* 空间复杂度：O(n+m)O(n+m)O(n+m)
四、小结
算法 KruskalKruskalKruskal PrimPrimPrim 对象 边 点 时间复杂度 O(mlogm)O(m log m)O(mlogm) O(mlogn)O(mlogn)O(mlogn) 空间复杂度 O(n+m)O(n+m)O(n+m) O(n+m)O(n+m)O(n+m) 适用场景 稀疏图 稠密图 数据结构 并查集 优先队列
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
PART 4 LCALCALCA—最近公共祖先
这是一个在树中非常常见且重要的问题，是许多其他高级问题的基础。
一、定义
字面意思对于一棵有根树中的两个节点 ppp 和 qqq，它们的最近公共祖先被定义为同时是 ppp 和 qqq 的祖先的节点中，深度最大的那个节点。
二、倍增法求LCALCALCA（暴力解法这里就跳过了）
1.简介
这是求LCALCALCA最常用的方法，用倍增的思想来向上“跳”。
2.核心思想
倍增法的主要思想是：任何整数都可以用二进制表示，那么从任何一个节点到其祖先的路径长度，也可以拆分为多个222的幂次方步长。我们预先计算好每个节点向上跳 2k2^k2k 步会到达哪里，查询时就能快速向上“跳”，而不需要一步一步走。
3.算法流程
* 预处理：
depth[i]depth[i]depth[i]：记录每个节点 iii 的深度。
up[i][j]up[i][j]up[i][j]：这是核心的倍增表。它表示从节点 iii 开始，向上跳 2j2^j2j 步后，所到达的祖先节点。
这两个数组均可在dfsdfsdfs中通过递推实现。
depthdepthdepth就不说了，我们重点讲解upupup，注意到从 iii 点跳 2j2^j2j 步 === 先从 iii 点跳 2j−12^{j-1}2j−1 步到一个中间节点 midmidmid，再从 midmidmid 节点跳 2j−12^{j-1}2j−1 步，由此，up[i][j]=up[up[i][j−1]][j−1]up[i][j] = up[ up[i][j-1] ][j-1]up[i][j]=up[up[i][j−1]][j−1]，这样，我们可以用已经计算好的 第j−1j-1j−1 层的信息，来构建第 jjj 层的信息。
* 查询
1. 深度对齐：首先，确保两个节点 uuu 和 vvv 处于同一深度。假设 depth[u]>depth[v]depth[u] > depth[v]depth[u]>depth[v]，我们需要把 uuu 往上提。计算深度差 d=depth[u]−depth[v]d = depth[u] - depth[v]d=depth[u]−depth[v]。将深度差 ddd 看作一个二进制数，利用倍增表快速提升 uuu。
2. 检查是否同一节点： 如果此时 u=vu =vu=v，那么这个点就是LCALCALCA，直接返回。
3. 同步攀升：如果深度对齐后 uuu 和 vvv 不同，则让它们一起向上跳，从最大的步数 k=20k = 20k=20 开始尝试，向下递减，如果 up[u][k]!=up[v][k]up[u][k] != up[v][k]up[u][k]!=up[v][k]，说明这个祖先还不是公共的（还没越过LCALCALCA），我们就可以安全地将 uuu 和 vvv 同时向上跳 2k2^k2k 步，否则说明越过了LCALCALCA，不跳。
4. 经过第333步后，uuu 和 vvv 会停留在LCALCALCA的正下方的两个直接子节点上。因此，uuu 和 vvv 此时的父节点就是LCALCALCA，即 up[u][0]up[u][0]up[u][0]。
4.代码实现
* 时间复杂度：O(nlogn)O(nlogn)O(nlogn)
* 空间复杂度：O(nlogn)O(nlogn)O(nlogn)
OK啊，终于杀青了！打字不易，点个赞吧。
特别鸣谢@AAA混泥土批发PPL哥、@复仇者_帅童对于FLOYDFLOYDFLOYD算法的指正、@沈思邈对于一些细节的建议！
屏幕前的家人们觉得我能长出身体吗？
有帮助，赞一个