最小生成树算法
字数 3384 2025-11-13 07:17:32

最小生成树算法

最小生成树（Minimum Spanning Tree, MST）是图论中的一个经典问题。给定一个连通的无向图，最小生成树是原图的一个子图，它是一棵树，包含图中所有顶点，并且具有最小的总边权之和。这个问题在网络设计、电路布线等领域有重要应用。

问题描述
假设有一个连通无向图 G=(V, E)，其中 V 是顶点集合，E 是边集合。每条边 (u, v) 都有一个权重 w(u, v)。我们的目标是找到一个边的子集 T ⊆ E，使得：

  1. T 连接了所有顶点（即所有顶点在 T 形成的子图中是连通的）。
  2. T 不形成任何环（即 T 是一棵树）。
  3. T 中所有边的权重之和 ∑w(u, v) 最小。

核心思想与关键性质
解决最小生成树问题的算法基于一个关键性质：切割性质。

  • 切割：将图的顶点集 V 任意划分成两个互不相交的子集 S 和 V-S。
  • 横跨切割的边：如果一个边的两个端点分别属于 S 和 V-S，则该边横跨切割 (S, V-S)。
  • 切割性质：对于任意一个切割，横跨该切割的所有边中权重最小的边，必然属于图的最小生成树。

这个性质是贪心算法的基础。我们可以通过一步步地、局部地选择“当前看来最优”的边（即横跨某个切割的最小权重边）来逐步构建全局最优的最小生成树。

有两种著名的算法都基于此思想，但构建切割的方式不同：Prim 算法和 Kruskal 算法。

Prim 算法

Prim 算法从一个顶点开始，逐步“生长”出一棵生成树。它每次增加一条连接“已访问顶点集合”和“未访问顶点集合”的最小权重边。

算法步骤

  1. 初始化：

    • 创建一个集合 mstSet（或使用一个布尔数组 inMST）来记录哪些顶点已经包含在最小生成树中。初始时，所有顶点都不在集合内。
    • 创建一个数组 key[]，用于记录每个顶点连接到当前最小生成树所需的最小权重。初始时，将所有顶点的 key 值设为无穷大（∞），表示尚未找到连接边。
    • 创建一个数组 parent[]，用于记录最小生成树中每个顶点的父节点，从而最终能构建出整棵树。
    • 任选一个顶点作为起始点（例如顶点 0）。将其 key 值设为 0，因为它将是树的根节点。将其 parent 设为 -1（表示没有父节点）。

  2. 循环处理所有顶点：
    当 mstSet 尚未包含所有顶点时，重复以下步骤：
    a. 选取下一个顶点：从尚未在 mstSet 中的顶点里，选取一个 key 值最小的顶点 u。在第一次迭代中，选取的自然是 key 为 0 的起始顶点。
    b. 将顶点加入生成树：将顶点 u 加入 mstSet，表示它已成为最小生成树的一部分。
    c. 更新相邻顶点的 key 值：遍历顶点 u 的所有未被访问过（不在 mstSet 中）的邻接顶点 v。
    * 如果边 (u, v) 的权重小于 v 当前的 key 值，则：
    * 更新 v 的 key 值为边 (u, v) 的权重。
    * 更新 v 的 parent 为 u。这表示在当前方案下，连接 v 到生成树的最佳边是 (u, v)。

  3. 输出结果：

    • 最终，parent[] 数组就定义了一棵最小生成树。对于每个顶点 i (i ≠ 根节点)，(parent[i], i) 就是最小生成树中的一条边。

