克鲁斯卡尔算法的基本思想：
在N个顶点的连通无向网中，在所有未选取的边中，在不构成构成回路的前提下，选最小边，若构成回路，取次小边，直到出现N-1条边。
#include<stdio.h> #include<string.h> #include<stdlib.h> #define Max 999999 int pre[Max],k=0,n,m; struct Egde{ int from,to,v;//from,to代表此边连接的两个结点，v代表第i条边的权值 }egde[Max];//边集 int cmp(const void *a,const void *b){ int aa=((struct Egde *)a)->v; int bb=((struct Egde *)b)->v; return aa-bb; } void addegde(int a,int b,int c){ //加入边集 egde[k].v=c; egde[k].from=a; egde[k].to=b; k++;//第K条边 } int find(int x){//寻找根节点 if(pre[x]==x) return pre[x]; else return pre[x]=find(pre[x]); } kruskal(){ int i; for(i=1;i<=n;i++){ pre[i]=i;//初始化根结点 } int from,to,fom,fto; for(i=0;i<m;i++){ from=egde[i].from; to=egde[i].to; fom=find(from);//寻找根节点 fto=find(to);//寻找根节点 if(fom==fto) continue;//根节点相同，在同一个联通分量上，若再加一条边，则存在回路 else{ printf("(%d %d)\n",from,to); } pre[fto]=pre[fom]; } } int main(){ int a,b,c,i;//n个结点，m条边，a,b表示一条边连接的两个顶点，c表示该边权值 scanf("%d%d",&n,&m); for(i=0;i<m;i++){ scanf("%d%d%d",&a,&b,&c); addegde(a,b,c);//加入边集 } qsort(egde,m,sizeof(egde[0]),cmp);//将边从小到大排序 kruskal();//生成树 }