Kruskal算法的基本思想是以边为主导的地位，始终都是选择当前可用的最小权值的边。具体实现如下：
(1)设一个有n个顶点的连通网络G（V,E），最初先构造一个只有n个顶点，没有边的非连通图T={V,Ø}，图中每个顶点自成一个连通分量。
(2)当在E中选择一条具有最小权值的边时，若该边的两个顶点落在不同的连通分量上，则将此边加入T中。否则，即这两条边落在同一连通分量上，则将此边舍弃（以后永不再用），重新选择一条权值最小的边。
(3)如此重复下去，直到所有顶点在同一个连通分量上为止。
例题：如图所示，求最小生成树，并输出依次选择的各条边及最终求得的最小生成树的权
测试数据
输入：
7 9
1 2 28
1 6 10
2 3 16
2 7 14
3 4 12
4 5 22
4 7 18
5 6 25
5 7 24
输出：
1 6 10
3 4 12
2 7 14
2 3 16
4 5 22
5 6 25
weight of MST is 99
#include<cstdio>#include<iostream>#include<algorithm>using namespace std;#define MAXN 110#define MAXM 110struct edge{int u,v,w;}edges[MAXN];int parent[MAXN];int n,m;int i,j;void UFset(){for(i=0;i<n;i++)parent[i]=-1;}int Find(int x){int s;for(s=x;parent[s]>=0;s=parent[s]);while(s!=x){int temp=parent[x];parent[x]=s;x=temp;}return s;}void Union(int R1,int R2){int r1=Find(R1),r2=Find(R2);int temp=parent[r1]+parent[r2];if(parent[r1]>parent[r2]){parent[r1]=r2;parent[r2]=temp;}else{parent[r2]=r1;parent[r1]=temp;}}bool cmp(edge a,edge b)///比较函数{return a.w<b.w;}void Kruskal(){int sumweight=0;///生成树的权值int num=0;///已选用的边的数量int u,v; ///选用边的两个顶点UFset();for(i=0;i<m;i++)///一条边一条地从小到大排查，直到生成最小生成树{u=edges[i].u;v=edges[i].v;if(Find(u)!=Find(v)){printf("%d %d %d\n",u,v,edges[i].w);sumweight+=edges[i].w; num++;Union(u,v);}if(num>=n-1) break;}printf("weight of MST is %d\n",sumweight);}int main(){int u,v,w;while(scanf("%d%d",&n,&m)!=EOF){for(i=0;i<m;i++){scanf("%d%d%d",&u,&v,&w);edges[i].u=u;edges[i].v=v;edges[i].w=w;}sort(edges,edges+m,cmp);///按照权值从小到大排序Kruskal();}}
