xxx 最小生成树问题（Jarník-Prim 算法） 题目描述 给定一个连通的无向图 \( G = (V, E) \)，其中每条边 \( e \in E \) 有一个权重 \( w(e) \)。目标是找到一个生成树 \( T \subseteq E \)，使得树中所有边的权重之和最小。这样的生成树称为最小生成树（Minimum Spanning Tree, MST）。Jarník-Prim 算法通过贪心策略逐步构建 MST。 解题过程 算法核心思想 Jarník-Prim 算法从任意一个顶点开始，逐步扩展生成树。每次选择连接当前生成树部分与图中其他部分的最小权重边，确保加入的边不会形成环。算法维护两个集合： 已包含在 MST 中的顶点集合 （记为 \( S \)）。 未包含的顶点集合 （记为 \( V \setminus S \)）。 通过优先队列（最小堆）高效选择最小权重边。 初始化步骤 选择任意起始顶点 \( s \in V \)，将其加入集合 \( S \)，并初始化其到生成树的距离为 0。 对于其他所有顶点 \( v \in V \setminus \{s\} \)，初始化其到生成树的距离为 \( \infty \)（即尚未连接）。 使用优先队列（最小堆）存储所有顶点，键值为顶点到当前生成树的最小边权重。 迭代扩展 MST 从优先队列中取出键值最小的顶点 \( u \)（即与当前生成树有最小权重边的顶点），将 \( u \) 加入集合 \( S \)，并将对应边加入 MST。 更新与 \( u \) 相邻的所有未包含顶点 \( v \) 的键值：如果边 \( (u, v) \) 的权重小于 \( v \) 当前的键值，则更新键值为 \( w(u, v) \)，并记录 \( u \) 为 \( v \) 的前驱（用于构建 MST）。 重复上述过程，直到所有顶点都加入 \( S \)。 关键细节 避免环的形成 ：由于每次只选择连接 \( S \) 和 \( V \setminus S \) 的边，加入的边不会在当前生成树中形成环。 时间复杂度 ： 使用二叉堆实现优先队列时，每次插入和提取最小值的操作耗时 \( O(\log n) \)，总时间复杂度为 \( O((|V| + |E|) \log |V|) \)。 使用斐波那契堆可优化到 \( O(|E| + |V| \log |V|) \)。 示例演示 考虑一个简单图：顶点集 \( V = \{A, B, C, D\} \)，边权重为 \( w(A,B)=2 \), \( w(A,C)=1 \), \( w(B,C)=3 \), \( w(B,D)=4 \), \( w(C,D)=5 \)。 从顶点 A 开始，初始 \( S = \{A\} \)。 优先队列中：B 的键值=2（边 A-B），C 的键值=1（边 A-C），D 的键值=∞。 选择最小键值顶点 C 加入 S，边 A-C 加入 MST。 更新相邻顶点：B 的键值min(2, 3)=2（不变），D 的键值=5（边 C-D）。 选择顶点 B 加入 S，边 A-B 加入 MST。 更新相邻顶点 D：键值min(5, 4)=4（边 B-D）。 最后加入顶点 D，边 B-D 加入 MST。 最终 MST 包含边 A-C、A-B、B-D，总权重为 1+2+4=7。 正确性保证 贪心选择性质：每次选择的最小边一定属于 MST（通过割性质证明，即连接两个集合的最小边必在 MST 中）。 算法结束时，所有顶点被连通且无环，生成树必然最小。 通过以上步骤，Jarník-Prim 算法高效且直观地解决了最小生成树问题。