最小生成树问题（Jarník-Prim算法） 题目描述 给定一个带权无向连通图 \( G = (V, E) \)，其中每条边 \( e \in E \) 有一个非负权重 \( w(e) \)。目标是找到一个边的子集 \( T \subseteq E \)，使得 \( T \) 构成一棵生成树（即连接所有顶点且无环），并且总权重 \( \sum_ {e \in T} w(e) \) 最小。Jarník-Prim算法通过贪心策略逐步扩展一棵树来解决此问题。 解题过程 1. 算法核心思想 Jarník-Prim算法从任意一个顶点开始，初始化一棵空树，每一步添加一条连接树内顶点与树外顶点的最小权重边（称为“轻边”），确保不形成环，直到所有顶点都被包含在树中。该过程依赖优先队列（最小堆）高效选择轻边。 2. 算法步骤详解 步骤1：初始化 选择一个起始顶点 \( s \in V \)，将其加入最小生成树（MST）的顶点集合 \( T_ V \)。 初始化一个优先队列 \( Q \)，存储所有与 \( T_ V \) 相邻的边（键为边的权重）。初始时，将 \( s \) 的所有邻边加入 \( Q \)。 记录每个顶点是否在 \( T_ V \) 中（例如用布尔数组 inMST ）。 初始化 MST 的边集合 \( T_ E = \emptyset \)。 步骤2：扩展MST 当 \( T_ V \) 未包含所有顶点时（即 \( |T_ V| < |V| \)）： 从 \( Q \) 中取出权重最小的边 \( e = (u, v) \)，其中 \( u \in T_ V \)，\( v \notin T_ V \)（通过 inMST 检查）。 将 \( v \) 加入 \( T_ V \)，将边 \( e \) 加入 \( T_ E \)。 遍历 \( v \) 的所有邻边 \( (v, w) \)：若 \( w \notin T_ V \)，将该边加入 \( Q \)。 若取出的边连接两个已在 \( T_ V \) 中的顶点，直接跳过（避免环）。 步骤3：输出结果 最终 \( T_ E \) 即为最小生成树的边集合，总权重为 \( \sum_ {e \in T_ E} w(e) \)。 3. 关键细节与正确性证明 贪心选择性质 ：每次选择的轻边必定属于某个MST（证明参考Cut Property：任意切割中，最小权重的横跨边必在MST中）。 避免环 ：只添加连接树内外顶点的边，确保无环。 复杂度分析 ： 使用二叉堆实现优先队列：每次插入和提取最小值操作需 \( O(\log |E|) \)，总操作次数为 \( O(|E|) \)，故时间复杂度为 \( O(|E| \log |E|) \)。 使用斐波那契堆可优化至 \( O(|E| + |V| \log |V|) \)。 4. 实例演示 考虑一个简单图（顶点集 \( V = \{A, B, C\} \)，边权重：\( AB=1, AC=3, BC=2 \)）： 从 \( A \) 开始，\( T_ V = \{A\} \)，将边 \( AB(1) \)、\( AC(3) \) 加入 \( Q \)。 取出最小边 \( AB(1) \)，将 \( B \) 加入 \( T_ V \)，边 \( AB \) 加入 \( T_ E \)。将 \( B \) 的邻边 \( BC(2) \) 加入 \( Q \)。 取出最小边 \( BC(2) \)，将 \( C \) 加入 \( T_ V \)，边 \( BC \) 加入 \( T_ E \)。 所有顶点已加入，MST包含边 \( AB \) 和 \( BC \)，总权重为 3。 总结 Jarník-Prim算法通过局部最优选择逐步构建全局最优解，其高效性依赖于优先队列。与Kruskal算法（按边排序）不同，Prim算法更适合稠密图（\( |E| \) 接近 \( |V|^2 \) 时性能更优）。