最小生成树是树的一种，具体有两种算法去实现。
普利姆（prim)算法：
大意：先找一个数（一般为1或输入的的一个数）将其视为一个集合m，那么剩下的集合可看做（u（设为总集合）-m）。
接着找出一个最短边（在连接两个集合的边中），然后将这边归入集合m，直到m=u；
例子：
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最小的公路总长度。
Sample Input
3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0
Sample Output
3 5
code：
#include <stdio.h>
#include <string.h>
#define MaxInt 65535//设置最大值 表示两个点不通
#define N 110
int map[N][N],low[N],visited[N];
int n;
int prim()
{
int i,j,pos,min,result=0;
memset(visited,0,sizeof(visited));
visited[1]=1;//遍历过就标记为一
pos=1;//记录m集合的“外交官”
for(i=1; i<=n; i++)
if(i!=pos)
low[i]=map[pos][i];//记录和pos点边距离的值
for(i=1; i<n; i++)//当然要算的是整个顶点
{
min=MaxInt;
for(j=1; j<=n; j++)
if(visited[j]==0&&min>low[j])
{
min=low[j];
pos=j;
}//找出最短边
result+=min;
visited[pos]=1;//纳入m集合.
for(j=1; j<=n; j++)
if(visited[j]==0&&low[j]>map[pos][j])
low[j]=map[pos][j];//记录和pos点边距离的值
}
return result;
}
int main()
{
int i,v,j,ans,a,b;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
break;
memset(map,MaxInt,sizeof(map));//初始值 视每两个点都不通
for(j=1; j<=n*(n-1)/2; j++)
{
scanf("%d%d%d",&a,&b,&v);
map[a][b]=map[b][a]=v;//标记两个城市间的距离
}
ans=prim();
printf("%d\n",ans);
}
return 0;
}
2 克鲁斯卡尔（kruskal）算法：
大意：
我们假设一个图有m个节点，n条边。首先，我们需要把m个节点看成m个独立的生成树，并且把n条边按照从小到大的数据进行排列。在n条边中，我们依次取出其中的每一条边，如果发现边的两个节点分别位于两棵树上，那么把两棵树合并成为一颗树；如果树的两个节点位于同一棵树上，那么忽略这条边，继续运行。等到所有的边都遍历结束之后，如果所有的生成树可以合并成一条生成树，那么它就是我们需要寻找的最小生成树，反之则没有最小生成树。ps 要用并查集的思想
例题：
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最小的公路总长度。
Sample Input
3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0
Sample Output
3 5
code：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define M 5000
int Start[M],End[M],Wealth[M],father[M],line[M];
int find_(int f)//查找父节点
{
if(f!=father[f])
return father[f]=find_(father[f]);
return f;
}
int cmp(const int i,const int j)//sort排序要加的东西，具体啥用不清楚。。。
{
if(Wealth[i]!=Wealth[j])
return Wealth[i]<Wealth[j];//按边值排序
}
int kruskal(int n,int m)//具体实现步骤
{
int e,ans=0,i,j,x,y;
for(i=0;i<=n;i++)//初始化为单一集合
father[i]=i;
for(i=0;i<=m;i++)
line[i]=i;
sort(line,line+m,cmp);//按边值排序
for(i=0;i<m;i++)
{
e=line[i],x=find_(Start[e]),y=find_(End[e]);
if(x!=y)//判断是否两个节点位于同一个树上
{
father[x]=y;
ans+=Wealth[e];
}
}
return ans;
}
int main()
{
int n,m,i,p;
while(1)
{
scanf("%d",&n);
if(n==0)
break;
m=n*(n-1)/2;
for(i=0;i<m;i++)
scanf("%d%d%d",&Start[i],&End[i],&Wealth[i]);
p=kruskal(n,m);
printf("%d\n",p);
}
}
总结：
1.普里姆（Prim)算法原文：http://my.oschina.net/u/1762578/blog/293212