最小生成树：Prim算法

字数 1508 2025-11-19 01:56:07

最小生成树：Prim算法

最小生成树（Minimum Spanning Tree, MST）是指在一个连通无向图中，找到一个包含所有顶点且边权之和最小的树。Prim算法是一种贪心算法，用于求解最小生成树问题。

1. 算法核心思想

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

2. 算法步骤详解

假设图 \(G = (V, E)\) 有 \(n\) 个顶点和 \(m\) 条边，每条边有权重 \(w(u, v)\)。

初始化：
- 选择一个起始顶点 \(s\)（任意顶点均可），将其加入已选集合 \(S\)（表示当前生成树中的顶点）。
- 初始化一个数组 key[]，表示每个顶点到已选集合的最小边权。初始时，key[s] = 0，其他顶点 key[v] = ∞。
- 初始化一个数组 parent[]，记录生成树中每个顶点的父节点（用于构建树结构）。
循环扩展生成树：
- 重复以下步骤 \(n-1\) 次（因为生成树有 \(n-1\) 条边）：
  a. 选择最小边：从所有未选顶点中，选择一个 key 值最小的顶点 \(u\)（即离已选集合最近的顶点）。
  b. 加入生成树：将 \(u\) 加入已选集合 \(S\)，并将边 (parent[u], u) 加入生成树。
  c. 更新相邻顶点的 key 值：遍历 \(u\) 的所有邻接顶点 \(v\)，如果 \(v\) 未在 \(S\) 中且边权 \(w(u, v) < key[v]\)，则更新 key[v] = w(u, v)，并设置 parent[v] = u。
结束：
- 当所有顶点都被加入 \(S\) 时，算法结束。此时 parent 数组记录了生成树的所有边。

3. 示例演示

考虑以下图（顶点为 A, B, C, D，边权如图）：

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

执行过程：

从 A 开始，key[A]=0，其他为 ∞。
选择 A（key 最小），更新邻接点 B 和 C：key[B]=2, key[C]=3, parent[B]=A, parent[C]=A。
选择未选顶点中 key 最小的 B（key=2），将边 (A,B) 加入生成树。更新 B 的邻接点：
- C：边权 1 < key[C]=3，更新 key[C]=1, parent[C]=B。
- D：边权 4 < ∞，更新 key[D]=4, parent[D]=B。
选择 key 最小的 C（key=1），将边 (B,C) 加入生成树。更新 C 的邻接点 D：边权 5 > key[D]=4，不更新。
选择最后一个顶点 D（key=4），将边 (B,D) 加入生成树。
最终生成树边：A-B, B-C, B-D，总权重 = 2+1+4=7。

4. 时间复杂度与优化

朴素实现：每次遍历所有未选顶点找最小值，时间复杂度 \(O(n^2)\)，适合稠密图。
堆优化：使用最小堆存储未选顶点的 key 值，每次取最小值的时间为 \(O(\log n)\)，总复杂度 \(O(m \log n)\)，适合稀疏图。

5. 与Kruskal算法的对比

Prim：基于顶点扩展，适合稠密图（边数多）。
Kruskal：基于边排序，适合稀疏图（边数少）。

通过以上步骤，Prim算法以贪心策略逐步构建最小生成树，确保每次加入的边都是当前最优选择。

最小生成树：Prim算法最小生成树（Minimum Spanning Tree, MST）是指在一个连通无向图中，找到一个包含所有顶点且边权之和最小的树。Prim算法是一种贪心算法，用于求解最小生成树问题。 1. 算法核心思想 Prim算法从任意一个顶点开始，逐步扩展生成树，每次选择一条连接已选顶点集和未选顶点集的最小权值边，并将该边加入生成树。重复这一过程，直到所有顶点都被包含。 2. 算法步骤详解假设图 \( G = (V, E) \) 有 \( n \) 个顶点和 \( m \) 条边，每条边有权重 \( w(u, v) \)。初始化：选择一个起始顶点 \( s \)（任意顶点均可），将其加入已选集合 \( S \)（表示当前生成树中的顶点）。初始化一个数组 key[] ，表示每个顶点到已选集合的最小边权。初始时， key[s] = 0 ，其他顶点 key[v] = ∞ 。初始化一个数组 parent[] ，记录生成树中每个顶点的父节点（用于构建树结构）。循环扩展生成树：重复以下步骤 \( n-1 \) 次（因为生成树有 \( n-1 \) 条边）： a. 选择最小边：从所有未选顶点中，选择一个 key 值最小的顶点 \( u \)（即离已选集合最近的顶点）。 b. 加入生成树：将 \( u \) 加入已选集合 \( S \)，并将边 (parent[u], u) 加入生成树。 c. 更新相邻顶点的 key 值：遍历 \( u \) 的所有邻接顶点 \( v \)，如果 \( v \) 未在 \( S \) 中且边权 \( w(u, v) < key[ v] \)，则更新 key[v] = w(u, v) ，并设置 parent[v] = u 。结束：当所有顶点都被加入 \( S \) 时，算法结束。此时 parent 数组记录了生成树的所有边。 3. 示例演示考虑以下图（顶点为 A, B, C, D，边权如图）：执行过程：从 A 开始， key[A]=0 ，其他为 ∞。选择 A（key 最小），更新邻接点 B 和 C： key[B]=2 , key[C]=3 , parent[B]=A , parent[C]=A 。选择未选顶点中 key 最小的 B（key=2），将边 (A,B) 加入生成树。更新 B 的邻接点： C：边权 1 < key[ C]=3，更新 key[C]=1 , parent[C]=B 。 D：边权 4 < ∞，更新 key[D]=4 , parent[D]=B 。选择 key 最小的 C（key=1），将边 (B,C) 加入生成树。更新 C 的邻接点 D：边权 5 > key[ D ]=4，不更新。选择最后一个顶点 D（key=4），将边 (B,D) 加入生成树。最终生成树边：A-B, B-C, B-D，总权重 = 2+1+4=7。 4. 时间复杂度与优化朴素实现：每次遍历所有未选顶点找最小值，时间复杂度 \( O(n^2) \)，适合稠密图。堆优化：使用最小堆存储未选顶点的 key 值，每次取最小值的时间为 \( O(\log n) \)，总复杂度 \( O(m \log n) \)，适合稀疏图。 5. 与Kruskal算法的对比 Prim ：基于顶点扩展，适合稠密图（边数多）。 Kruskal ：基于边排序，适合稀疏图（边数少）。通过以上步骤，Prim算法以贪心策略逐步构建最小生成树，确保每次加入的边都是当前最优选择。