Kruskal算法的C++语言程序

Kruskal算法是有关图的最小生成树的算法。Kruskal算法是两个经典的最小生成树算法之一，另外一个是PRim算法。

程序来源：Minimum Spanning Tree using Krushkal’s Algorithm。

百度百科：Kruskal算法。

维基百科：Kruskal's Algorithm。

C＋+语言程序：

/* Krushkal's Algorithm to find minimum spanning tree by TheCodersPortal */#include <iostream>#include <map>using namespace std;/* Structure of a Disjoint-Set node */typedef struct dset{    char data;    int rank;    struct dset* parent;}dset;/* To count the number of disjiont sets present at a time */int count=0;/* Map is used to get the address of the node by its data */map <char,dset*> mymap;/* MakeSet function is responsible for creating a disjoint-set whose only member is data,    initially the rank is 0 and it is the representative of itself */void MakeSet(char data){    dset* node=new dset;    node->data=data;    mymap[data]=node;    node->rank=0;    node->parent=node;    count++;}/* FindSetUtil takes input to the pointer to the node and return the pointer to    the representative of that node. A Heuristic is used here, path compression    which means that all the nodes on the find path point directly to the root */dset* FindSetUtil(dset* node){    if(node!=node->parent)        node->parent=FindSetUtil(node->parent);    return node->parent;}/*FindSet function is used to find the node using the data and pass this node to FindSetUtil*/char FindSet(char x){    dset* node=mymap[x];    node=FindSetUtil(node);    return node->data;}/*isconnected checks whether the two elements of the set are connected or not */bool isconnected(char x,char y){    return (FindSet(x)==FindSet(y));}/* LinkSet is responsible for union of two disjoint set according to a Heuristics, Union by Rank */void LinkSet(char x,char y){    if(isconnected(x,y))        return;    dset* node1=mymap[x];    dset* node2=mymap[y];    if(node1->rank>node2->rank)        node2->parent=node1;    else        node1->parent=node2;    if(node1->rank==node2->rank)    {        node1->rank=node1->rank+1;    }    count--;}/* UnionSet calls the LinkSet function with arguments as FindSet(x),FindSet(y) */void UnionSet(char x,char y){    LinkSet(FindSet(x),FindSet(y));}/* freeset is used to free the memory allocated during the run-time */void freeset(char arr[],int n){    for(int i=0;i<n;i++)    {        dset* node=mymap[arr[i]];        delete node;    }}void QuickSort(int array[],int low,int high,char edgein[],char edgeout[]){    int i=low,j=high;    /* Here we are taking pivot as mid element */    int pivot=array[(low+high)/2];    /* Partitioning the array */    while(i<=j)    {        while(array[i]<pivot)            i++;        while(array[j]>pivot)            j--;        if (i<=j)        {            /* Swapping of elements at ith index and jth index */            int temp = array[i];            array[i] = array[j];            array[j] = temp;            char tmp=edgein[i];            edgein[i]=edgein[j];            edgein[j]=tmp;            tmp=edgeout[i];            edgeout[i]=edgeout[j];            edgeout[j]=tmp;            i++;            j--;        }    }    /* Recursion */    if (i<high)        QuickSort(array, i, high,edgein,edgeout);    if (j>low)        QuickSort(array, low, j,edgein, edgeout);}/* MSTKrushkal is the function which is used to find minimum spanning treeusing Krushkal's    Algorithm */void MSTKrushkal(char vertices[],char edgein[],char edgeout[],int weight[],int n,int m){    //int n=sizeof(vertices)/sizeof(vertices[0]);    for(int i=0;i<n;i++)    {        MakeSet(vertices[i]);    }    /*Sorting of edges in non-decreasing order of their weights */    QuickSort(weight,0,m-1,edgein,edgeout);    int A=0;    cout<<"Minimum spanning tree containing edges"<<endl;    for(int i=0;i<9;i++)    {        /* if adding the edge result in cycle, ignore the edge */        if(isconnected(edgein[i],edgeout[i]))            continue;        /* Add the edge to the minimum spanning tree */        UnionSet(edgein[i],edgeout[i]);        A+=weight[i];        cout<<edgein[i]<<"--"<<edgeout[i]<<endl;    }    cout<<"Total weight = "<<A<<endl;    freeset(vertices,n);}/* Driver program to test the above functions */int main(){    /* vertices array contains all the vertices of the graph */    char vertices[]={'A','B','C','D','E','F'};    /* edgein,edgeout and weight array indicates that there is an edge    between vertices edgein[i] and edgeout[i] having weight weight[i] */    char edgein[]={'A','A','A','B','B','C','C','D','D'};    char edgeout[]={'B','D','C','D','E','D','F','E','F'};    int weight[]={6,5,3,8,2,2,6,5,3};    int n=sizeof(vertices)/sizeof(vertices[0]);    int m=sizeof(weight)/sizeof(weight[0]);    MSTKrushkal(vertices,edgein,edgeout,weight,n,m);}程序运行结果：
Minimum spanning tree containing edgesB--EC--DD--FA--CD--ETotal weight = 15