最小生成树：Kruskal算法

字数 2027 2025-12-10 16:40:28

最小生成树：Kruskal算法

Kruskal算法是一种用于在加权连通图中寻找最小生成树（Minimum Spanning Tree, MST）的贪心算法。最小生成树是一个连通所有顶点的无环子图，其所有边的权重之和最小。

算法思想：

Kruskal算法的核心思想是：将所有边按权重从小到大排序，然后依次考虑每条边，如果这条边的加入不会导致生成树形成环，就将其加入生成树中，否则丢弃。重复此过程，直到生成树中包含了V-1条边（V为顶点数）。

详细步骤：

排序：将图中所有边按权重从小到大排序。
初始化：创建一个并查集（Union-Find/Disjoint Set）数据结构，用于高效地判断顶点是否连通。初始化时，每个顶点自成一个集合。
选边：按顺序处理每条边（u, v, weight）。
- 检查连通性：用并查集的Find操作检查边(u, v)的两个端点u和v是否在同一个集合中（即是否已连通）。
- 决策：
  - 如果Find(u) != Find(v)：说明加入这条边不会形成环。执行Union(u, v)将u和v所在的集合合并，并将该边加入最小生成树的边集合中。
  - 如果Find(u) == Find(v)：说明u和v已经通过之前选择的边连通了。再加入当前边会形成环，因此丢弃这条边。
终止条件：重复步骤3，直到最小生成树的边数等于V-1（V是顶点总数），此时所有顶点都已连通，算法结束。

具体例子：

考虑以下加权连通图（顶点：A, B, C, D）：

    A
 1/ | \2
B   3  C
 4\ | /5
    D

边列表（[顶点1, 顶点2, 权重]）:
[A, B, 1], [A, C, 2], [A, D, 3], [B, D, 4], [C, D, 5]

算法执行过程：

排序：将边按权重排序。
- [A, B, 1]
- [A, C, 2]
- [A, D, 3]
- [B, D, 4]
- [C, D, 5]
初始化并查集：
- Set1: {A}, Set2: {B}, Set3: {C}, Set4: {D}
处理边[A, B, 1]：
- Find(A) -> A, Find(B) -> B。结果不同，不连通。
- 执行Union(A, B)，合并集合{A}和{B}。将边A-B加入MST。
- 集合状态：Set1: {A, B}, Set2: {C}, Set3: {D}
- MST 边：{A-B}，权重和=1
处理边[A, C, 2]：
- Find(A) -> A (或B, 因为是同一集合), Find(C) -> C。不同，不连通。
- 执行Union(A, C)，合并{A, B}和{C}。将边A-C加入MST。
- 集合状态：Set1: {A, B, C}, Set2: {D}
- MST 边：{A-B, A-C}，权重和=3
处理边[A, D, 3]：
- Find(A) -> A, Find(D) -> D。不同，不连通。
- 执行Union(A, D)，合并{A, B, C}和{D}。将边A-D加入MST。
- 集合状态：Set1: {A, B, C, D}
- MST 边：{A-B, A-C, A-D}，权重和=6

此时，MST已有4-1=3条边，算法结束。最终最小生成树总权重为1+2+3=6。

注意：如果处理下一条边[B, D, 4]，会发现Find(B)=A，Find(D)=A，两顶点已在同一集合，加入会形成环，所以丢弃。

关键要点与复杂度：

并查集的作用：其Find和Union操作（通常配合路径压缩和按秩合并优化）的时间复杂度接近常数O(α(N))，其中α是阿克曼函数的反函数，增长极慢。这使得Kruskal算法非常高效。
时间复杂度：算法的时间复杂度主要取决于排序。对E条边排序的复杂度是O(E log E)。在稠密图（E ≈ V^2）中，O(E log E) 近似于 O(E log V)。排序后，用并查集处理每条边是O(α(V)) ≈ O(1)，总复杂度为O(E log E)。
空间复杂度：主要是存储边O(E)和并查集O(V)，为O(E+V)。
适用场景： Kruskal算法在边相对稀疏的图中表现优异，因为其复杂度与边数E直接相关。相比适用于稠密图的Prim算法，Kruskal在处理稀疏图时通常更简洁高效。

总结：
Kruskal算法是一种基于边的贪心算法，其巧妙之处在于通过并查集高效判断环的存在。它从权重最小的边开始逐步构建森林并最终合并成树，确保了最终生成树的总权重最小。记住其核心步骤：排序 -> 利用并查集检查环 -> 无环则加边。