图解过程（简化）
假设有一个图，顶点为 A, B, C, D，边及其权重为：A-B:1, A-C:4, B-C:2, B-D:6, C-D:3。

  • 初始化：选 A 为起点，key[A]=0, key[B]=key[C]=key[D]=∞。
  • 第1步：选 key 最小的 A。更新其邻居 B 和 C：key[B] = min(∞, 1) = 1, parent[B]=A；key[C] = min(∞, 4) = 4, parent[C]=A。
  • 第2步：在 {B, C, D} 中选 key 最小的 B（key=1）。将 B 加入 MST。更新 B 的邻居 C 和 D：对于 C，边权重 2 < key[C] 的 4，所以更新 key[C]=2, parent[C]=B；对于 D，更新 key[D]=6, parent[D]=B。
  • 第3步：在 {C, D} 中选 key 最小的 C（key=2）。将 C 加入 MST。更新 C 的邻居 D：边权重 3 < key[D] 的 6，所以更新 key[D]=3, parent[D]=C。
  • 第4步：选 D（key=3）。将 D 加入 MST。所有顶点处理完毕。
  • 最终 MST 边为：(A,B), (B,C), (C,D)，总权重为 1+2+3=6。

时间复杂度：

  • 使用邻接矩阵和简单的遍历查找最小 key 顶点，复杂度为 O(V²)。
  • 使用邻接表和最小堆（优先队列）来高效地提取最小 key 顶点和更新 key 值，复杂度可优化至 O(E log V)。

Kruskal 算法

Kruskal 算法不从一个顶点开始生长，而是考虑所有边，按权重从小到大依次尝试加入生成树，如果加入该边不会形成环，则加入，否则跳过。

算法步骤

  1. 初始化：

    • 将图的所有边按权重从小到大排序。
    • 创建一个并查集（Union-Find）数据结构，初始时每个顶点自成一个集合。
    • 初始化一个空集合 MST 用于存储最终选中的边。

  2. 处理排序后的边：
    按权重从小到大的顺序遍历每一条边 (u, v)：

    • 使用并查集检查顶点 u 和 v 是否属于同一个集合（即是否已经连通）。
    • 如果不在同一个集合：说明加入边 (u, v) 不会形成环。将这条边加入 MST 集合，并使用并查集的合并操作将 u 和 v 所在的集合合并。
    • 如果在同一个集合：说明 u 和 v 已经通过其他边连通，加入 (u, v) 会形成环，因此跳过此边。

  3. 算法终止：

    • 当 MST 中的边数达到 |V| - 1 时，最小生成树已经形成，可以提前终止。
    • 或者遍历完所有边后结束。

图解过程（简化）
使用同上例的图：边 A-B:1, A-C:4, B-C:2, B-D:6, C-D:3。

  • 边排序后为：A-B(1), B-C(2), C-D(3), A-C(4), B-D(6)。
  • 处理 A-B(1)：A, B 不在同一集合，加入 MST。合并 {A, B}。
  • 处理 B-C(2)：B 在 {A,B}, C 在 {C}，不在同一集合，加入 MST。合并为 {A,B,C}。
  • 处理 C-D(3)：C 在 {A,B,C}, D 在 {D}，不在同一集合，加入 MST。合并为 {A,B,C,D}。此时 MST 已有 3 条边（|V|=4, 3=4-1），算法结束。
  • 最终 MST 边为：A-B, B-C, C-D，总权重为 6。

时间复杂度：

  • 排序边需要 O(E log E) 时间，由于 E 最多为 O(V²)，所以 O(E log E) 等价于 O(E log V)。
  • 并查集的操作（查找和合并）经过路径压缩和按秩优化后，近似为常数时间 O(α(V))，其中 α 是反阿克曼函数，增长极慢。
  • 因此，总时间复杂度为 O(E log E) 或 O(E log V)，主要由排序步骤决定。

总结与对比

特性 Prim 算法 Kruskal 算法
核心思想 从点出发，逐步“生长”一棵树。 从边出发，按权重从小到大合并森林。
适用图 对稠密图（边数 E 接近 V²）更有效。 对稀疏图（边数 E 远小于 V²）更有效。
数据结构 通常使用优先队列（最小堆）。 需要排序边，并使用并查集。
时间复杂度 O(E log V)（使用二叉堆和邻接表） O(E log E)（主要由排序决定）

