最小生成树问题（Prim算法） 题目描述 给定一个连通无向图G=(V, E)，其中每条边有一个正的权重（代表距离、成本等），要求找出一个边的子集T⊆E，使得T连接所有顶点，并且这些边的总权重最小。这样的子集T构成的树称为最小生成树（MST）。 解题思路 Prim算法是一种贪心算法，它从一个顶点开始，逐步扩展树，每次添加一条连接树内顶点和树外顶点的最小权重边，直到所有顶点都被包含在树中。 详细步骤 初始化 选择一个起始顶点s（任意顶点均可，比如顶点0）。 维护三个关键数据结构： key[v] ：记录每个顶点v与当前生成树的最小连接边的权重，初始时 key[s] = 0 ，其他顶点 key[v] = ∞ 。 inMST[v] ：标记顶点v是否已加入生成树，初始时所有顶点为 false 。 parent[v] ：记录顶点v在生成树中的父节点，用于构建MST的边。 主循环 重复以下步骤直到所有顶点加入生成树： a. 选择顶点 ：从尚未加入生成树的顶点中选出 key 值最小的顶点u（即u与当前树有最小的连接边）。 b. 加入生成树 ：将u标记为 inMST[u] = true 。如果u不是起始顶点，将边 (parent[u], u) 加入MST。 c. 更新key值 ：遍历u的所有邻接顶点v。如果v未加入生成树且边(u, v)的权重小于 key[v] ，则更新 key[v] = weight(u, v) ，并设置 parent[v] = u 。 算法结束 当所有顶点加入生成树后， parent 数组和 key 数组共同定义了MST的所有边及其权重。 举例说明 考虑一个包含4个顶点的图，边权重如下： (0,1)=2, (0,2)=4, (1,2)=1, (1,3)=3, (2,3)=5。 从顶点0开始： key[0]=0 , 其他为∞。 第一次迭代：选择顶点0，更新邻接顶点1和2的 key 为2和4， parent[1]=0 , parent[2]=0 。 第二次迭代：选择最小 key 的顶点1（key=2），加入边(0,1)。更新顶点2（因为边(1,2)=1<4，故 key[2]=1 , parent[2]=1 ）和顶点3（ key[3]=3 , parent[3]=1 ）。 第三次迭代：选择顶点2（key=1），加入边(1,2)。更新顶点3（边(2,3)=5>3，不更新）。 第四次迭代：选择顶点3（key=3），加入边(1,3)。 最终MST包含边(0,1)、(1,2)、(1,3)，总权重为6。 关键点 Prim算法通过贪心选择确保每次加入的边都是当前最小权重的连接边。 使用优先队列（如最小堆）优化顶点选择，可将时间复杂度从O(V²)降至O(E log V)。 算法适用于稠密图（如使用邻接矩阵）和稀疏图（如使用邻接表+堆）。