最小生成树之克鲁卡斯尔算法

代码示意：重点有连通集的设计，选择排序，克鲁卡斯尔算法的用法
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef struct{
int start;
int end;
int weight;
}EdgeType;
typedef int FatherType;
typedef struct{
int ne,nv;
FatherType father[30];
EdgeType edge[30];
}Graph;

//创建一个图，其中边的权值为随机函数随机生成。
void Create(Graph &g)
{
    srand(time(0));
    printf("Please input the number of edge and vertex:\n");
    scanf ("%d%d",&g.ne,&g.nv);
    for(int i=0;i<g.ne;i++){
        printf("input the start edge and end edge:\n");
        scanf("%d%d",&g.edge[i].start,&g.edge[i].end);
        g.edge[i].weight=rand()%100+1;
    }
    for(int i=0;i<g.nv;i++){
        g.father[i]=i;
    }
}

//判断同一条边的两个点是否位于同一个集合中，位于同一集合，返回1
int Is_Same_Set(Graph g,int x)
{
    int start,end;
    for(start=g.edge[x].start;start!=g.father[start];start=g.father[start]);
    for(end=g.edge[x].end;end!=g.father[end];end=g.father[end]);
    if(start!=end){
        return 0;
    }
    return 1;
}

 //将两个点合并到一个集合中去
void Merge_Set(Graph &g,int x,int y)
{
    g.father[x]=y;
}

//选择排序算法，按权值大小排序
void Sort(Graph &g)
{
    EdgeType temp;
    int i,j,k,min=100;
    for(i=0;i<g.ne;i++){
        k=i;
        min=100;
        for(j=i;j<g.ne;j++){
            if(min>g.edge[j].weight){
                min=g.edge[j].weight;
                k=j;
            }
        }
        if(k!=i){
            temp=g.edge[k];
            g.edge[k]=g.edge[i];
            g.edge[i]=temp;
        }
    }
}

 //利用克鲁卡斯尔算法构造最小生成树
void MST(Graph g)
{
    int min=0,num=0;
    for(int i=0;i<g.ne&&num<g.nv-1;i++)
    {
        if(!Is_Same_Set(g,i)){
            Merge_Set(g,g.edge[i].start,g.edge[i].end);
        }
        num++;
        printf("the min spanning tree add edge:<%d %d %d>\n",g.edge[i].start,g.edge[i].end,g.edge[i].weight);
        min+=g.edge[i].weight;
    }
    printf("the min spanning tree's cost is %d\n",min);
}
void Print(Graph g)
{
    for(int i=0;i<g.ne;i++){
        printf("%d %d %d\n",g.edge[i].start,g.edge[i].end,g.edge[i].weight);
    }
}
int main()
{
    Graph G;
    Create(G);
    Sort(G);
    printf("the sorted edge following:\n"); 
    Print(G);
    printf("\n");
    MST(G);
}