最小生成树：Prim算法的实现与优化
字数 1914 2025-12-09 14:25:16

最小生成树：Prim算法的实现与优化

1. 问题描述

最小生成树（Minimum Spanning Tree, MST） 是指在一个连通的无向带权图中，找到一个包含所有顶点的树（无环连通子图），使得树上所有边的总权重最小。

Prim算法是解决MST问题的经典贪心算法之一，适用于稠密图。它的核心思想是：

  • 从任意一个顶点开始，逐步扩展生成树，每次选择一条连接已选顶点集和未选顶点集的最小权重边，并将该边加入生成树，直到所有顶点都被包含。

2. 算法步骤详解

假设图有 \(V\) 个顶点，\(E\) 条边，权重均为非负数。

基本Prim算法流程：

  1. 初始化：

    • 任选一个顶点（如顶点0）作为起始点，将其加入已选顶点集 \(MSTSet\)。
    • 维护一个数组 key[]，key[v] 表示顶点 \(v\) 到当前已选顶点集的最小边权重。初始时，key[0] = 0（起始点），其他顶点 key[v] = ∞。
    • 维护一个数组 parent[]，parent[v] 表示顶点 \(v\) 在MST中的父节点（用于最后构造MST）。初始时，parent[0] = -1（根节点）。

  2. 循环扩展（重复 \(V-1\) 次，每次加入一个顶点）：
    a. 从未选顶点集中，选择一个 key 值最小的顶点 \(u\)。
    b. 将 \(u\) 加入已选顶点集 \(MSTSet\)。
    c. 遍历 \(u\) 的所有邻居顶点 \(v\)（且 \(v\) 未在 \(MSTSet\) 中）：

    • 如果边 \((u, v)\) 的权重 \(w\) 小于 key[v]，则更新 key[v] = w，并设置 parent[v] = u。

  3. 结束：

    • 最终 parent[] 数组记录了MST中每条边的连接关系，所有边的权重之和即为最小生成树的总权重。

3. 示例演示

考虑以下图（顶点数 V=5）：

顶点与边权重：
0 -1- 1
0 -3- 2
1 -3- 2
1 -6- 3
2 -4- 3
2 -2- 4
3 -5- 4

执行过程（从顶点0开始）：

  • 初始：MSTSet = {}，key = [0, ∞, ∞, ∞, ∞]，parent = [-1, -1, -1, -1, -1]。
  • 第1步：选 key 最小顶点0加入 MSTSet，更新邻居：
    • 顶点1：key[1] = 1，parent[1] = 0
    • 顶点2：key[2] = 3，parent[2] = 0
  • 第2步：未选顶点中 key 最小是顶点1（key=1），加入 MSTSet，更新邻居：
    • 顶点2：边(1,2)权重3，但当前 key[2]=3 不变。
    • 顶点3：key[3] = 6，parent[3] = 1
  • 第3步：未选顶点中 key 最小是顶点2（key=3），加入 MSTSet，更新邻居：
    • 顶点3：边(2,3)权重4 < key[3]=6，更新 key[3]=4，parent[3]=2
    • 顶点4：key[4] = 2，parent[4] = 2
  • 第4步：未选顶点中 key 最小是顶点4（key=2），加入 MSTSet，更新邻居：
    • 顶点3：边(4,3)权重5 > key[3]=4，不更新。
  • 第5步：未选顶点中 key 最小是顶点3（key=4），加入 MSTSet，结束。

MST边（根据 parent[]）：

  • 1 → 0（权重1）
  • 2 → 0（权重3）
  • 3 → 2（权重4）
  • 4 → 2（权重2）
    总权重 = 1+3+4+2 = 10。

4. 时间复杂度与优化

  • 朴素实现（每次遍历所有顶点找最小 key）：

    • 时间复杂度 \(O(V^2)\)，适合稠密图（边数 \(E ≈ V^2\)）。

  • 堆优化（使用最小堆存储未选顶点的 key 值）：

    • 初始化堆：\(O(V)\)
    • 每次从堆中提取最小顶点：\(O(\log V)\)，共 \(V\) 次 → \(O(V \log V)\)
    • 每条边可能触发一次 key 更新和堆调整：\(O(E \log V)\)
    • 总复杂度：\(O((V+E) \log V)\)，适合稀疏图。

  • 进一步优化（使用斐波那契堆）：

    • 可将复杂度降至 \(O(E + V \log V)\)，但常数较大，实际应用较少。

