xxx 最小生成树问题（Prim算法） 题目描述 给定一个带权无向连通图 \( G = (V, E) \)，其中 \( V \) 是顶点集，\( E \) 是边集，每条边有一个非负权值。要求构造一棵生成树，使得树上所有边的权值之和最小，这样的生成树称为最小生成树（Minimum Spanning Tree, MST）。Prim算法通过贪心策略逐步扩展子树来求解该问题。 解题过程 算法核心思想 Prim算法从任意一个顶点开始，初始时子树只包含该顶点。每一步选择一条连接当前子树与外部顶点的最小权值边，将对应外部顶点加入子树，直到所有顶点都被包含。该过程保证每次加入的边都是当前可选边中最小的，最终得到最小生成树。 数据结构准备 key数组 ：记录每个顶点到当前子树的最小边权（初始为无穷大，起点为0）。 inMST数组 ：标记顶点是否已加入子树。 parent数组 ：记录生成树中每个顶点的父节点（用于构建树结构）。 优先队列（最小堆） ：按key值排序，高效选取下一个待加入的顶点。 步骤详解 步骤1 ：初始化 任选一个顶点（如顶点0）作为起点，设置 key[0] = 0 ，其他顶点的key值为无穷大。 将所有顶点加入优先队列（按key值排序）。 步骤2 ：循环处理顶点 从队列中取出key最小的顶点 \( u \)（首次为起点），将其加入子树（标记 inMST[u] = true ）。 遍历 \( u \) 的所有邻接顶点 \( v \)： 若 \( v \) 未加入子树，且边 \( (u, v) \) 的权值小于 key[v] ，则更新 key[v] = weight(u, v) ，并设置 parent[v] = u 。 重复上述过程，直到所有顶点加入子树。 示例演示 考虑一个包含4个顶点的图（顶点0-3），边权如下： (0,1): 1 (0,2): 4 (1,2): 2 (1,3): 5 (2,3): 3 执行过程 ： 从顶点0开始，key=[ 0, ∞, ∞, ∞ ]。 取出顶点0，更新邻接点1和2的key：key=[ 0, 1, 4, ∞]，parent[ 1]=0, parent[ 2 ]=0。 取出key最小的顶点1，更新顶点2（边权2<4，故key[ 2]=2, parent[ 2]=1）和顶点3（key[ 3 ]=5）。 取出顶点2，更新顶点3（边权3<5，故key[ 3]=3, parent[ 3 ]=2）。 取出顶点3，所有顶点已加入子树。 生成树边 ：(0,1), (1,2), (2,3)，总权值=1+2+3=6。 复杂度分析 使用邻接表和二叉堆：每次更新key值需 \( O(\log V) \)，共处理 \( V \) 个顶点和 \( E \) 条边，总复杂度为 \( O((V+E) \log V) \)。 使用斐波那契堆可优化至 \( O(E + V \log V) \)。 关键点说明 贪心正确性：每次选择最小权值边能保证全局最优（基于割性质定理）。 适用性：仅适用于无向连通图，图中不能有负权边（但负权边不影响结果，因MST关注边权和，负权边可能被选中）。 通过以上步骤，Prim算法逐步构建出权值和最小的生成树。