最小生成樹算法之克魯斯卡爾（Kruskal）算法_修改版

//---Kruskal最小生成樹算法---//
//1. 将各弧存放線上性表Ｌ中，并通過堆排序将其按弧權值從小到大排序
//2.設定集合Ｓ，集合中數組表示圖中的各個頂點
//3.根據線性表Ｌ中各弧的順序，依次選擇各弧，通過判斷各弧所依附頂點是否在集合Ｓ中的同一子集，來判斷是否選擇該弧為生成樹
//4.如果弧所依附的頂點分屬不同的子集，則弧為生成樹的弧，并将兩個頂點所在集合并為同一個集合。
#include <stdio.h>
#include <stdlib.h>
#include "AdjacencyMultilist.h"
#define MAXSIZE 30

typedef struct
{
    ArcNode *r[MAXSIZE+1];
    int length;
}SqList;                 //定義線性表，用于線性存儲弧及對弧進行堆排序
//---定義集合，用于表示圖的各連通分量---//
typedef struct
{
    int parent[MAXSIZE];  //parent的下标表示各頂點（在圖結構中頂點數組的下标），parent的值表示該下标對應的頂點的父結點
    int n;
}MFSet;

void Swap(SqList *L,int low,int high);
void HeapAdjust(SqList *L,int s,int m);
void HeapSort(SqList *L);
int LT(ArcNode *a,ArcNode *b);
void MiniSpanTree_Kruskal(AMLGraph *G);
Status mix_mfset(MFSet *S,int i,int j);
int find_root_in_mfset(MFSet *S,int i);

