xxx 最小生成树的 Jarník-Prim 算法

题目描述
给定一个连通无向图 G=(V, E)，其中每条边 e∈E 有一个权重 w(e)（表示距离或成本）。目标是找到一个边的子集 T⊆E，使得 T 连接所有顶点且无环（即构成一棵生成树），并且所有边的权重之和最小。这个问题称为最小生成树（Minimum Spanning Tree, MST）问题。Jarník-Prim 算法（常称为 Prim 算法）是一种贪心算法，用于高效求解 MST 问题。

解题过程循序渐进讲解

1. 算法核心思想

   • Prim 算法从一个任意顶点开始，逐步扩展生成树。每一步都选择连接当前生成树与外部顶点的最小权重边，将新顶点加入生成树。这确保了每次扩展都是当前局部最优选择，最终得到全局最小生成树。
   • 关键点：维护一个集合 S（已加入生成树的顶点）和一个优先队列（存储连接 S 与 V\S 的边）。

2. 算法步骤详解

   • 步骤 1：初始化

     • 选择一个起始顶点 s（任意顶点均可，例如顶点 0）。
     • 初始化集合 S = {s}，表示当前生成树包含的顶点。
     • 初始化一个优先队列（最小堆），存储边及其权重。将所有与 s 相连的边加入优先队列，键为边的权重。
     • 初始化一个数组 key（记录每个顶点到 S 的最小边权重）和 parent（记录生成树中边的连接关系）。对于所有顶点 v：
       • key[v] = ∞（表示初始时未知最小权重），但 key[s] = 0。
       • parent[v] = -1（表示无父节点）。

   • 步骤 2：扩展生成树

     • 当 S ≠ V（即还有顶点未加入生成树）时，重复以下过程：
       a. 从优先队列中取出权重最小的边 (u, v)，其中 u∈S, v∉S。如果队列为空但 S≠V，说明图不连通（但题目假设图连通）。
       b. 将顶点 v 加入集合 S。
       c. 将边 (u, v) 加入生成树 T（通过 parent[v] = u 记录）。
       d. 更新优先队列：遍历 v 的所有邻接顶点 w：
       • 如果 w∉S 且边 (v, w) 的权重小于 key[w]，则更新 key[w] 为该权重，并将 (v, w) 加入优先队列（或更新队列中 w 对应的权重）。
     • 注意：实际实现中，优先队列通常存储顶点（而非边），键为 key[v]，通过 key 的更新自动反映最小权边。

3. 示例演示
   考虑一个简单图，顶点集 {A, B, C, D}，边及权重：

   • (A,B)=1, (A,C)=4, (B,C)=2, (B,D)=5, (C,D)=3
   • 从顶点 A 开始：
     • 初始：S={A}, key=[0,∞,∞,∞], 队列包含 A 的边 (A,B)=1, (A,C)=4。
     • 第 1 步：选最小边 (A,B)=1，加入 B，S={A,B}。更新队列：B 的邻接边 (B,C)=2（小于原 key[C]=4，故更新）、(B,D)=5。
     • 第 2 步：选最小边 (B,C)=2，加入 C，S={A,B,C}。更新队列：C 的邻接边 (C,D)=3（小于 key[D]=5，更新）。
     • 第 3 步：选最小边 (C,D)=3，加入 D，S={A,B,C,D}。结束。
     • 生成树 T 包含边 (A,B), (B,C), (C,D)，总权重 6。

4. 复杂度与优化

   • 时间复杂度：
     • 使用二叉堆实现优先队列时，为 O(|E| log |V|)。
     • 使用斐波那契堆可优化到 O(|E| + |V| log |V|)，适合稠密图。
   • 空间复杂度：O(|V| + |E|)，用于存储图和优先队列。
   • 与 Kruskal 算法对比：Prim 算法在稠密图中更高效，而 Kruskal 在稀疏图中更具优势。

5. 正确性证明概要

   • Prim 算法基于贪心选择性质：每次选择的边都是当前连接 S 与 V\S 的最小权边，这一定包含在某个 MST 中（可通过切割性质证明）。
   • 归纳法：假设当前 T 是某 MST 的子集，加入最小边后仍为 MST 子集，最终覆盖所有顶点。

通过以上步骤，Prim 算法逐步构建最小生成树，确保在每一步做出局部最优决策，最终得到全局最优解。