1、kruscal
模板：
//kruskal 算法
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int per[105],n;
struct node//结构体来保存边
{int a,b;int dis;
}x[5005];
bool cmp(node a,node b)
{return a.dis<b.dis;
}
void init()//初始化操作
{for(int i=1;i<=n;++i){per[i]=i;}
}
int find(int x)//并查集的查找操作
{int r=x;while(r!=per[r]){r=per[r];}int i=x,j;while(i!=r){j=per[i];per[i]=r;i=j;}return r;
}
bool join(int a,int b)//判断某条边是否可以选择
{int x=find(a),y=find(b);if(x!=y){per[y]=x;return 1;}return 0;
}int main()
{int a,b,c,m;while(scanf("%d",&n),n){init();m=n*(n-1)/2;for(int i=0;i<m;++i){scanf("%d%d%d",&a,&b,&c);x[i].a=a;x[i].b=b;x[i].dis=c;}sort(x,x+m,cmp);//对边进行排序int sum=0,cnt=0;for(int i=0;cnt<n-1;++i)//依次选择使得所有顶点连通的边{if(join(x[i].a,x[i].b)){sum+=x[i].dis;++cnt;}}printf("%d\n",sum);//输出最小生成树的权值}return 0;
}
2、prim算法：<pre name="code" class="cpp">#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int map[105][105];
int prim(int n)
{int vis[105]={0},dis[105],ans=0;memset(dis,inf,sizeof(dis));//初始化为无穷大 dis[1]=0;//随意选定一个点开始 for(int i=1;i<=n;++i)//循环加入n个顶点 {int k=-1,tp=inf; for(int j=1;j<=n;++j)//查找距离已连接的部分最近的顶点 {if(!vis[j]&&dis[j]<tp){k=j;tp=dis[j];}}vis[k]=1;ans+=tp;//统计和标记 for(int j=1;j<=n;++j)//更新未选中的点和已经连接的部分之间的最短距离 {if(!vis[j]&&map[k][j]<dis[j]){dis[j]=map[k][j];}}}return ans;
}
int main()
{int n,m,a,b,c;while(scanf("%d",&n)&&n){memset(map,inf,sizeof(map));m=n*(n-1)/2;//边的数量 for(int i=0;i<m;i++){scanf("%d%d%d",&a,&b,&c);map[a][b]=map[b][a]=c;//无向边 }printf("%d\n",prim(n));}return 0;
}