脚本宝典收集整理的这篇文章主要介绍了最小生成树问题-prim算法，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
稠密图适合PRim/**1.构建一棵空的最小生成树T。并将全部节点赋值为无穷大.2.任选一个节点放入T。另外一个节点集合为V-t.3.对V-T中节点的赋值进行更新(因为此时新增加一个节点，这些距离可能发生变化)4.从V-T中选择赋值最小的节点，增加T中5.假设V-T非空，继续步骤3～5，否则算法终结*/
邻接矩阵定义
1 tyPEdef struct{ 2 VertexType vertex[MaxNum]; //顶点一维数组 3 EdgeType edge[MaxNum][MaxNum];//路径权值二维数组 4 int vexNum,arcNum; //顶点数，弧数 5 }MGraph;
记忆算法过程
void prim(MGraph G) { 定义顶点下标数组a； 定义相关顶点的边权值数组b； 初始化第一个顶点权值为0 ；（权值的元素为0，代表该下标对应的顶点已加入生成树） 初始化顶点数组a首元素为0（顶点v0）； 循环操作 将a数组首元素0（顶点v0）的所有边权值放入数组b并初始化顶点数组元 素全部为0 开始进行主旋律 1层循环： （1）循环操作找出目前权值数组b中不为0的最小的那条边 并记录下标为k（此下标代表顶点Vk）； 数组b中k位置设为0，即把该条边加入生成树； （2）将第k个顶点的权值与数组b中权值顺序依次比较，如果b中值为0跳过，如果小于b中该顶点（j）权值，则替换权值b【j】=G.arc【k】【j】，并将顶点数组a【j】=k 2层循环 （1）找出目前权值数组b中不为0最小的那条边 并记录下标k1（此下标代表顶点Vk1）； 数组b中k1位置设为0，即将该条边加入生成树； （2）将第k1个顶点的权值与数组b中权值顺序依次比较，如果b中值为0跳过，如果小于b中该顶点（j1）权值，则替换权值b【j1】=G.arc【k1】【j1】，并将顶点数组a【j1】=k1 3层循环 （1）找出目前权值数组b中不为0最小的那条边 并记录下标k2（此下标为顶点） 数组b中k2位置设为0，即将该条边加入生成树，根据顶点数组a【k2】输出改点 （2）将第k2个顶点的权值与数组b中权值顺序依次比较，如果b中值为0跳过，如果小于b中该顶点（j2）权值，则替换权值b【j1】=G.arc【k2】【j2】，并将顶点数组a【j2】=k2 。。。。。。。 }
算法实现代码
void prim(MGraph G) { int min, i, j, k; int adjvex[MAXV]; //保存相关顶点下标 int lowcost[MAXV]; //保存相关顶点间边的权值 lowcost[0] = 0; //初始化第一个权值为0，即将v0加入生成树 //lowcost的值为0表示此下标的顶点已经加入生成树 adjvex[0] = 0; //初始化第一个顶点下标为0 for (i = 1; i < G.Vnum;i++) { lowcost[i] = G.arc[0][i]; //将v0顶点与之有关的边的权值都存放入权值数组 adjvex[i] = 0; //初始化都为v0的下标 } for (i = 1; i < G.Vnum;i++) { min = 65535; j = 1; k = 0; while (j<G.Vnum)//找最小值 并记录节点下标为k { if (lowcost[j]!=0&&lowcost[j]<min) { //如果权值不为0且权值小于min min = lowcost[j]; //则让当前权值成为最小值 k = j; //将当前最小值的下标存放k } j++; } printf("(%d,%d)", adjvex[k], k); //打印当前顶点边中权值最小边 lowcost[k] = 0;//将当前顶点的权值置为0，表示此顶点已经完成任务 //更新权值数组 for (j = 1; j < G.Vnum;j++) //循环所有顶点，因为我们已经确认第一个放入的0，所有我们循环可以省去0 { if (lowcost[j] != 0 && G.arc[k][j]<lowcost[j]) { /* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */ lowcost[j] = G.arc[k][j]; //将较小权值存入lowcost adjvex[j] = k; //将下标为k的顶点存入adjvex } } } }
以上是脚本宝典为你收集整理的最小生成树问题-prim算法全部内容，希望文章能够帮你解决最小生成树问题-prim算法所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。