两种算法都是贪心算法的优秀范例，通过切割性质保证了正确性。在实际应用中，根据图的稠密程度选择更合适的算法。

最小生成树算法 最小生成树（Minimum Spanning Tree, MST）是图论中的一个经典问题。给定一个连通的无向图，最小生成树是原图的一个子图，它是一棵树，包含图中所有顶点，并且具有最小的总边权之和。这个问题在网络设计、电路布线等领域有重要应用。 问题描述 假设有一个连通无向图 G=(V, E)，其中 V 是顶点集合，E 是边集合。每条边 (u, v) 都有一个权重 w(u, v)。我们的目标是找到一个边的子集 T ⊆ E，使得： T 连接了所有顶点（即所有顶点在 T 形成的子图中是连通的）。 T 不形成任何环（即 T 是一棵树）。 T 中所有边的权重之和 ∑w(u, v) 最小。 核心思想与关键性质 解决最小生成树问题的算法基于一个关键性质： 切割性质 。 切割 ：将图的顶点集 V 任意划分成两个互不相交的子集 S 和 V-S。 横跨切割的边 ：如果一个边的两个端点分别属于 S 和 V-S，则该边横跨切割 (S, V-S)。 切割性质 ：对于任意一个切割，横跨该切割的所有边中权重最小的边，必然属于图的最小生成树。 这个性质是贪心算法的基础。我们可以通过一步步地、局部地选择“当前看来最优”的边（即横跨某个切割的最小权重边）来逐步构建全局最优的最小生成树。 有两种著名的算法都基于此思想，但构建切割的方式不同：Prim 算法和 Kruskal 算法。 Prim 算法 Prim 算法从一个顶点开始，逐步“生长”出一棵生成树。它每次增加一条连接“已访问顶点集合”和“未访问顶点集合”的最小权重边。 算法步骤 初始化 ： 创建一个集合 mstSet （或使用一个布尔数组 inMST ）来记录哪些顶点已经包含在最小生成树中。初始时，所有顶点都不在集合内。 创建一个数组 key[] ，用于记录每个顶点连接到当前最小生成树所需的最小权重。初始时，将所有顶点的 key 值设为无穷大（∞），表示尚未找到连接边。 创建一个数组 parent[] ，用于记录最小生成树中每个顶点的父节点，从而最终能构建出整棵树。 任选一个顶点作为起始点（例如顶点 0）。将其 key 值设为 0，因为它将是树的根节点。将其 parent 设为 -1（表示没有父节点）。 循环处理所有顶点 ： 当 mstSet 尚未包含所有顶点时，重复以下步骤： a. 选取下一个顶点 ：从尚未在 mstSet 中的顶点里，选取一个 key 值最小的顶点 u 。在第一次迭代中，选取的自然是 key 为 0 的起始顶点。 b. 将顶点加入生成树 ：将顶点 u 加入 mstSet ，表示它已成为最小生成树的一部分。 c. 更新相邻顶点的 key 值 ：遍历顶点 u 的所有未被访问过（不在 mstSet 中）的邻接顶点 v 。 * 如果边 (u, v) 的权重小于 v 当前的 key 值，则： * 更新 v 的 key 值为边 (u, v) 的权重。 * 更新 v 的 parent 为 u 。这表示在当前方案下，连接 v 到生成树的最佳边是 (u, v) 。 输出结果 ： 最终， parent[] 数组就定义了一棵最小生成树。对于每个顶点 i (i ≠ 根节点)， (parent[i], i) 就是最小生成树中的一条边。 图解过程（简化） 假设有一个图，顶点为 A, B, C, D，边及其权重为：A-B:1, A-C:4, B-C:2, B-D:6, C-D:3。 初始化：选 A 为起点， key[A]=0 , key[B]=key[C]=key[D]=∞ 。 第1步：选 key 最小的 A。更新其邻居 B 和 C： key[B] = min(∞, 1) = 1 , parent[B]=A ； key[C] = min(∞, 4) = 4 , parent[C]=A 。 第2步：在 {B, C, D} 中选 key 最小的 B（ key=1 ）。将 B 加入 MST。更新 B 的邻居 C 和 D：对于 C，边权重 2 < key[C] 的 4，所以更新 key[C]=2 , parent[C]=B ；对于 D，更新 key[D]=6 , parent[D]=B 。 第3步：在 {C, D} 中选 key 最小的 C（ key=2 ）。将 C 加入 MST。更新 C 的邻居 D：边权重 3 < key[D] 的 6，所以更新 key[D]=3 , parent[D]=C 。 第4步：选 D（ key=3 ）。将 D 加入 MST。所有顶点处理完毕。 最终 MST 边为：(A,B), (B,C), (C,D)，总权重为 1+2+3=6。 时间复杂度 ： 使用邻接矩阵和简单的遍历查找最小 key 顶点，复杂度为 O(V²)。 使用邻接表和最小堆（优先队列）来高效地提取最小 key 顶点和更新 key 值，复杂度可优化至 O(E log V)。 Kruskal 算法 Kruskal 算法不从一个顶点开始生长，而是考虑所有边，按权重从小到大依次尝试加入生成树，如果加入该边不会形成环，则加入，否则跳过。 算法步骤 初始化 ： 将图的所有边按权重从小到大排序。 创建一个并查集（Union-Find）数据结构，初始时每个顶点自成一个集合。 初始化一个空集合 MST 用于存储最终选中的边。 处理排序后的边 ： 按权重从小到大的顺序遍历每一条边 (u, v) ： 使用并查集检查顶点 u 和 v 是否属于同一个集合（即是否已经连通）。 如果不在同一个集合 ：说明加入边 (u, v) 不会形成环。将这条边加入 MST 集合，并使用并查集的合并操作将 u 和 v 所在的集合合并。 如果在同一个集合 ：说明 u 和 v 已经通过其他边连通，加入 (u, v) 会形成环，因此跳过此边。 算法终止 ： 当 MST 中的边数达到 |V| - 1 时，最小生成树已经形成，可以提前终止。 或者遍历完所有边后结束。 图解过程（简化） 使用同上例的图：边 A-B:1, A-C:4, B-C:2, B-D:6, C-D:3。 边排序后为：A-B(1), B-C(2), C-D(3), A-C(4), B-D(6)。 处理 A-B(1)：A, B 不在同一集合，加入 MST。合并 {A, B}。 处理 B-C(2)：B 在 {A,B}, C 在 {C}，不在同一集合，加入 MST。合并为 {A,B,C}。 处理 C-D(3)：C 在 {A,B,C}, D 在 {D}，不在同一集合，加入 MST。合并为 {A,B,C,D}。此时 MST 已有 3 条边（|V|=4, 3=4-1），算法结束。 最终 MST 边为：A-B, B-C, C-D，总权重为 6。 时间复杂度 ： 排序边需要 O(E log E) 时间，由于 E 最多为 O(V²)，所以 O(E log E) 等价于 O(E log V)。 并查集的操作（查找和合并）经过路径压缩和按秩优化后，近似为常数时间 O(α(V))，其中 α 是反阿克曼函数，增长极慢。 因此，总时间复杂度为 O(E log E) 或 O(E log V)，主要由排序步骤决定。 总结与对比 | 特性 | Prim 算法 | Kruskal 算法 | | :--- | :--- | :--- | | 核心思想 | 从点出发，逐步“生长”一棵树。 | 从边出发，按权重从小到大合并森林。 | | 适用图 | 对稠密图（边数 E 接近 V²）更有效。 | 对稀疏图（边数 E 远小于 V²）更有效。 | | 数据结构 | 通常使用优先队列（最小堆）。 | 需要排序边，并使用并查集。 | | 时间复杂度 | O(E log V)（使用二叉堆和邻接表） | O(E log E)（主要由排序决定） | 两种算法都是贪心算法的优秀范例，通过切割性质保证了正确性。在实际应用中，根据图的稠密程度选择更合适的算法。