xxx 最小生成树的 Prim 算法 题目描述 给定一个连通无向图 \( G = (V, E) \)，其中每条边 \( (u, v) \) 有一个权重 \( w(u, v) \)，要求构造一棵生成树，使得所有边的权重之和最小。Prim 算法通过逐步扩展子树来求解最小生成树（MST），其核心思想是从任意顶点开始，每次选择连接当前子树与外部顶点的最小权重边，并将对应顶点加入子树，直到所有顶点均被包含。 解题过程 初始化 选择任意顶点 \( s \) 作为起始点，将其加入集合 \( S \)（表示当前子树中的顶点）。 初始化一个数组 key ，记录每个顶点到子树 \( S \) 的最小边权重。初始时， key[s] = 0 ，其他顶点的 key 值为无穷大（表示尚未连接到 \( S \)）。 使用优先队列（最小堆）维护所有未加入 \( S \) 的顶点，按 key 值排序。 逐步扩展子树 从优先队列中取出 key 值最小的顶点 \( u \)（即与当前子树 \( S \) 距离最近的顶点），将其加入 \( S \)。 遍历 \( u \) 的所有邻接顶点 \( v \)： 若 \( v \notin S \) 且边 \( (u, v) \) 的权重小于 key[v] ，则更新 key[v] = w(u, v) ，并记录 \( u \) 为 \( v \) 的父节点（用于后续构建生成树）。 重复上述过程，直到优先队列为空。 生成最小生成树 所有顶点的父节点关系构成一棵最小生成树，树边为 \( (v, \text{parent}[ v]) \)，总权重为所有 key 值之和。 示例说明 考虑以下无向图（顶点为 A、B、C、D，边及权重为 A-B:1, A-C:4, B-C:2, B-D:5, C-D:3）： 从 A 开始， key[A]=0 ，其他为 ∞。 取出 A，更新邻接顶点 B 和 C 的 key 值（B:1, C:4）。 取出 B（最小 key=1 ），更新 C 和 D（C 的 key 从 4 更新为 2，D:5）。 取出 C（ key=2 ），更新 D 的 key 为 3。 取出 D（ key=3 ），所有顶点已加入子树。 生成树边为 A-B、B-C、C-D，总权重为 1+2+3=6。 关键点 Prim 算法的时间复杂度取决于优先队列的实现：使用二叉堆时为 \( O(|E| \log |V|) \)，使用斐波那契堆可优化至 \( O(|E| + |V| \log |V|) \)。 算法始终选择当前最小权重的边，通过贪心策略保证全局最优。