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

1. 适用范围:

1. 稀疏图中求最小生成树

2. 算法思想梗概:

1. 保证不产生环的前提下, 在图中选出权值最小的, 顶点总数-1, 条边作为最小生成树的边

3. 在c语言中的实现:

梗概:

1. 每纳入一条边前, 先判断是否会形成环
2. use::判断是否形成环 代码:

typedef struct {
    int start;
    int end;
    int weight;
}Edge;
Edge MinEdges[MAX_VERTEX_NUM];
int get_edges(Graph *G,Edge edges[]){}
void sort_edges(Edge edges[],int edgenum){}
int Kruskal(Graph *G, Edge MinEdges[]){
//把最小生成树的边都保存到MinEdges数组中
    int i,n,m,k;
    /*保存所生成树的所有边*/
    Edge edges[MAX_VERTEX_NUM];
    /*借助并查集*/
    int parent[MAX_VERTEX_NUM];
    /*获取图中所有边的所需信息*/
    get_edges(G,edges);
    /*升序排序*/
    sort_edges(edges,G->arcnum);
    /*初始并查集*/
    for(i=0;i<G->vexnum;++i)
        parent[i]=-1;
    k=0;
    for(i=0;i<G->arcnum;++i){
        /*用并查集判断两顶点是否在同一颗树*/
        n=Find(edges[i].start,parent);
        m=Find(edges[i].end,parent);
        if(n!=m){
            parent[n]=m;//两顶点合为一个集
            /*该边纳入生成树中*/
            MinEdges[k].start=edges[i].start;
            MinEdges[k].end=edges[i].end;
            MinEdges[k].weight=edges[i].weight;
            ++k;
            /*最小生成树条件达成*/
            if(k==G->vexnum-1)return 1;
        }
    }
    /*图中的边不足以生成树*/
    if(k<G->vexnum-1)return 0;
}