并查集實作Kruskal算法

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 100      //最大頂點數
#define MAXSIZE 20
#define OK 1
#define ERROR 0
typedef char VertexType;     //頂點
typedef int EdgeType;   //權值
#define INFINITY 65535      /*用65535來代表∞*/
#define UNVISITED -1    //标記未通路
#define VISITED 1   //标記未通路

//并查集時用到
typedef struct parTreeNode
{
    VertexType value;   //頂點(結點)元素
    int nCount; //子樹元素數目
    struct parTreeNode * parent;    //父結點指針
}parTreeNode;



typedef struct
{
    int from;   //邊的始點
    int to; //邊的終點
    EdgeType weight;    //權重
}Edge;  //邊的結構

//圖的結構
typedef struct
{
    int numVertex;  //頂點個數
    int numEdge;    //邊的個數
    parTreeNode vexs[MAXVEX];   /*頂點表*/
    int Indegree[MAXVEX];   //頂點入度
    int Mark[MAXVEX];   //标記是否被通路過
    EdgeType arc[MAXVEX][MAXVEX];   //邊表
    Edge MST[MAXVEX];   //數組MST用于儲存最小生成樹的邊
}Graph;

typedef int Status;
typedef Edge ElemType;  //定義為Edge類型



//最小堆的存儲結構
typedef struct 
{
    ElemType heapArray[MAXSIZE];
    int length;
}MinHeap;


//傳回依附于頂點的第一條邊
Edge FirstEdge(Graph * G,int oneVertex);

//傳回與preEdge有相同頂點的下一條邊
Edge NextEdge(Graph * G,Edge preEdge);

//判斷是否為邊
bool IsEdge(Edge oneEdge);


//傳回node結點的根結點
parTreeNode * Find(parTreeNode * node)
{
    parTreeNode * pointer=node;
    while(pointer->parent!=NULL)
    {
        pointer=pointer->parent;
    }
    return pointer;
}


//判斷結點i和j是否有相同的根結點
bool Different(Graph * G,int i,int j)
{
    parTreeNode * pointer_i=Find(&G->vexs[i]);  //找到結點i的根
    parTreeNode * pointer_j=Find(&G->vexs[j]);  //找的結點j的根
    return pointer_i!=pointer_j;    //若結點i和j的根結點不相同傳回true
}


//合并
void Union(Graph * G,int i,int j)
{
    parTreeNode * pointer_i=Find(&G->vexs[i]);  //找到結點i的根
    parTreeNode * pointer_j=Find(&G->vexs[j]);  //找的結點j的根
    if(pointer_i!=pointer_j)
    {
        if(pointer_i->nCount>=pointer_j->nCount)
        {
            pointer_j->parent=pointer_i;    //把結點i設定為j的父結點
            pointer_i->nCount=pointer_i->nCount+pointer_j->nCount;
        }
        else
        {
            pointer_i->parent=pointer_j;    //把結點j設定為i的父結點
            pointer_j->nCount=pointer_i->nCount+pointer_j->nCount;
        }
    }
}





//初始化堆數組
Status Init_heapArray(Graph * G,MinHeap * M)
{
    for(int i=;i<G->numVertex;i++)
    {
        for(Edge e=FirstEdge(G,i);IsEdge(e);e=NextEdge(G,e))
        {
            if(e.from<e.to) //對于無向圖，防止重複插入邊
            {
                M->heapArray[M->length]=e;
                M->length++;
            }
        }
    }
    return OK;
}



//對最小堆初始化
Status Init_MinHeap(Graph * G,MinHeap * M)
{
    M->length=;
    Init_heapArray(G,M);
    return OK;

}



int MinHeap_Leftchild(int pos)  //傳回左孩子的下标
{
    return *pos+;
}


int MinHeap_Rightchild(int pos) //傳回右孩子的下标
{
    return *pos+;
}


int MinHeap_Parent(int pos) //傳回雙親的下标
{
    return (pos-)/;
}



void MinHeap_SiftDown(MinHeap * M,int left)
{
    int i=left; //辨別父結點
    int j=MinHeap_Leftchild(i); //用于記錄關鍵值較小的子結點
    ElemType temp=M->heapArray[i];  //儲存父結點
    while(j<M->length)  //過篩
    {
        if((j<M->length-)&&(M->heapArray[j].weight>M->heapArray[j+].weight))  //若有右子結點，且小于左子結點
        {
            j++;    //j指向右子結點
        }
        if(temp.weight>M->heapArray[j].weight)  //如果父結點大于子結點的值則交換位置
        {
            M->heapArray[i]=M->heapArray[j];
            i=j;
            j=MinHeap_Leftchild(j);
        }
        else    //堆序性滿足時則跳出
        {
            break;
        }
    }
    M->heapArray[i]=temp;
}


void MinHeap_SiftUp(MinHeap * M,int position)   //從position開始向上調整
{
    int temppos=position;
    ElemType temp=M->heapArray[temppos];    //記錄目前元素
    while((temppos>) && (M->heapArray[MinHeap_Parent(temppos)].weight>temp.weight))    //temppos>0,結束于根結點
    {
        M->heapArray[temppos]=M->heapArray[MinHeap_Parent(temppos)];
        temppos=MinHeap_Parent(temppos);
    }
    M->heapArray[temppos]=temp;
}


void Swap(MinHeap * M,int data1,int data2)
{
    ElemType temp;
    temp=M->heapArray[data1];
    M->heapArray[data1]=M->heapArray[data2];
    M->heapArray[data2]=temp;
}


