最小生成树：
概念：在无向图中，连通且不含圈的图称为树。给定无向图 G =（V，E），连接 G 中所有点，且边集是 E 的子集的树称为 G 的生成树，而权值最小的生成树称为最小生成树（MST）。下面就介绍两个算法：Kruskal算法和Prim算法。
Kruskal算法
算法描述：克鲁斯卡尔算法需要对图的边进行访问，所以克鲁斯卡尔算法的时间复杂度只和边又关系。
算法过程：
1.将图各边按照权值进行排序
2.将图遍历一次，找出权值最小的边，（条件：此次找出的边不能和已加入最小生成树集合的边构成环），若符合条件，则加入最小生成树的集合中。不符合条件则继续遍历图，寻找下一个最小权值的边。
3.递归重复步骤1，直到找出n-1条边为止（设图有n个结点，则最小生成树的边数应为n-1条），算法结束。得到的就是此图的最小生成树。
克鲁斯卡尔（Kruskal）算法因为只与边相关，则适合求稀疏图的最小生成树。
如图：
代码（HDU 1233题 还是畅通工程）：
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,m,ans;
int father[105];//记录父亲节点，开始都指向自己
struct zhang
{
int x,y,w;
}t[5009];
bool cmp(const zhang &a,const zhang &b)
{
return a.w < b.w ;//按权值从小到大排序
}
void kruskal()
{
int find(int x);
int x,y,i;
for(i=0;i<m;i++)
{
x=find(t[i].x);
y=find(t[i].y);
if(x!=y)
{
father[x]=y;
ans+=t[i].w;
}
}
}
int find(int x)//查找父亲节点
{
if(father[x]!=x)
x=find(father[x]);
return x;
}
int main()
{
int i;
while(scanf("%d",&n)!=EOF)
{
ans=0;
if(n==0)
break;
m=n*(n-1)/2;
for(i=1;i<=n;i++)
father[i]=i;
for(i=0;i<m;i++)
scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].w);
sort(t,t+m,cmp);
kruskal();
printf("%d\n",ans);
}
return 0;
}
Prim算法
普里姆算法的基本思想：
从图G={V,E}中的某一顶点U0出发，选择与它关联的具有最小权值的边(U0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去，直到图中的所有顶点都加入到生成树顶点集合U中为止。
算法描述：Prim算法需要对图的顶点进行访问，所以Prim算法的时间复杂度只和图中的顶点有关系，所以适合求稠密图的最小生成树。
任意指定一个顶点作为起始点，放在S中(一般选1点)。
每一步将最短的特殊边放入S中，需要n-1步，即可把所有的其他的点放入S中。算法结束。
如图：
代码（NOJ 502题 筹建工程）：
#include<stdio.h>
#include<string.h>
#define INF 9999999
int ans,m,q;
int vis[102],low[102],map[102][102];
void prim()
{
int i,j,k;
for(i=2;i<=m;i++)
low[i]=map[1][i];
vis[1]=1;
q=1;
for(i=2;i<=m;i++)
{
int x=1,min=INF;
for(j=2;j<=m;j++)//寻找最小边
if(!vis[j]&&low[j]<min)
{
x=j;
min=low[j];
}
ans+=min;
if(x==1)
break;
q++;
vis[x]=1;//标记顶点
for(k=2;k<=m;k++)
if(!vis[k]&&low[k]>map[x][k])
low[k]=map[x][k];
}
}
int main()
{
int T,i,j,n,x,y,z;
scanf("%d",&T);
while(T--)
{
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
if(i!=j)
map[i][j]=INF;
else
map[i][j]=0;
for(i=0;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
map[x][y]= map[y][x]=z;
}
ans=0;
prim();
if(q==m)
printf("%d\n",ans);
else
printf("No solution\n");
}
return 0;
}