最小生成树：Prim算法

一、问题描述
最小生成树（Minimum Spanning Tree, MST）是指在加权连通图中找到一棵生成树，使得所有边的权重之和最小。Prim算法是一种用于构建最小生成树的贪心算法，其核心思想是从一个顶点开始，逐步扩展树，每次选择连接树与非树节点的最小权重边，直到覆盖所有顶点。

二、算法步骤详解

1. 初始化

   • 选择图中任意一个顶点作为起始点，将其加入最小生成树集合（记为MST）。
   • 维护一个数组key[]，记录每个顶点到MST的最小边权重。初始时，起始点的key值为0，其他顶点为无穷大（表示尚未连接）。
   • 维护一个数组parent[]，记录每个顶点在MST中的父节点（用于构建树结构）。

2. 贪心选择与扩展

   • 重复以下步骤，直到所有顶点都加入MST：
     a. 从尚未加入MST的顶点中，选取key值最小的顶点u（即当前与MST距离最近的顶点）。
     b. 将u加入MST。
     c. 遍历u的所有邻接顶点v：
     若v未在MST中，且边(u, v)的权重小于v的当前key值，则更新key[v] = weight(u, v)，并设置parent[v] = u。

3. 终止条件

   • 当所有顶点都加入MST时，算法结束。此时parent[]数组即定义了最小生成树的边。

三、示例演示
以如下加权图为例（顶点为A、B、C、D，边权重如图）：

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

执行过程：

1. 从A开始，key[A]=0，其他顶点key值为∞。
2. 选择A加入MST，更新邻接点B和C的key值：key[B]=2, key[C]=3。
3. 选择最小key顶点B（权重2）加入MST，更新邻接点D的key=4，检查C：边B-C权重1小于当前key[C]=3，更新key[C]=1。
4. 选择最小key顶点C（权重1）加入MST，检查邻接点D：边C-D权重5大于当前key[D]=4，不更新。
5. 最后将D加入MST。生成树边为A-B、B-C、B-D，总权重=2+1+4=7。

四、算法复杂度与优化

• 时间复杂度：
  • 朴素实现（邻接矩阵+遍历找最小key）：O(V²)，适合稠密图。
  • 优化实现（邻接表+最小堆）：O(E log V)，适合稀疏图。
• 空间复杂度：O(V)（存储key和parent数组）。

五、对比Kruskal算法

• Prim算法基于顶点扩展，适合稠密图；Kruskal算法基于边排序，适合稀疏图。
• 两者均保证最优解，但贪心策略不同：Prim始终维护一棵树，Kruskal可能同时维护多棵子树（通过并查集合并）。