5. 关键点总结

  1. Prim算法基于顶点扩展，每次选择当前可达的最小边。
  2. 与Kruskal算法（基于边排序）相比，Prim在稠密图中更高效。
  3. 算法正确性依赖于贪心选择性质：当前最小边一定属于全局最小生成树。
  4. 注意处理非连通图：Prim只能得到连通分量的MST，需对每个连通分量单独执行。
最小生成树：Prim算法的实现与优化 1. 问题描述 最小生成树（Minimum Spanning Tree, MST） 是指在一个 连通的无向带权图 中，找到一个包含所有顶点的树（无环连通子图），使得树上所有边的 总权重最小 。 Prim算法是解决MST问题的经典贪心算法之一，适用于 稠密图 。它的核心思想是： 从任意一个顶点开始，逐步扩展生成树，每次选择一条 连接已选顶点集和未选顶点集的最小权重边 ，并将该边加入生成树，直到所有顶点都被包含。 2. 算法步骤详解 假设图有 \(V\) 个顶点，\(E\) 条边，权重均为非负数。 基本Prim算法流程 ： 初始化 ： 任选一个顶点（如顶点0）作为起始点，将其加入已选顶点集 \(MSTSet\)。 维护一个数组 key[] ， key[v] 表示顶点 \(v\) 到当前已选顶点集的 最小边权重 。初始时， key[0] = 0 （起始点），其他顶点 key[v] = ∞ 。 维护一个数组 parent[] ， parent[v] 表示顶点 \(v\) 在MST中的父节点（用于最后构造MST）。初始时， parent[0] = -1 （根节点）。 循环扩展 （重复 \(V-1\) 次，每次加入一个顶点）： a. 从 未选顶点集 中，选择一个 key 值最小的顶点 \(u\)。 b. 将 \(u\) 加入已选顶点集 \(MSTSet\)。 c. 遍历 \(u\) 的所有邻居顶点 \(v\)（且 \(v\) 未在 \(MSTSet\) 中）： 如果边 \((u, v)\) 的权重 \(w\) 小于 key[v] ，则更新 key[v] = w ，并设置 parent[v] = u 。 结束 ： 最终 parent[] 数组记录了MST中每条边的连接关系，所有边的权重之和即为最小生成树的总权重。 3. 示例演示 考虑以下图（顶点数 V=5）： 执行过程 （从顶点0开始）： 初始： MSTSet = {} ， key = [0, ∞, ∞, ∞, ∞] ， parent = [-1, -1, -1, -1, -1] 。 第1步 ：选 key 最小顶点0加入 MSTSet，更新邻居： 顶点1： key[1] = 1 ， parent[1] = 0 顶点2： key[2] = 3 ， parent[2] = 0 第2步 ：未选顶点中 key 最小是顶点1（key=1），加入 MSTSet，更新邻居： 顶点2：边(1,2)权重3，但当前 key[2]=3 不变。 顶点3： key[3] = 6 ， parent[3] = 1 第3步 ：未选顶点中 key 最小是顶点2（key=3），加入 MSTSet，更新邻居： 顶点3：边(2,3)权重4 < key[3]=6 ，更新 key[3]=4 ， parent[3]=2 顶点4： key[4] = 2 ， parent[4] = 2 第4步 ：未选顶点中 key 最小是顶点4（key=2），加入 MSTSet，更新邻居： 顶点3：边(4,3)权重5 > key[3]=4 ，不更新。 第5步 ：未选顶点中 key 最小是顶点3（key=4），加入 MSTSet，结束。 MST边 （根据 parent[] ）： 1 → 0（权重1） 2 → 0（权重3） 3 → 2（权重4） 4 → 2（权重2） 总权重 = 1+3+4+2 = 10。 4. 时间复杂度与优化 朴素实现 （每次遍历所有顶点找最小 key ）： 时间复杂度 \(O(V^2)\)，适合稠密图（边数 \(E ≈ V^2\)）。 堆优化 （使用最小堆存储未选顶点的 key 值）： 初始化堆：\(O(V)\) 每次从堆中提取最小顶点：\(O(\log V)\)，共 \(V\) 次 → \(O(V \log V)\) 每条边可能触发一次 key 更新和堆调整：\(O(E \log V)\) 总复杂度：\(O((V+E) \log V)\)，适合稀疏图。 进一步优化 （使用斐波那契堆）： 可将复杂度降至 \(O(E + V \log V)\)，但常数较大，实际应用较少。 5. 关键点总结 Prim算法基于 顶点 扩展，每次选择当前可达的最小边。 与Kruskal算法（基于边排序）相比，Prim在稠密图中更高效。 算法正确性依赖于 贪心选择性质 ：当前最小边一定属于全局最小生成树。 注意处理 非连通图 ：Prim只能得到连通分量的MST，需对每个连通分量单独执行。