用Kruskal方法解决无向连通图最小生成树问题：
1所有的点初始化的时候自成一个集合
2所有的边按照权值大小，从小到大排序
3选取权值小的边加入现有集合中，且加入后必须不构成环路，加入后，记录点的祖先
4重复步骤3，直到所有的点都被放入一个集合中
1 /* 2 desription:use Kruskal method to solve mini span tree problem 3 copyright:Hou Shengtao 4 data:2016/12/7 5 */ 6 #include<stdio.h> 7 #include<stdlib.h> 8 #define max 100 9 #define INF 999 10 int edge_num,vertex_num; 11 int p[max];//record SET ID 12 struct edge{ 13 int a; 14 int b; 15 int w; 16 }e[max]; 17 void sort(){ 18 int i,j; 19 20 for(i=1;i<edge_num;i++){ 21 j=i-1; 22 int x=e[i].w; 23 int aa=e[i].a; 24 int bb=e[i].b; 25 26 while(j>=0&&e[j].w>x){ 27 e[j+1].a=e[j].a; 28 e[j+1].b=e[j].b; 29 e[j+1].w=e[j].w; 30 j--; 31 } 32 e[j+1].a=aa; 33 e[j+1].b=bb; 34 e[j+1].w=x; 35 } 36 } 37 //find() use to find the ancester node 38 int find(int x){ 39 return x==p[x]?x:(p[x]=find(p[x])); 40 } 41 //unioned() use to pass the ancester ID to its children 42 //so that all the mini tree vertex have the same ID 43 void unioned(int x,int y){ 44 p[find(x)]=find(y); 45 } 46 void Kruskal(){ 47 //init 48 int i,j; 49 for(i=0;i<vertex_num;i++){ 50 p[i]=i;//init the SET ID 51 } 52 //sorting according to edge's weight 53 sort(); 54 printf(" "); 55 for(i=0,j=0;i<vertex_num&&j<edge_num;i++,j++){ 56 if(find(e[j].a)==find(e[j].b))continue;//form circle,skip 57 58 unioned(e[j].a,e[j].b); 59 60 printf("start:%d end:%d weight:%d ",e[j].a,e[j].b,e[j].w); 61 } 62 } 63 64 int main(){ 65 66 FILE *fin = fopen ("mst.in", "r"); 67 FILE *fout = fopen ("mst.out", "w"); 68 69 char buf[10]; 70 fgets(buf,10,fin); 71 edge_num=atoi(buf); 72 fgets(buf,10,fin); 73 vertex_num=atoi(buf); 74 printf("edge_num:%d ",edge_num); 75 printf("vertex_num:%d ",vertex_num); 76 77 int i; 78 for(i=0;i<edge_num;i++){ 79 int start,end,weight;//start point,end point and the weight of edge 80 fgets(buf,10,fin); 81 sscanf(buf,"%d %d %d",&start,&end,&weight); 82 printf("start:%d end:%d weight:%d ",start,end,weight); 83 e[i].a=start; 84 e[i].b=end; 85 e[i].w=weight; 86 } 87 Kruskal(); 88 89 return 0; 90 }