普里姆（Prim）求最小生成树

一、普里姆（Prim）算法

　　1.基本思想：设G=(V, E)是具有n个顶点的连通网，T=(U, TE)是G的最小生成树， T的初始状态为U={u0}（u0∈V），TE={}，重复执行下述操作：在所有u∈U，v∈V-U的边中找一条代价最小的边(u, v)并入集合TE，同时v并入U，直至U=V。即：

（1）从连通网络 G = { V, E }中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。

　　（2）以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。

　　2、示例：

3、实现代码如下：

#include "stdio.h" #include "stdlib.h" #define MAX 110 int a[MAX][MAX],p[MAX]; int main(void) { int i,j,k,n,t,min,sum,new_point,x,y,d; printf("请输入顶点的个数："); scanf("%d",&n); t=n*(n-1)/2; memset(p,0,sizeof(p)); //将p数组初始化为0 printf("请输入每条边的起始端点、权值：/n"); for(i=0;i<t;i++) { scanf("%ld%ld%ld",&x,&y,&d); //输入每条边的权值 a[x][y]=a[y][x]=d; } p[1]=1; sum=0; for(k=0;k<n-1;k++) { min=-1; for(i=1;i<=n;i++) { if(p[i]==1) { for(j=1;j<=n;j++) { if(p[j]==0 && (min==-1 || min>a[i][j])) { min=a[i][j]; //从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边 new_point=j; } } } } p[new_point]=1; sum+=min; } printf("最小生成树的权值为：%d/n",sum); system("pause"); return 0; }