算法研究：图解最小生成树之普里姆算法

算法研究：图解最小生成树之普里姆算法2013-08-26 csdn Simba888888我们在图的定义中说过，带有权值的图就是网结构。一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的n-1条边。所谓的最小成本，就是n个顶点，用n-1条边把一个连通图连接起来，并且使得权值的和最小。综合以上两个概念，我们可以得出：构造连通网的最小代价生成树，即最小生成树（Minimum Cost Spanning Tree）。

找连通图的最小生成树，经典的有两种算法，普里姆算法和克鲁斯卡尔算法，这里介绍克里姆算法。

为了能够讲明白这个算法，我们先构造网图的邻接矩阵，如图7-6-3的右图所示。

也就是说，现在我们已经有了一个存储结构为MGraph的MG（见《邻接矩阵创建图》）。MG有9个顶点，它的二维数组如右图所示，数组中我们使用65535代表无穷。

下面我们对着程序和每一步循环的图示来看：

算法代码：

/* Prim算法生成最小生成树*/void MiniSpanTree_Prim（MGraph MG）{int min, i, j, k;int adjvex[MAXVEX];/* 保存相关顶点下标 */int lowcost[MAXVEX];/* 保存相关顶点间边的权值 */lowcost[0] = 0;/* 初始化第一个权值为0，即v0加入生成树 *//* lowcost的值为0，在这里就是此下标的顶点已经加入生成树 */adjvex[0] = 0;/* 初始化第一个顶点下标为0 */cout << "最小生成树的边为：" << endl;for （i = 1; i < MG.numVertexes; i++）{lowcost[i] = MG.arc[0][i];/* 将v0顶点与之有边的权值存入数组 */adjvex[i] = 0;/* 初始化都为v0的下标 */}for （i = 1; i < MG.numVertexes; i++）{min = INFINITY; /* 初始化最小权值为∞， */j = 1;k = 0;while （j < MG.numVertexes）/* 循环全部顶点 */{if （lowcost[j] ！= 0 && lowcost[j] < min）/* 如果权值不为0且权值小于min */{min = lowcost[j];/* 则让当前权值成为最小值 */k = j;/* 将当前最小值的下标存入k */}j++;}cout << "（" << adjvex[k] << ", " << k << "）" << ""; /* 打印当前顶点边中权值最小的边 */lowcost[k] = 0;/* 将当前顶点的权值设置为0,表示此顶点已经完成任务 */for （j = 1; j < MG.numVertexes; j++）/* 循环所有顶点 */{/* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */if （lowcost[j] ！= 0 && MG.arc[k][j] < lowcost[j]）{lowcost[j] = MG.arc[k][j];/* 将较小的权值存入lowcost相应位置 */adjvex[j] = k;/* 将下标为k的顶点存入adjvex */}}}cout << endl;}