最小生成树问题（Prim算法）

题目描述
在一个连通的无向图中，每条边都有一个权重（或成本）。最小生成树（Minimum Spanning Tree, MST）是指原图的一个子图，它是一棵树（无环且连通），包含原图的所有顶点，并且其所有边的权重之和最小。Prim算法是一种贪心算法，用于求解加权无向图的最小生成树。

解题过程

1. 问题分析

• 目标：从连通无向图中选择边，使得所有顶点连通且总权重最小。
• 约束：生成树必须包含所有顶点、无环且边数 = 顶点数 - 1。
• 核心思想：Prim算法通过逐步扩展一棵树来构建MST，每次添加一个与当前树相连的最小权重边。

2. 算法步骤详解
步骤1：初始化

• 选择任意一个顶点（如顶点0）作为起始点，加入最小生成树集合（MST集合）。
• 维护一个数组 key（或 dist），记录每个顶点到当前MST集合的最小边权重。初始时，起始点的 key 值为0，其他顶点为无穷大（∞）。
• 维护一个数组 parent，记录每个顶点在MST中的父节点（用于构建树结构）。
• 使用优先队列（最小堆）快速选择当前最小 key 值的顶点。

步骤2：贪心选择

• 从优先队列中取出 key 值最小的顶点 u（首次取到起始点），将其加入MST集合。
• 遍历 u 的所有邻接顶点 v：
  • 如果 v 不在MST集合中，且边 (u, v) 的权重小于 v 当前的 key 值，则更新 v 的 key 值为该权重，并设置 parent[v] = u。
• 重复此过程，直到所有顶点都加入MST集合。

步骤3：输出结果

• 最终 parent 数组定义了MST的边：对于每个顶点 i（除起始点），边 (parent[i], i) 是MST的一部分。

3. 示例演示
考虑以下图（顶点0~3，边权重如图）：

    (0) —2— (1)
     |     / |
     3    3  1
     |  /    |
    (2) —1— (3)

执行过程：

1. 初始：MST集合 = {}，key = [0, ∞, ∞, ∞]，parent = [-1, -1, -1, -1]。
2. 选择顶点0：MST集合 = {0}，更新邻接顶点1和2的 key：
   • key[1] = 2, parent[1] = 0
   • key[2] = 3, parent[2] = 0
3. 选择最小 key 顶点1：MST集合 = {0,1}，更新顶点2和3：
   • 边(1,2)权重3 ≥ 当前 key[2]（3），不更新
   • key[3] = 1, parent[3] = 1
4. 选择顶点3：MST集合 = {0,1,3}，更新顶点2：
   • 边(3,2)权重1 < 当前 key[2]（3），更新 key[2] = 1, parent[2] = 3
5. 选择顶点2：MST集合已包含所有顶点。
   MST边：(0,1), (1,3), (3,2)，总权重 = 2 + 1 + 1 = 4。

4. 关键点说明

• 贪心正确性：每次选择最小权边保证局部最优解导向全局最优解。
• 时间复杂度：
  • 使用邻接矩阵：O(V²)
  • 使用邻接表 + 最小堆：O(E log V)
• 适用场景：稠密图（顶点少边多）时Prim算法效率较高。

5. 对比Kruskal算法

• Kruskal算法按边权重排序后选择边，适合稀疏图。
• Prim算法需维护连通分量，适合稠密图。