最小生成树是最小权重生成树的简称。一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边
普里姆算法（Prim算法） 在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和也为最小。
例如如下：图B是由图A的最小生成树
图A 图B
算法过程详解： 存在两个集合：都存储结点 S集合里有所有顶点，V集合中的顶点表示已经确定了到该顶点的边。 初始化V集合中有顶点1,V集合的顶点用i表示，S-V集合中顶点j，寻找w[i][j]最小值找到j点，将j顶点加入到V集合中，继续，直到找到所有顶点。
详解： （1）初始化： 将生成树的起点设为1，V={1}，S-V={2，3，4，5，6} vert[2].loweight=7， vert[2].close=1; vert[3].loweight=1， vert[3].close=1; vert[4].loweight=5， vert[4].close=1; vert[5].loweight=max， vert[5].close=1; vert[6].loweight=max， vert[6].close=1;
（2）第一次循环 V={1，3}，S-V={2，4，5，6} ①遍历vert[j].loweight，找最短边，找到3， 将3加入到V集合中， ②因为V集合中多了3，所以要更新vert[j].loweight，进入到V集合的顶点就不用管了。 更新后： vert[2].loweight=6， vert[2].close=3; vert[3] 不用管了 vert[4].loweight=5， vert[4].close=1; vert[5].loweight=6， vert[5].close=3; vert[6].loweight=4， vert[6].close=3;
（3）第二次循环 V={1，3，6}，S-V={2，4，5} ①遍历vert[j].loweight，找最短边，找到6， 将6加入到V集合中， ②要更新vert[j].loweight 更新后： vert[2].loweight=6， vert[2].close=3; vert[3] 不用管了 vert[4].loweight=5， vert[4].close=1; vert[5].loweight=2， vert[5].close=6; vert[6] 不用管了
（4）第三次循环 V={1，3，6，4}，S-V={2，5} ①遍历vert[j].loweight，找最短边，找到6， 将6加入到V集合中， ②更新vert[j].loweight 更新后： vert[2].loweight=6， vert[2].close=3; vert[3] 不用管了 vert[4] 不用管了 vert[5].loweight=2， vert[5].close=3; vert[6] 不用管了
（5）第四次循环
（6）最终
算法：
#include<stdio.h> #include<stdlib.h> #include<string.h> #define Max 999999 #define min(a,b) a<b?a:b int w[10000][10000],v[10000],n,m; struct ver{//S-V集合中j顶点 int loweight;//j顶点到V集合中i顶点的最小权值 int close;//j顶点与V集合中某点连接中的连线最短的连接点 }vert[10000]; prim(){ int i,j,k;//i表示V中集合中的顶点，j表示S-V中的集合的顶点 v[1]=1;//1到V集合中了 for(j=2;j<=n;j++){ vert[j].close=1; vert[j].loweight=w[1][i]; } for(k=1;k<n;k++){//循环n-1次，一次确定一条边 //找这条最短边 int min=Max; for(j=2;j<=n;j++){ if(vert[j].loweight<min&&v[j]==0){ min=vert[j].loweight; i=j; } } v[i]=1;//这条边找到了，权重为vert[i].loweight，j顶点加入了V集合， printf("%d->%d %d\n",vert[i].close,i,min); //此时S-V集合顶点i，vert[i].close的值或者还是原值，或者是新加入V的那个顶点，比较即可知道，然后更新 for(j=2;j<=n;j++){ if(w[i][j]<vert[j].loweight&&v[j]==0){ vert[j].loweight=w[i][j]; vert[j].close=i; } } } } int main(){ int i,j,a,b,c; memset(v,0,sizeof(v));//v[i]判断连接顶点i的边是否已经确定，初始化为0，表示还未确定，顶点都在S集合中，若为1，则表示此顶点变到V集合中 scanf("%d%d",&n,&m);//n个顶点，m条边 for(i=0;i<=n;i++){ for(j=0;j<=n;j++){ w[i][j]=Max; } } for(i=0;i<m;i++){ scanf("%d%d%d",&a,&b,&c); w[a][b]=c;//记录顶点a到顶点b的权值 w[b][a]=c;//记录顶点a到顶点b的权值 } prim();//生成树 return 0; }哈哈，希望能有帮助，一起进步
