2. Kruskal 算法
# 2. Kruskal 算法
与 Prim 算法从一个顶点开始扩展最小生成树的方式不同，Kruskal（克鲁斯卡尔）算法采用按边的权值递增次序选择合适的边来构造最小生成树的方法。
**考点提及** ▶ Kruskal 算法构造最小生成树的实例（2015、2018、2020）
初始时，图 $T = \{V, \{\}\}$ 包含全部 $n$ 个顶点，但不含任何边，每个顶点自成一个连通分量。然后按照边的权值从小到大的顺序，依次考察各条边：如果当前边连接的两个顶点属于 $T$ 中不
<!-- page: 240 -->
2027年数据结构考研复习指导
同的连通分量（可通过并查集判断），则将该边加入 $T$；否则，舍弃此边，继续考察下一条权值最小的边。重复这一过程，直到所有顶点都属于同一个连通分量，此时得到的 $T$ 即为最小生成树。图6.16展示了Kruskal算法构造最小生成树的过程。
Kruskal算法步骤如下：
假设 $G = (V, E)$ 是连通图，其最小生成树 $T = (U, E_T)$，$E_T$ 是 $T$ 中的边集合。
初始化：$U = V, E_T = \emptyset$。即每个顶点构成一棵独立的树，$T$ 此时是一个仅含 $|\mathcal{V}|$ 个顶点的森林。
循环（重复，直至 $T$ 成为一棵树）：按照边权值递增的顺序，从 $E - E_{T}$ 中选择一条边。若该边加入 $T$ 后不构成回路，则将其加入 $E_{T}$；否则舍弃，直到 $E_{T}$ 包含 $n - 1$ 条边为止。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图6.16 Kruskal算法构造最小生成树的过程
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
Kruskal算法的简单实现如下： 在Kruskal算法中，每当选择一条连接两棵不同树的边时，这两棵树将通过这条边合并为一棵更大的树，随着算法的进行，整个森林逐渐合并成一棵树。考虑到算法效率，在最坏情况下需要对所有的|E|条边各扫描一次。通常，边会存储在一个堆（见第7章）中，每次从中选出最小权值的边所需时间为 $O(\log_2|E|)$。同时，使用并查集来快速确定两个顶点是否属于同一集合的时间复杂度为 $O(a(|\mathcal{V}|))$，这里 $a(|\mathcal{V}|)$ 增长极其缓慢，可视为常数。因此，Kruskal算法的总时间复杂度为 $O(|E| \log_2 |E|)$，不依赖于 $|\mathcal{V}|$，这使得它特别适合于处理边稀疏但顶点较多的图。 ## 6.4.2 最短路径 **考虑通径** 最短路径的分析与举例以及相关的算法（2009、2023） 在6.3节中讨论的广度优先搜索算法适用于求解无权图的最短路径。当图是带权图时，从一个顶点 $\nu_{0}$ 到图中任意另一个顶点 $\nu_{i}$ 的路径上所有边的权值之和，称为该路径的带权路径长度；其中，带权路径长度最小的路径（可能存在多条）称为最短路径。 <!-- page: 241 --> 第6章图 求解最短路径问题的算法通常基于其最优子结构性质：两点间最短路径上的任意子路径，也是对应端点间的最短路径。图的最短路径问题一般可分为两类：一是单源最短路径——求图中某个顶点到其余各顶点的最短路径，可使用经典的 Dijkstra（迪杰斯特拉）算法求解；二是所有顶点对之间的最短路径，可使用 Floyd（弗洛伊德）算法求解。 ## 1. Dijkstra 算法求解最短路径问题 Dijkstra 算法使用一个集合 $S$ 记录已确定最短路径的顶点。初始时，将源点（顶点 0）放入 $S$；每当将一个新顶点 $i$ 加入 $S$ 后，需更新源点到所有尚未确定最短路径的顶点（集合 $V - S$ 中的顶点）的当前最短路径长度。算法执行过程中维护以下三个辅助数组： - **final[|]**：标记各顶点是否已找到最短路径（是否属于集合 $S$）。 - **dist[|]**：记录从源点到各顶点的当前最短路径长度。初始化时，若存在从源点到顶点 $i$ 的直接边，则 $\mathrm{dist}[i]$ 为该边的权值，否则置为 $\infty$。 - **path[|]**：path[i]存储从源点到顶点 $i$ 的最短路径。算法结束后，可通过 path[|] 数组回溯，重构出完整的最短路径。 假设源点为顶点 0，集合 $S$ 初始仅含顶点 0。图以邻接矩阵 $\arcs$ 表示，其中 $\arcs[i][j]$ 为有向边 $< i,j>$ 的权值；若该边不存在，则 $\arcs[i][j]$ 为 $\infty$。 Dijkstra 算法的步骤如下（暂不考虑对 path[|] 的操作）： 1）初始化：集合 $S = \{0\}$，$\mathrm{dist}[]$ 的初始值为 $\mathrm{dist}[i] = \arcs[0][i], i = 1,2,\dots ,n - 1$。 2）选择最短路径顶点：从不在 $S$ 中的顶点集合（$V - S$）中选出顶点 $j$，使得 $\mathrm{dist}[j]$ 最小，此时，顶点 $j$ 即为当前从源点出发的最短路径的终点，将其加入集合 $S$。 3）松弛操作：对每个从顶点 $j$ 出发的邻接顶点 $k$（$\arcs[j][k] \neq \infty$），若 $\mathrm{dist}[j] + \arcs[j][k] < \mathrm{dist}[k]$，则更新 $\mathrm{dist}[k] = \mathrm{dist}[j] + \arcs[j][k]$。 4）重复步骤2）～3）共 $n - 1$ 次，直至所有顶点都包含在集合 $S$ 中。 每个新顶点加入集合 $S$ 后，都可能发现到达其他尚未确定最短路径顶点的更短路径，从而需要更新相应的 $\mathrm{dist}[]$ 值。以右图为例，设源点为 $\nu_{0}$，初始时 $S = \{\nu_{0}\}$，$\mathrm{dist}[1] = 3$，$\mathrm{dist}[2] = 7$。将 $\nu_{1}$ 加入集合 $S$ 后，发现路径 $\nu_{0} \rightarrow \nu_{1} \rightarrow \nu_{2}$ 的长度为 4（$\mathrm{dist}[1] + \arcs[1][2] = 3 + 1 = 4$），小于原来的7，因此将 $\mathrm{dist}[2]$ 更新为4。 思考：Dijkstra 算法与 Prim 算法有何异同之处？①
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
**参考资料** ▶ Dijkstra 算法求解最短路径的实例（2012、2014、2016、2021） 例如，对图 6.17 中的图应用 Dijkstra 算法求从顶点 1 出发到其余各顶点的最短路径的过程，如表 6.2 所示。算法执行过程的说明如下。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
每轮得到的最短路径如下：
第1轮：$1\rightarrow 5$，路径距离为5
第2轮：$1\rightarrow 5\rightarrow 4$，路径距离为7
第3轮：$1\rightarrow 5\rightarrow 2$，路径距离为8
第4轮：$1\rightarrow 5\rightarrow 2\rightarrow 3$，路径距离为9
图 6.17 应用 Dijkstra 算法的图
① Dijkstra 算法的流程、操作与 Prim 算法的都很相似，都基于贪心策略。区别在于，i. 目的不同：Dijkstra 算法的目的是构建单源点的最短路径树；Prim 算法的目的是构建最小生成树。ii. 算法思路略有不同：Prim 算法从一个点开始，每次选择权值最小的边，将其连接到已构建的生成树上，直至所有顶点都已加入；而 Dijkstra 算法每次找出到源点距离最近且未归入集合的点，并把它归入集合，同时以这个点为基础，更新从源点到其他所有顶点的距离。iii. 适用的图不同：Prim 算法只能用于带权无问图；Dijkstra 算法可用于带权有问图或带权无问图。
<!-- page: 242 -->
2027年数据结构考研复习指导
表 6.2 从 $v_{1}$ 到各终点的 dist 值和最短路径的求解过程
| 顶点 | 第1轮 | 第2轮 | 第3轮 | 第4轮 |
| --- | --- | --- | --- | --- |
| 2 | 10
$v_{1} \rightarrow v_{2}$ | 8
$v_{1} \rightarrow v_{5} \rightarrow v_{2}$ | 8
$v_{1} \rightarrow v_{5} \rightarrow v_{2}$ | |
| 3 | ∞ | 14
$v_{1} \rightarrow v_{5} \rightarrow v_{3}$ | 13
$v_{1} \rightarrow v_{5} \rightarrow v_{4} \rightarrow v_{3}$ | 9
$v_{1} \rightarrow v_{5} \rightarrow v_{2} \rightarrow v_{3}$ |
| 4 | ∞ | 7
$v_{1} \rightarrow v_{5} \rightarrow v_{4}$ | | |
| 5 | 5
$v_{1} \rightarrow v_{5}$ | | | |
| 集合 S | {1, 5} | {1, 5, 4} | {1, 5, 4, 2} | {1, 5, 4, 2, 3} |
初始化：集合 $S$ 初始为 $\{v_{1}\}$，从 $v_{1}$ 可达 $v_{2}$ 和 $v_{5}$，不可达 $v_{3}$ 和 $v_{4}$，因此 $\mathrm{dist}[]$ 数组的初始值为 $\mathrm{dist}[2] = 10$，$\mathrm{dist}[3] = \infty$，$\mathrm{dist}[4] = \infty$，$\mathrm{dist}[5] = 5$。
第1轮：选出最小值 $\mathrm{dist}[5]$，将 $v_{5}$ 加入集合 $S$，此时已确定 $v_{1}$ 到 $v_{5}$ 的最短路径。检查从 $v_{5}$ 出发的邻接边：$v_{5}$ 可达 $v_{2}$，$v_{1} \rightarrow v_{5} \rightarrow v_{2}$ 的长度为8，小于当前 $\mathrm{dist}[2] = 10$，更新 $\mathrm{dist}[2] = 8$；$v_{5}$ 可达 $v_{3}$，$v_{1} \rightarrow v_{5} \rightarrow v_{3}$ 的长度为14，更新 $\mathrm{dist}[3] = 14$；$v_{5}$ 可达 $v_{4}$，$v_{1} \rightarrow v_{5} \rightarrow v_{4}$ 的长度为7，更新 $\mathrm{dist}[4] = 7$。
第2轮：选出最小值 $\mathrm{dist}[4]$，将 $v_{4}$ 加入集合 $S$。检查从 $v_{4}$ 出发的邻接边：$v_{4}$ 不可达 $v_{2}$，$\mathrm{dist}[2]$ 不变；$v_{4}$ 可达 $v_{3}$，$v_{1} \rightarrow v_{5} \rightarrow v_{4} \rightarrow v_{3}$ 的长度为13，小于当前 $\mathrm{dist}[3] = 14$，更新 $\mathrm{dist}[3] = 13$。
第3轮：选出最小值 $\mathrm{dist}[2]$，将 $v_{2}$ 加入集合 $S$。检查从 $v_{2}$ 出发的邻接边：$v_{2}$ 可达 $v_{3}$，$v_{1} \rightarrow v_{5} \rightarrow v_{2} \rightarrow v_{3}$ 的长度为9，小于当前 $\mathrm{dist}[3] = 13$，更新 $\mathrm{dist}[3] = 9$。
第4轮：选出唯一最小值 $\mathrm{dist}[3]$，将 $v_{3}$ 加入集合 $S$，此时，所有顶点均已包含在集合 $S$ 中。
使用邻接矩阵表示图，并采用线性扫描 $\mathrm{dist}[]$ 查找最小值时，Dijkstra 算法的时间复杂度为 $O(|V|^2)$。若改用带权邻接表，虽然松弛操作的总代价可降至 $O(|E|)$，但由于查找最小 $\mathrm{dist}[]$ 值仍需 $O(|V|)$ 时间，总时间复杂度仍为 $O(|V|^2)$。即使只需求解从源点到某一个特定顶点的最短路径，在最坏情况下仍需处理所有顶点，因此时间复杂度不变，仍为 $O(|V|^2)$。
特别注意：Dijkstra 算法不适用于存在负权边的图。该算法基于贪心策略，一旦顶点被加入集合 S，便不再更新其最短路径。然而，若图中存在负权边，后续路径可能通过负权边“绕回”已确定的顶点，从而发现更短路径，而 Dijkstra 算法无法察觉这一变化，导致结果错误。例如，对于图 6.18 所示的带权有向图，Dijkstra 算法可能无法得到正确的最短路径。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b)
图 6.18 边上带有负权值的有向带权图
## 2. Floyd 算法求各顶点之间最短路径问题
给定带权有向图，对任意两个不同顶点 $v_{i} \neq v_{j}$，求解从 $v_{i}$ 到 $v_{j}$ 的最短路径及其长度。
Floyd 算法的基本思想：迭代生成一系列 $n$ 阶方阵 $A^{(-1)}, A^{(0)}, \dots, A^{(k)}, \dots, A^{(n-1)}$，其中 $A^{(k)}[i][j]$ 表示从顶点 $v_{i}$ 到 $v_{j}$，仅允许使用编号不超过 $k$ 的顶点作为中间顶点时的最短路径长度。初始时 $(k = -1)$，若存在从 $v_{i}$ 到 $v_{j}$ 的直接边，则 $A^{(-1)}[i][j]$ 为该边的权值；否则设为 $\infty$。特别地，对所有 $i$，令 $A^{(-1)}[i][i] = 0$。随后，依次考虑顶点 $k$ ($k = 0, 1, \dots, n-1$) 作为中间顶点，若经由 $v_{k}$ 的路径
<!-- page: 243 -->
第6章图
比当前记录的路径更短，则更新对应的距离。算法的描述如下：
定义 $n$ 阶方阵序列 $A^{(-1)}, A^{(0)}, \dots, A^{(n-1)}$，其中，
$$
A^{(-1)}[i][j] = \operatorname{arcs}[i][j]
$$
$$
A^{(k)}[i][j] = \operatorname{Min}\left\{A^{(k-1)}[i][j], \quad A^{(k-1)}[i][k] + A^{(k-1)}[k][j]\right\}, \ k = 0, 1, \cdots, n-1
$$
式中，$A^{(0)}[i][j]$ 表示从 $v_{i}$ 到 $v_{j}$、仅允许使用 $v_{0}$ 作为中间顶点的最短路径长度；一般地，$A^{(k)}[i][j]$ 表示从 $v_{i}$ 到 $v_{j}$、中间顶点编号不超过 $k$ 的最短路径长度。Floyd 算法是一个迭代过程，每完成一次迭代，便将下一个顶点纳入可选的中间顶点集合；经过 $n$ 次迭代后，$A^{(n-1)}[i][j]$ 即为 $v_{i}$ 到 $v_{j}$ 的最短路径长度。最终，矩阵 $A^{(n-1)}$ 中的每个元素即为对应顶点对的最短路径长度。
图 6.19 所示为一带权有向图 $G$ 及其邻接矩阵。应用 Floyd 算法求解所有顶点对之间的最短路径长度的过程如表 6.3 所示。算法执行过程的说明如下。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 有向图 $G$ 图 6.19 带权有向图 $G$ 及其邻接矩阵
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) $G$ 的邻接矩阵
初始化：方阵 $A^{(-1)}[i][j] = \operatorname{arcs}[i][j]$。
第 1 轮：以 $v_{0}$ 为中间顶点，检查全部顶点对 $\{i,j\}$。若 $A^{(-1)}[i][j] > A^{(-1)}[i][0] + A^{(-1)}[0][j]$，则将 $A^{(-1)}[i][j]$ 更新为 $A^{(-1)}[i][0] + A^{(-1)}[0][j]$。$A^{(-1)}[2][1] = \infty$，而 $A^{(-1)}[2][0] + A^{(-1)}[0][1] = 11$，因 $\infty > 11$，故更新 $A^{(-1)}[2][1] = 11$。其余元素保持不变，得到方阵 $A^{(0)}$。
第 2 轮：以 $v_{1}$ 为中间顶点，检查全部顶点对 $\{i,j\}$。$A^{(0)}[0][2] = 13$，而 $A^{(0)}[0][1] + A^{(0)}[1][2] = 10$，因 $13 > 10$，故更新 $A^{(0)}[0][2] = 10$，得到方阵 $A^{(1)}$。
第 3 轮：以 $v_{2}$ 为中间顶点，检查全部顶点对 $\{i,j\}$。$A^{(1)}[1][0] = 10$，而 $A^{(1)}[1][2] + A^{(1)}[2][0] = 9$，更新 $A^{(1)}[1][0] = 9$，最终得到方阵 $A^{(2)}$，其中每个元素 $A^{(2)}[i][j]$ 即为 $v_{i}$ 到 $v_{j}$ 的最短路径长度。
表 6.3 Floyd 算法的执行过程
| A | A^{(−1)} | | | A^{(0)} | | | A^{(1)} | | | A^{(2)} | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| | V_{0} | V_{1} | V_{2} | V_{0} | V_{1} | V_{2} | V_{0} | V_{1} | V_{2} | V_{0} | V_{1} | V_{2} |
| V_{0} | 0 | 6 | 13 | 0 | 6 | 13 | 0 | 6 | 10 | 0 | 6 | 10 |
| V_{1} | 10 | 0 | 4 | 10 | 0 | 4 | 10 | 0 | 4 | 2 | 0 | 4 |
| V_{2} | 5 | ∞ | 0 | 5 | 11 | 0 | 5 | 11 | 0 | 5 | 11 | 0 |
Floyd 算法的时间复杂度为 $O(|V|^3)$。其代码结构紧凑，仅需一个三重循环，无须复杂数据结构，且常数因子较小，因此在中等规模图上实际运行效率较高。
Floyd 算法允许图中存在负权边，但不允许存在负权环。Floyd 算法同样适用于带权无向图——只需将每条无向边视为两条方向相反、权值相同的有向边。
此外，也可通过调用单源最短路径算法求解所有顶点对的最短路径：在边权非负的条件下，依次以每个顶点为源点运行 Dijkstra 算法。Dijkstra 算法的时间复杂度为 $O(|V|^2)$，因此共需执行 $|\mathbf{V}|$ 次，总时间复杂度为 $O(|V|^3)$，与 Floyd 算法的相同。
<!-- page: 244 -->
2027年数据结构考研复习指导
BFS算法、Dijkstra算法和Floyd算法求最短路径的总结如表6.4所示。
表 6.4 BFS 算法、Dijkstra 算法和 Floyd 算法求最短路径的总结
| | BFS 算法 | Dijkstra 算法 | Floyd 算法 |
| --- | --- | --- | --- |
| 用途 | 求单源最短路径 | 求单源最短路径 | 求各顶点之间的最短路径 |
| 无权图 | 适用 | 适用 | 适用 |
| 带权图 | 不适用 | 适用 | 适用 |
| 带负权值的图 | 不适用 | 不适用 | 适用 |
| 带负权回路的图 | 不适用 | 不适用 | 不适用 |
| 时间复杂度 | O(|V|2)或 O(|V|+|E|) | O(|V|2) | O(|V|2) |