本文主要是介绍15分钟掌握最小生成树普利姆（Prim）算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
15分钟掌握最小生成树普利姆（Prim）算法
假如你是电信工程师，需要为一个镇的9个村庄架设通信网络，村中位置大致如下图V0-V8是村庄，之间的数据是村庄之间的距离，距离越长架设用的线路越长，成本就越高。你们领导要你用最小的成本的完成这次任务，你该怎么办呢?
显然这是个带权值得图，网结构。所谓的最小成本，就是N个顶点，用n-1条边把一个连通图连起来，并使权值的和最小。我们把构造连通网的最小代价生成树称为最小生成树。这里我用普利姆（Prim算法讲解）
我先贴代码，一步一步解释。
void MiniSpanTree_prim(MGraph G)
{
int min,i,j,k;
int adjvex[9];//保存相关顶点下标
int lowcost[9];//保存相关顶点间的权值
lowcost[0]=0;//初始化第一个权值为0，即V0加入生成树
adjvex[i]=0;//初始化第一个顶点下标为0
lowcost[0]=0;
for(int j=1;j<G.numvertex;j++)
{
lowcost[j]=G.arc[0][j];//将V0顶点与之有边的权值存入数组
adjvex[j]=0;//初始化都为V0的下标
}
for(int j=1;j<G.numvertex;j++)
{
min=INFINITY;//初始化最小权值为#
j=1,k=0;
while(j<G.numvertex)//循环全部顶点
{
if(lowcost[j]!=0&&lowcost[j]<min)
{ //如果权值不为0，且权值小于min
min=lowcost[j];//则让当前权值称为最小值
k=j;//将当前最小值小标存入K
}
j++;
}
cout<<"("<<adjvers[k]<<","<<k<<")"<<endl;//打印当前顶点边//中权值最小的边
lowcost[k]=0;
for(j=1;j<G.numvertex;j++)
{
if(lowcost[j]!=0&&arc[k][j]<lowcost[j])
{//若下标为K顶点各边权值小于此前的这些顶点未被加入生///成树树的
lowcost[j]=arc[k][j];//更新
adjvex[j]=k;
}
}
}
}
邻接矩阵如下图
9~13行完成初始工作后，两个数组内容为
14-29行代码执行功能为找到权值最小顶点，找到后赋值给K，并打印adjvex【k】，k。如下图：
30~38行 以K为新的顶点，跟新lowcost数组，执行完后两个数组为，如下图：
这是一个循环后个结果，14-29，在lowcost里找权值最小的，30~38以新的K顶点，更新lowcost数组，运行后如下图：
第三次循环后的结果图
第四次循环后的结果图为：
第5次循环后：
恩，下面我就不贴图了，直到所有的点访问完毕结束
这篇关于15分钟掌握最小生成树普利姆（Prim）算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
