xxx 最小生成树问题（Jarník-Prim算法） 题目描述 给定一个带权无向连通图 G=(V, E)，其中每条边 (u, v) 有一个非负权重 w(u, v)。目标是找到一个边的子集 T ⊆ E，使得这些边连接所有顶点且不形成环（构成一棵生成树），并且所有边的权重之和最小。这样的生成树称为最小生成树（MST）。Jarník-Prim算法通过逐步扩展一棵子树来构建MST。 解题过程 算法核心思想 Jarník-Prim算法属于贪心算法。它从任意一个顶点开始，初始化一棵只包含该顶点的树。每一步中，选择连接当前树与树外顶点且权重最小的边，将该边和对应的顶点加入树中。重复此过程直到所有顶点都被包含。 数据结构准备 键值数组（key） ：记录每个顶点到当前子树的最小边权重。初始时，树中顶点的key设为0，其他顶点的key设为∞。 父节点数组（parent） ：记录每个顶点在MST中的父节点，用于构建生成树。 优先队列（最小堆） ：根据key值高效选取下一个要加入的顶点。 详细步骤 a. 初始化 ： 任选一个顶点（如顶点0）作为起点，设置 key[ 0 ] = 0。 其他顶点 v 的 key[ v] = ∞，parent[ v ] = -1（表示未连接）。 将所有顶点按key值插入最小堆。 b. 循环处理直至堆空 ： 从堆中取出key最小的顶点 u（首次取到起点）。 遍历 u 的所有邻接顶点 v： 若 v 仍在堆中（未加入MST）且边权 w(u, v) < key[ v ]，说明找到更优连接： 更新 key[ v ] = w(u, v)。 更新 parent[ v ] = u。 调整堆中 v 的位置（减少其key值）。 c. 输出结果 ： 最终 parent 数组记录了MST的边：对于每个顶点 v ≠ 0，边 (parent[ v ], v) 属于MST。 MST的总权重为所有 key[ v ] 之和。 实例演示 考虑一个包含4个顶点的图（顶点0-3），边权重如下： (0,1): 1, (0,2): 4, (1,2): 2, (1,3): 5, (2,3): 3 从顶点0开始，key = [ 0, ∞, ∞, ∞ ]。 取出顶点0，更新邻居：key[ 1]=1（parent[ 1]=0），key[ 2]=4（parent[ 2 ]=0）。 取出key最小的顶点1，检查邻居： 顶点2：边权2 < key[ 2]=4，更新key[ 2]=2（parent[ 2 ]=1）。 顶点3：key[ 3]=5（parent[ 3 ]=1）。 取出顶点2，检查邻居顶点3：边权3 < key[ 3]=5，更新key[ 3]=3（parent[ 3 ]=2）。 取出顶点3，无未处理邻居。 MST边为 (0,1), (1,2), (2,3)，总权重=1+2+3=6。 复杂度分析 使用二叉堆时，每次调整堆需 O(log V)，共处理 V 个顶点和 E 条边，总复杂度为 O((V+E) log V)。 使用斐波那契堆可优化至 O(E + V log V)，适合稠密图。 关键点 贪心选择性质：每次选最小边保证全局最优。 与Kruskal算法区别：Prim维护一棵树，Kruskal可能多棵子树合并。