//建立最小堆
void Create_MinHeap(MinHeap * M)
{
    for(int i=M->length/-;i>=;i--)
    {
        MinHeap_SiftDown(M,i);
    }
}



//删除最小堆的最小值
Status MinHeap_Delete(MinHeap * M,ElemType * MinElem)
{
    if(M->length==)
    {
        printf("不能删除，堆已空！\n");
        return ERROR;
    }
    else
    {

        Swap(M,,--M->length);
        if(M->length>)
        {
            MinHeap_SiftDown(M,);
        }
        *MinElem=M->heapArray[M->length];
        return OK;
    }
}




//初始化圖
void InitGraph(Graph * G,int numVert,int numEd )    //傳入頂點個數,邊數
{
    G->numVertex=numVert;
    G->numEdge=numEd;
    for(int i=;i<numVert;i++)
    {
        G->vexs[i].nCount=;
        G->vexs[i].parent=NULL;
        G->Mark[i]=UNVISITED;
        G->Indegree[i]=;
        for(int j=;j<numVert;j++)
        {
            G->arc[i][j]=INFINITY;
            if(i==j)
            {
                G->arc[i][j]=;
            }
        }
    }
    return ;
}




//判斷是否為邊
bool IsEdge(Edge oneEdge)
{
    if(oneEdge.weight> && oneEdge.weight!=INFINITY && oneEdge.to>=)
    {
        return true;
    }
    else
    {
        return false;
    }
}




//建立有向圖的鄰接矩陣
void CreatGraph(Graph * G)
{
    int i,j,k,w;
    printf("請輸入%d個頂點元素：\n",G->numVertex);
    for(i=;i<G->numVertex;i++)
    {
        scanf(" %c",&G->vexs[i].value);
    }
    for(k=;k<G->numEdge;k++)
    {
        printf("請輸入邊(Vi,Vj)的下标Vi,Vj,和權重w:\n");
        scanf("%d%d%d",&i,&j,&w);
        G->Indegree[j]++;
        G->arc[i][j]=w;
    }
}



//傳回頂點個數
int VerticesNum(Graph * G)
{
    return G->numVertex;
}


//傳回依附于頂點的第一條邊
Edge FirstEdge(Graph * G,int oneVertex)
{
    Edge firstEdge;
    firstEdge.from=oneVertex;
    for(int i=;i<G->numVertex;i++)
    {
        if(G->arc[oneVertex][i]!= && G->arc[oneVertex][i]!=INFINITY)
        {
            firstEdge.to=i;
            firstEdge.weight=G->arc[oneVertex][i];
            break;
        }

    }
    return firstEdge;
}   


//傳回oneEdge的終點
int ToVertex(Edge oneEdge)
{
    return oneEdge.to;
}


//傳回與preEdge有相同頂點的下一條邊
Edge NextEdge(Graph * G,Edge preEdge)
{
    Edge myEdge;
    myEdge.from=preEdge.from;   //邊的始點與preEdge的始點相同
    if(preEdge.to<G->numVertex) //如果preEdge.to+1>=G->numVertex;将不存在下一條邊
        for(int i=preEdge.to+;i<G->numVertex;i++)  //找下一個arc[oneVertex][i]
        {                                           //不為0的i
            if(G->arc[preEdge.from][i]!= && G->arc[preEdge.from][i]!=INFINITY)
            {
                myEdge.to=i;
                myEdge.weight=G->arc[preEdge.from][i];
                break;
            }
        }
        return myEdge;
}



//設定一條邊
Edge Setedge(int from,int to,int weight)
{
    Edge edge;
    edge.from=from;
    edge.to=to;
    edge.weight=weight;
    return edge;
}

void Edge_to_MST(Graph * G,Edge e,int num)
{
    G->MST[num]=e;
}



//列印出MST數組
void Print_MST(Graph * G,int n)
{
    for(int i=;i<n;i++)
    {
        printf("elem:%c->%c   Edge:(%d,%d)  length:%d\n",G->vexs[G->MST[i].from].value,G->vexs[G->MST[i].to].value,G->MST[i].from,G->MST[i].to,G->MST[i].weight);
    }
    printf("\n");
}




void Kruskal(Graph * G,MinHeap * M)
{
    Init_MinHeap(G,M);
    Create_MinHeap(M);
    int MSTtag=;
    int EquNum=G->numVertex;    //開始n個頂點分别作為一個等價類
    while(EquNum>) //當等價類的個數大于1時合并等價類
    {
        Edge e;
        if(M->length!=)    //堆不為空
        {
            MinHeap_Delete(M,&e);   //獲得一條權值最小的邊
        }
            if(M->length== || e.weight==INFINITY)
            {
                printf("不存在最小生成樹！\n");
                return ;
            }
            int from=e.from;
            int to=e.to;
            if(Different(G,from,to))    //邊e的兩個頂點不在一個等價類
            {
                Union(G,from,to);   //将邊e的兩個頂點所在的等價類合并為一個
                Edge_to_MST(G,e,MSTtag++);
                EquNum--;
            }
    }
        Print_MST(G,MSTtag);
}







int main()
{
    Graph G;
    MinHeap M;
    int numVert,numEd;
    printf("請輸入頂點數和邊數：\n");
    scanf("%d%d",&numVert,&numEd);
    InitGraph(&G,numVert,numEd );
    CreatGraph(&G);
    Kruskal(&G,&M);
    return ;
}