xxx 最小生成树问题（Jarník-Prim 算法） 题目描述 给定一个带权无向连通图 \( G = (V, E) \)，其中每条边 \( e \in E \) 有一个非负权值 \( w(e) \)。目标是找到图 \( G \) 的一棵生成树，使得所有边的权值之和最小。这样的生成树称为最小生成树（Minimum Spanning Tree, MST）。Jarník-Prim 算法（常称为 Prim 算法）通过逐步扩展一个子树来构建 MST。 解题过程 算法思想 Jarník-Prim 算法采用贪心策略，从任意一个顶点开始，逐步扩展生成树。每一步选择连接当前生成树与树外顶点且权值最小的边，将对应顶点加入生成树，直到所有顶点都被包含。 关键数据结构 优先队列（最小堆） ：用于高效选取当前连接生成树与树外顶点的最小权值边。 数组 key ：记录每个顶点到当前生成树的最小边权。初始时， key 设为无穷大（表示未连接）。 数组 inMST ：标记顶点是否已加入生成树。 步骤详解 步骤 1 ：初始化 任选一个起始顶点 \( s \)（如 \( s = 0 \)），设置 key[s] = 0 ，其他顶点的 key 值为无穷大。 将所有顶点加入优先队列，按 key 值排序。 初始化 inMST 全为 false ，表示尚无顶点在生成树中。 步骤 2 ：迭代扩展生成树 当优先队列非空时，重复以下过程： 从队列中取出 key 值最小的顶点 \( u \)（即当前与生成树连接代价最小的顶点）。 将 \( u \) 标记为 inMST[u] = true ，表示加入生成树。 遍历 \( u \) 的所有邻接顶点 \( v \)： 若 \( v \) 不在生成树中（ inMST[v] == false ）且边 \( (u, v) \) 的权值 \( w(u, v) < \text{key}[ v ] \)： 更新 key[v] = w(u, v) ，表示找到更小的连接代价。 在优先队列中调整 \( v \) 的位置（或重新插入）。 步骤 3 ：输出结果 算法结束时， key 数组记录每个顶点加入生成树时的最小边权，所有 key 值之和即为 MST 的总权值。实际 MST 可通过记录每条边的连接方式还原。 示例演示 考虑一个包含 4 个顶点的图，边权如下： 从顶点 0 开始， key = [0, ∞, ∞, ∞] 。 取出顶点 0，更新邻接顶点： key[1] = 1 , key[2] = 4 。 取出顶点 1（最小 key=1 ），更新顶点 2 和 3： key[2] = 2 （更优）, key[3] = 5 。 取出顶点 2（ key=2 ），更新顶点 3： key[3] = 3 （更优）。 取出顶点 3（ key=3 ），队列空。 MST 总权值 = 1 + 2 + 3 = 6，边为 {(0,1), (1,2), (2,3)}。 复杂度分析 使用二叉堆实现优先队列时，每次插入和提取最小值的操作时间为 \( O(\log V) \)，总操作次数为 \( O(E) \)（每条边可能触发一次更新），故时间复杂度为 \( O(E \log V) \)。 若使用斐波那契堆，可优化至 \( O(E + V \log V) \)。 正确性保证 算法的贪心选择由 MST 的割性质（Cut Property）保证：对于任意割（将顶点分为两个集合），连接两集的最小权边必属于 MST。每一步中，算法选取当前生成树与树外顶点形成割的最小边，因此最终构造的生成树是最小的。