Prim算法如何保证每步选最小边

Prim算法在构建最小生成树时通过维护一个顶点集合和一个权值数组并采用贪心策略来保证每一步都选择当前代价最小的边。其核心在于算法始终从已选顶点集合生成树的一部分出发寻找连接该集合与未选顶点集合的权值最小的边并将该边及其对应的未选顶点加入生成树。这个过程是迭代进行的每一步的局部最优选择最终导向全局最优解——一棵总权值最小的生成树。为了清晰地展示Prim算法的执行逻辑与关键操作我们可以将其核心步骤总结如下表步骤操作描述目的与保证1. 初始化任选一个起始顶点加入集合U初始化数组lowcost[]记录U中顶点到其他所有顶点的边的权值。建立初始的已选顶点集合和待选边信息。2. 寻找最小边在当前lowcost[]数组中寻找权值最小的边该边连接了集合U中的一个顶点和集合V-U中的一个顶点。确保当前步骤选择的是所有跨接两个集合的边中权值最小的一条。这是贪心策略的直接体现。3. 收录顶点将上一步找到的最小边所连接的、属于V-U的顶点加入集合U并将该边加入最小生成树。扩展生成树的顶点集合。4. 更新权值检查新加入的顶点到V-U中其他顶点的边的权值。如果某条边的权值小于lowcost[]中记录的对应值则更新lowcost[]。动态维护U到V-U中每个顶点的最小权值连接为下一步的“最小边选择”提供最新、最准确的数据。保证下一步依然是从当前最优的候选边中选取。5. 循环与结束重复步骤2-4直到集合U包含所有顶点即V-U为空此时已收录的n-1条边构成最小生成树。通过n-1次迭代确保最终生成树包含所有顶点且总权值最小。下面我们通过一个具体的例子和代码来详细说明这个过程。一、算法过程实例演示假设有一个无向连通网其顶点和边的权值如下所示使用邻接矩阵表示INF表示无穷大即两点间无边顶点ABCDA0612B6053C1504D2340我们以顶点A为起始点演示Prim算法的执行过程初始化U {A}。lowcost[]初始化为A到各点的直接距离[0, 6, 1, 2]A到自身的权值为0表示已收录。第一轮在lowcost[]中寻找最小值非0是1对应顶点C。边(A, C)被选中。将C加入UU {A, C}。更新lowcost[]检查C到B、D的权值。C到B权值5当前lowcost[B]6更新lowcost[B]5C到D权值4当前lowcost[D]2不更新。更新后lowcost[]为[0, 5, 0, 2]C对应值置0。第二轮在lowcost[]中寻找最小值非0是2对应顶点D。边(A, D)被选中。将D加入UU {A, C, D}。更新lowcost[]检查D到B的权值。D到B权值3当前lowcost[B]5更新lowcost[B]3。更新后lowcost[]为[0, 3, 0, 0]。第三轮在lowcost[]中寻找最小值非0是3对应顶点B。边(D, B)被选中。将B加入UU {A, B, C, D}。所有顶点已收录算法结束。最终得到的最小生成树包含边(A, C),(A, D),(D, B)总权值为1 2 3 6。可以看到每一步选择的边(A,C),(A,D),(D,B)都是当时连接U和V-U的所有边中权值最小的。二、代码实现与关键注释以下是使用C语言、基于邻接矩阵实现Prim算法的核心代码其中包含了保证每一步选择最小边的关键逻辑。#include stdio.h #include limits.h #define V 4 // 顶点数 #define INF INT_MAX // 用最大值代表无穷大无边 // Prim算法函数返回最小生成树的总权值 int primMST(int graph[V][V]) { int parent[V]; // 用于存储最小生成树中每个顶点的前驱顶点即这条边来自U中的哪个顶点 int lowcost[V]; // 关键数组记录从U到每个未收录顶点V-U的最小权值边 int mstSet[V]; // 标记数组mstSet[i]为1表示顶点i已收录进集合U // 1. 初始化 for (int i 0; i V; i) { lowcost[i] INF; // 初始时所有顶点到U的距离为无穷大 mstSet[i] 0; // 初始时所有顶点都未收录 } // 选择第一个顶点作为起始点 lowcost[0] 0; // 自己到自己的距离为0保证它第一个被选出 parent[0] -1; // 第一个顶点是树的根没有父节点 // 循环V-1次寻找剩下的V-1条边 for (int count 0; count V - 1; count) { // 2. 寻找最小边从lowcost数组中选取最小值关键步骤保证当前最小 int min INF, u; for (int v 0; v V; v) { if (mstSet[v] 0 lowcost[v] min) { // 在未收录的顶点中找权值最小的 min lowcost[v]; u v; // u是当前找到的、连接U和V-U的权值最小的边所指向的顶点 } } // 将选中的顶点u加入集合U mstSet[u] 1; // 3. 更新权值检查新加入的顶点u是否带来了更小的连接关键步骤维护下一步的最优性 for (int v 0; v V; v) { // 条件1v未被收录。条件2u和v之间有边。条件3这条边的权值小于v当前记录的最小权值 if (mstSet[v] 0 graph[u][v] graph[u][v] lowcost[v]) { parent[v] u; // 更新v的前驱为u意味着边(u,v)是目前连接v到U的最佳选择 lowcost[v] graph[u][v]; // 更新v对应的最小权值 } } } // 计算最小生成树的总权值并打印结果 int totalWeight 0; printf(Edge \tWeight ); for (int i 1; i V; i) { printf(%d - %d \t%d , parent[i], i, graph[i][parent[i]]); totalWeight graph[i][parent[i]]; } printf(Total Weight of MST: %d , totalWeight); return totalWeight; } // 主函数使用上述例子中的图 int main() { /* 创建上述例子中的图 */ int graph[V][V] { {0, 6, 1, 2}, {6, 0, 5, 3}, {1, 5, 0, 4}, {2, 3, 4, 0}, }; primMST(graph); return 0; }代码关键点解析lowcost数组的核心作用它动态维护着集合U到集合V-U中每个顶点的、当前已知的最小连接权值。在每一轮循环开始时从中选取最小值就等价于从所有跨接U和V-U的边中选取了权值最小的一条。寻找最小边内层第一个循环for (int v 0; v V; v) { if (mstSet[v] 0 lowcost[v] min) ... }这一步是贪心策略的直接实现。它遍历所有未收录的顶点找出lowcost值最小的那个这个顶点就是通过当前最小权值边与生成树相连的顶点。更新权值内层第二个循环if (mstSet[v] 0 graph[u][v] graph[u][v] lowcost[v]) { ... }这一步保证了信息的时效性和最优性。当新顶点u加入U后U的边界扩大了。我们需要检查从u出发到所有未收录顶点v的边如果这条边(u, v)的权值比v当前记录的lowcost[v]更小说明发现了一条从U到v的更优更短的连接于是更新lowcost[v]和parent[v]。这为下一轮选择最小边提供了最新的、最优的数据基础。三、算法正确性保证与对比Prim算法每一步都选择当前最小边这基于一个重要的贪心选择性质对于任意一个正在构建中的最小生成树的子树即集合U连接U和V-U的最小权值边必然包含在整个图的最小生成树中。通过数学归纳法可以证明遵循这一性质进行迭代最终得到的树就是最小生成树。与另一种经典算法Kruskal相比Prim算法是**“加点法”始终维护一个连通的子树并不断扩张而Kruskal是“加边法”**按全局边权排序后依次添加并利用并查集避免环路。两者都采用了贪心策略但维护的数据结构和扩张方式不同。Prim算法在稠密图边数接近顶点数平方中效率更高通常使用邻接矩阵或邻接表配合优先队列实现其时间复杂度在朴素实现下为O(V²)使用优先队列可优化至O(E log V)。参考来源PTA 公路村村通Prim思想最小生成树——Prim算法C语言实现数据结构之最小生成树Prim算法最小生成树(Prim、Kruskal)算法秒懂图的应用--最小生成树c实现prim算法最小生成树