最小生成树：Kruskal算法 Kruskal算法是一种用于在加权连通图中寻找最小生成树（Minimum Spanning Tree, MST）的贪心算法。最小生成树是一个连通所有顶点的无环子图，其所有边的权重之和最小。算法思想： Kruskal算法的核心思想是：将所有边按权重从小到大排序，然后依次考虑每条边，如果这条边的加入不会导致生成树形成环，就将其加入生成树中，否则丢弃。重复此过程，直到生成树中包含了 V-1 条边（ V 为顶点数）。详细步骤：排序：将图中所有边按权重从小到大排序。初始化：创建一个并查集（Union-Find/Disjoint Set）数据结构，用于高效地判断顶点是否连通。初始化时，每个顶点自成一个集合。选边：按顺序处理每条边（ u , v , weight ）。检查连通性：用并查集的 Find 操作检查边 (u, v) 的两个端点 u 和 v 是否在同一个集合中（即是否已连通）。决策：如果 Find(u) != Find(v) ：说明加入这条边不会形成环。执行 Union(u, v) 将 u 和 v 所在的集合合并，并将该边加入最小生成树的边集合中。如果 Find(u) == Find(v) ：说明 u 和 v 已经通过之前选择的边连通了。再加入当前边会形成环，因此丢弃这条边。终止条件：重复步骤3，直到最小生成树的边数等于 V-1 （ V 是顶点总数），此时所有顶点都已连通，算法结束。具体例子：考虑以下加权连通图（顶点：A, B, C, D）：边列表（ [顶点1, 顶点2, 权重] ）: [A, B, 1] , [A, C, 2] , [A, D, 3] , [B, D, 4] , [C, D, 5] 算法执行过程：排序：将边按权重排序。 [A, B, 1] [A, C, 2] [A, D, 3] [B, D, 4] [C, D, 5] 初始化并查集： Set1: {A} , Set2: {B} , Set3: {C} , Set4: {D} 处理边 [A, B, 1] ： Find(A) -> A , Find(B) -> B 。结果不同，不连通。执行 Union(A, B) ，合并集合 {A} 和 {B} 。将边 A-B 加入MST。集合状态： Set1: {A, B} , Set2: {C} , Set3: {D} MST 边：{A-B}，权重和=1 处理边 [A, C, 2] ： Find(A) -> A (或 B , 因为是同一集合), Find(C) -> C 。不同，不连通。执行 Union(A, C) ，合并 {A, B} 和 {C} 。将边 A-C 加入MST。集合状态： Set1: {A, B, C} , Set2: {D} MST 边：{A-B, A-C}，权重和=3 处理边 [A, D, 3] ： Find(A) -> A , Find(D) -> D 。不同，不连通。执行 Union(A, D) ，合并 {A, B, C} 和 {D} 。将边 A-D 加入MST。集合状态： Set1: {A, B, C, D} MST 边：{A-B, A-C, A-D}，权重和=6 此时，MST已有 4-1=3 条边，算法结束。最终最小生成树总权重为 1+2+3=6 。注意：如果处理下一条边 [B, D, 4] ，会发现 Find(B)=A ， Find(D)=A ，两顶点已在同一集合，加入会形成环，所以丢弃。关键要点与复杂度：并查集的作用：其 Find 和 Union 操作（通常配合路径压缩和按秩合并优化）的时间复杂度接近常数 O(α(N)) ，其中 α 是阿克曼函数的反函数，增长极慢。这使得Kruskal算法非常高效。时间复杂度：算法的时间复杂度主要取决于排序。对 E 条边排序的复杂度是 O(E log E) 。在稠密图（ E ≈ V^2 ）中， O(E log E) 近似于 O(E log V) 。排序后，用并查集处理每条边是 O(α(V)) ≈ O(1) ，总复杂度为 O(E log E) 。空间复杂度：主要是存储边 O(E) 和并查集 O(V) ，为 O(E+V) 。适用场景： Kruskal算法在边相对稀疏的图中表现优异，因为其复杂度与边数 E 直接相关。相比适用于稠密图的Prim算法，Kruskal在处理稀疏图时通常更简洁高效。总结： Kruskal算法是一种基于边的贪心算法，其巧妙之处在于通过并查集高效判断环的存在。它从权重最小的边开始逐步构建森林并最终合并成树，确保了最终生成树的总权重最小。记住其核心步骤：排序 -> 利用并查集检查环 -> 无环则加边。