void Create_ArcSqList_from_Graph(AMLGraph G,SqList *S);
int main()
{
    AMLGraph *G;
    G=(AMLGraph *)malloc(sizeof(AMLGraph));

    CreateAMLGraph(G);
    int i;
    //列印鄰接多重表
    printf("列印鄰接多重表表示的圖結構：\n");
    for(i=0;i<G->vexnum;i++)
    {
        ArcNode *p;
        p=(ArcNode *)malloc(sizeof(ArcNode));
        p=G->vertices[i].firstarc;
        printf("%c: ",G->vertices[i].data);
        while(p)
        {

            int n1,n2;
            n1=p->ivex;
            n2=p->jvex;
            printf("%c---%c ",G->vertices[n1].data,G->vertices[n2].data);
            if(p->ivex==i)
                p=p->ilink;
            else
                p=p->jlink;
        }
        printf("\n");
    }

    MiniSpanTree_Kruskal(G);
    printf("\n");
    return 0;
}
//---Kruskal最小生成樹算法---//
void MiniSpanTree_Kruskal(AMLGraph *G)
{
    int i;
    MFSet *S;
    S=(MFSet *)malloc(sizeof(MFSet));
    for(i=0;i<G->vexnum;i++)
        S->parent[i]=-1; //頂點的parent均設為－１
    S->n=G->vexnum;

    SqList *L;
    L=(SqList *)malloc(sizeof(SqList));
    L->length=0;
    Create_ArcSqList_from_Graph(*G,L);  //将各條弧放入線性表L中
    HeapSort(L);          //對線性表中的各條弧進行堆排序，使其按從小到大排列
    printf("堆排序後的各弧：");
    for(i=1;i<=L->length;i++)
        printf("%d ",*(L->r[i]->info));
    //Kruskal算法思想
    printf("\n最小生成樹所包含的弧：");
    for(i=1;i<=L->length;i++)
    {
        int vex1,vex2;
        vex1=L->r[i]->ivex;  //目前弧所指向的兩個頂點
        vex2=L->r[i]->jvex;

        if(find_root_in_mfset(S,vex1)!=find_root_in_mfset(S,vex2))  //如果目前弧所指向的兩個頂點不在同一子集，則該弧為生成樹的弧
        {
            mix_mfset(S,vex1,vex2);                 //将兩個頂點所在子集合并
            printf("%c----%c ",G->vertices[vex1].data,G->vertices[vex2].data);//列印目前弧
        }
    }
}
//---從圖Ｇ中生成表示各弧的線性表，用于堆排序---//
void Create_ArcSqList_from_Graph(AMLGraph G,SqList *S)
{
    int i;
    for(i=0;i<G.vexnum;i++)
    {
        ArcNode *p;
        p=(ArcNode *)malloc(sizeof(ArcNode));

        p=G.vertices[i].firstarc;
        while(p)
        {
            p->mark=unvisited;  //将各弧結點的mark标記為未被通路，
            p=p->ilink;         //用于避免下一個for循環中不會重複将同一條弧放入線性表中
        }
        free(p);
    }
    for(i=0;i<G.vexnum;i++)
    {
        ArcNode *t;
        t=(ArcNode *)malloc(sizeof(ArcNode));

        t=G.vertices[i].firstarc;
        while(t)
        {
            if(t->mark==unvisited)
            {
                t->mark=visited;
                S->r[++S->length]=t;  //由于堆排序中需用到“結點i的左子結點為2i、右子結點為2i+1”，是以線性表須從１開始表示第一個結點
            }
            t=t->ilink;
        }
        free(t);
    }
}
/*堆排序：即使最壞情況下，時間複雜度為nlogn*/
/*篩選：即s至m序列中，除s外均滿足堆定義，将s自頂向下調整，以滿足堆定義*/
void HeapAdjust(SqList *L,int s,int m)
{
    int j;
    ArcNode *rc;
    rc=L->r[s];
    for(j=2*s;j<=m;j*=2)
    {
        if(j<m && LT(L->r[j],L->r[j+1]))  //比較左、右孩子結點j和j+1，将j改為較大結點（如果右孩子大，則j增１即為右孩子）
            j++;
        if(!LT(rc,L->r[j]))   //比較目前結點s和左、右孩子結點中的較大者j
            break;            //如果結點s不是更小，則表明符合大堆定義，不必再往下繼續
        L->r[s]=L->r[j];      //如果結點s更小，則
        s=j;
    }
    L->r[s]=rc;
}
void HeapSort(SqList *L)
{
    int i;
    for(i=L->length/2;i>0;i--)
        HeapAdjust(L,i,L->length);
    for(i=L->length;i>1;i--)
    {
        Swap(L,1,i);
        HeapAdjust(L,1,i-1);
    }
}
void Swap(SqList *L,int low,int high)
{
    ArcNode *t;
    t=(ArcNode *)malloc(sizeof(ArcNode));
    t=L->r[low];
    L->r[low]=L->r[high];
    L->r[high]=t;
}
int LT(ArcNode *a,ArcNode *b)
{
    return *(a->info)<*(b->info);
}
//---合并結點i和結點j所在的集合---//
Status mix_mfset(MFSet *S,int i,int j)
{
    int root_i,root_j;
    root_i=find_root_in_mfset(S,i);     //找到結點i的所在子集的根結點
    root_j=find_root_in_mfset(S,j);     //找到結點j的所在子集的根結點
    //開始合并集合
    if(S->parent[root_i]>S->parent[root_j])  //如果結點i所在集合結點數量少，則将結點i的雙親parent指向結點j所在子集的根結點
    {
        S->parent[root_j]+=S->parent[root_i];//并将結點j所在子集的根結點的parent(表示子集結點數量)相應更改
        S->parent[root_i]=root_j;            //将結點i所在子集的根結點指向j所在子集的根結點，即為合并
    }
    else
    {
        S->parent[root_i]+=S->parent[root_j];//反之，将結點i所在子集的根結點的parent(表示子集結點數量)相應更改
        S->parent[root_j]=root_i;            将結點j所在子集的根結點指向i所在子集的根結點，即為合并
    }
    return OK;
}
//---尋找結點i所在子集的根結點，通過根結點的資料域來區分各集合---//
int find_root_in_mfset(MFSet *S,int i)
{
    int j;
    j=i;
    while(S->parent[j]>=0)   //當j的parent小于０時，則表明j就是根結點
        j=S->parent[j];

    return j;
}