并查集的最小生成树算法

摘要
   树结构实现得并查集数据结构，用来求无向图的最小生成树。
   基本操作：
   0. 根据弧的权值对图的所有弧进行排序，设弧的数目为e， 使用归并排序，排序复杂度 log(eloge)
   1. 设无向图共有N个结点，初始化N棵树，树的根代表图的一个结点。
   2. 从小到大考察每一条弧，如果弧的两个结点在不同一棵树上，则合并这两树。否则跳过这条弧，考察下一条弧。
      合并的原则是将“小树“(树的深度小)合并到“大树“ , 复杂度 O(1)
      判断两个结点是否在同一颗树上需要从某个结点向上遍历至树根，因为只有树根存储集合号。把这个操作称为 Union_Find (int nodeIndex);
      在便利的同时，将每一个便利过的结点直接指向树根，这样可以减少下一次 Union_Find () 的时间。这样Union_Find的复杂度可以从O(logn)降低到O(G(n)); 做此操作带来的附加难度是需要在Union_Find后更新树的高度。

关键字
   并查集，树结构，最小生成树

联系作者：
   如果发现任何的bug，请发信到yaming.kuang@gmail.com;

文件结构
graph.h          实现图的头文件, 定义图的数据结构 - 邻接表；
graph.cpp        定义图构造函数，对弧的排序函数（归并排序）。
MiniSpanTree_Kruskal_TreeImpl.cpp  实现Union_Find等操作，文件内对每个函数的注释已经很清楚了。
MiniSpanTree_Kruskal_TreeImpl.h    实现树结构时显得并查集的树集结构，文件内注释已经很清楚了。
main.cpp         测试函数

/******************************************************************************/
/********************************* file: graph.h ******************************/
/******************************************************************************/

#ifndef __GRAPHH__
#define __GRAPHH__

const int  MAX_VERTEX_NUM = 30;
typedef enum { DG, AG } GraphKind;  // { Digraph, Undigraph}
/*
 * Adjacency List.
 * */
typedef int ArcInfoType ;            // The weight of arc
typedef struct ArcNode{             // Arc Node
    int             adjvex;         // The Node pointed by this arc.
    struct ArcNode *nextarc;        // Point to next arc.
    ArcInfoType     weight;           // Info about this arc. e.g. weight of this arc.
}ArcNode;

typedef int VertexType;            // The index of Vertex Node.
typedef struct VNode{               // Vertex Node
    VertexType      data;           // Info of node
    ArcNode        *firstarc;       // Point to the first arc originates from this Vertex.
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct{
    AdjList     vertices;           //
    int         vexnum, arcnum;     // Number of vertex and arc.
    GraphKind   kind;               // The kind of this graph.
}ALGraph;

typedef struct ArcGraph{
    int             VStart;
    int             VEnd;     
    ArcInfoType     weight;           // Info about this arc.
}ArcGraph;

ALGraph* CreateALGraph ();
ArcGraph* GetArcsToArray (ALGraph *graph);
void SortArcs (ArcGraph *arcGraph, int numArcs );
void MergeSort_ArcGraph (ArcGraph *E, int first, int last);
void Merge_ArcGraph (ArcGraph *E, int first, int mid, int last);
void PrintArcGraph (ArcGraph *arcGraph, int numArcs);

#endif

/*************************  end of file: graph.h ******************************/


/******************************************************************************/
/********************************* file: graph.cpp ******************************/
/******************************************************************************/

#include <iostream>
#include "graph.h"
using namespace std;

/*
 * Func Name    :  CreateALGraph   
 * Desc         :  Create an Adjacency List Graph.
 * Input        :   
 *      - graph    
 * Output       :   
 *      -
 * Return Value :  None
 * Remarks      :  None
 * */
ALGraph* CreateALGraph (){
     cout << "CreateALGraph" << endl;
     ALGraph *graph = new ALGraph;
     graph->vexnum = 8;   
     graph->arcnum = 17;
     graph->kind   = AG;

     // Create Adjacency List for node 1
     ArcNode **pArc = &(graph->vertices[0].firstarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 1;  // 1->2
     (*pArc)->weight = 6;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 2;  // 1->3
     (*pArc)->weight = 1;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 3;  // 1->4
     (*pArc)->weight = 5;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 7;  // 1->8
     (*pArc)->weight = 9;

     (*pArc)->nextarc = NULL;

     // Create Adjacency List for node 2
     pArc = &(graph->vertices[1].firstarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 0;  // 2->1
     (*pArc)->weight = 6;
    
     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 2;  // 2->3
     (*pArc)->weight = 5;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 4;  // 2->5
     (*pArc)->weight = 3;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 7;  // 2->8
     (*pArc)->weight = 6;

     (*pArc)->nextarc = NULL;

     // Create Adjacency List for node 3
     pArc = &(graph->vertices[2].firstarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 0;  // 3->1
     (*pArc)->weight = 1;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 1;  // 3->2
     (*pArc)->weight = 5;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 3;  // 3->4
     (*pArc)->weight = 5;
    
     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 4;  // 3->5
     (*pArc)->weight = 6;
    
     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 5;  // 3->6
     (*pArc)->weight = 4;

     (*pArc)->nextarc = NULL;
    
     // Create Adjacency List for node 4
     pArc = &(graph->vertices[3].firstarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 0;  // 4->1
     (*pArc)->weight = 5;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 2;  // 4->3
     (*pArc)->weight = 5;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 5;  // 4->6
     (*pArc)->weight = 2;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 6;  // 4->7
     (*pArc)->weight = 8;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 7;  // 4->8
     (*pArc)->weight = 5;

     (*pArc)->nextarc = NULL;

     // Create Adjacency List for node 5
     pArc = &(graph->vertices[4].firstarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 1;  // 5->2
     (*pArc)->weight = 3;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 2;  // 5->3
     (*pArc)->weight = 6;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 5;  // 5->6
     (*pArc)->weight = 6;
    
     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 6;  // 5->7
     (*pArc)->weight = 6;

     (*pArc)->nextarc = NULL;
   
     // Create Adjacency List for node 6
     pArc = &(graph->vertices[5].firstarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 2;  // 6->3
     (*pArc)->weight = 4;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 3;  // 6->4
     (*pArc)->weight = 2;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 4;  // 6->5
     (*pArc)->weight = 6;
    
     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 6;  // 6->7
     (*pArc)->weight = 10;

     (*pArc)->nextarc = NULL;
   
     // Create Adjacency List for node 7
     pArc = &(graph->vertices[6].firstarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 3;  // 7->4
     (*pArc)->weight = 8;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 4;  // 7->5
     (*pArc)->weight = 3;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 5;  // 7->6
     (*pArc)->weight = 10;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 7;  // 7->8
     (*pArc)->weight = 4;

     (*pArc)->nextarc = NULL;

     // Create Adjacency List for node 8
     pArc = &(graph->vertices[7].firstarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 0;  // 8->1
     (*pArc)->weight = 9;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 1;  // 8->2
     (*pArc)->weight = 6;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 3;  // 8->4
     (*pArc)->weight = 5;

     pArc = &((*pArc)->nextarc);
     *pArc = new ArcNode;
     (*pArc)->adjvex = 6;  // 8->7
     (*pArc)->weight = 4;

     (*pArc)->nextarc = NULL;
     return graph;
}

/*
 * Func Name    :  GetArcsToArray
 * Desc         :  
 *      Retrieve all the arcs in graph.
 *      arcGraph is an unsorted array. SortArcs will be called to sort the arcs by weight.
 * Input        :  
 *      - graph     The graph that we want to retrieve arcs from.
 * Output       :  
 *      -
 * Return Value :  The allocated array ArcGraph that has arcs copied from graph.
 * Remarks      :  None
 * */
ArcGraph* GetArcsToArray (ALGraph *graph){
    cout << "GetArcsToArray" << endl;
    int numArcs = graph->arcnum;
    int i,j;
    ArcGraph *arcGraph = new ArcGraph[numArcs];

    for (i = 0, j = 0; i < graph->vexnum && j < numArcs; i++){
        ArcNode *pArcNode = graph->vertices[i].firstarc;
        while(pArcNode)
        {
            if (pArcNode->adjvex > i)
            {
               arcGraph[j].VStart = i;
               arcGraph[j].VEnd   = pArcNode->adjvex;
               arcGraph[j].weight = pArcNode->weight;
               j++;
            }
            pArcNode = pArcNode->nextarc;
        }
    }

    PrintArcGraph (arcGraph, numArcs);
    return arcGraph;
}


/*
 * Func Name    :  SortArcs 
 * Desc         :  
 *      Sort the arcs by weight.
 *      arcGraph is sorted for those application who want to loop arcs by weight.
 *      The complexity should be less than O(nlogn);
 * Input        :  
 *      - arcGraph  The array that has unsorted arcs. 
 *      - numArcs   The number of arcs.
 * Output       :  
 *      - arcGraph  The sorted array.
 * Return Value :  None
 * Remarkg      :  None
 * */
void SortArcs ( ArcGraph *arcGraph, int numArcs ){
    // Use classic sorting algrithm to sort arcs.
    MergeSort_ArcGraph (arcGraph, 0, numArcs-1);
    cout << "After Merge Sort for arcs with weight:"<< endl;
    PrintArcGraph (arcGraph, numArcs);
}

void MergeSort_ArcGraph (ArcGraph *E, int first, int last)
{
   if (first < last)
   {
      int mid = ( first + last )/2;
      MergeSort_ArcGraph (E, first, mid);    // MergeSort E form E[first] to E[mid];
      MergeSort_ArcGraph (E, mid+1, last);   // MergeSort E from E[mid+1] to E[last];
      // Merge the sorted sub sequence E[first]...E[mid] and E[mid+1]...E[last] into a whole sequenced array E;
      Merge_ArcGraph (E, first, mid, last); 
   }
   return;

}

void Merge_ArcGraph (ArcGraph *E, int first, int mid, int last)
{
   // Merge the sorted sub sequence E[first]...E[mid] and E[mid+1]...E[last] into array E;
   ArcGraph * pE = 0;
   int i, j, k;
   pE = new ArcGraph[last - first + 1];

   for (i = first, j = mid+1, k = 0; (i <= mid) && (j <= last); )
   {
       if (E[i].weight < E[j].weight)
           pE[k++] = E[i++];
       else
           pE[k++] = E[j++];
   }
  
   if ( i > mid )
   {
       if ( j <= last )
        for ( ; j <= last ; k++, j++)
            pE[k] = E[j];
   }
   else if ( j > last )
   {
       if ( i <= mid )
           for ( ; i <= mid; k++, i++ )
               pE[k] = E[i];
   }
   for ( i = first, k = 0; i <= last; i++,k++ )
       E[i] = pE[k];

   delete []pE;
   return;
}

void PrintArcGraph (ArcGraph *arcGraph, int numArcs)
{
    int i;
    for (i = 0; i < numArcs; i++)
    {
        cout << "arcGraph["<<i<<"]: VStart: "<<arcGraph[i].VStart<<", VEnd: "<< arcGraph[i].VEnd<<", weight: "<< arcGraph[i].weight<< endl;  
    }

    return;
}
/************************** end of file: graph.cpp *****************************/

/*******************************************************************************/
/***************** file: MiniSpanTree_Kruskal_TreeImpl.h ***********************/
/*******************************************************************************/
#ifndef __MINISPANTREE_KRUSKAL_TREEIMPL_H___
#define __MINISPANTREE_KRUSKAL_TREEIMPL_H___

#include "graph.h"

/* **************************************************************************
 *
 *           Dynamic Set Structure - Tree Implementation
 *
 *            Index: 0   1   2   ...  
 *           ________________________   Data - data, parent, setID,numChilds, memCtrl, height.
 *          | Data | P | C1 | C2 | ^ |  parChildrenArray: P   - Pointer to Parent Node.
 *          |______|___|____|____|___|                    C1  - Pointer to 1st Child
 *                       /      \                         C2  - Pointer to 2nd Child
 *                     /          \                       C3  - NULL. End of child.
 *                   /              \   The size of parChildrenArray is increased dynamically. 
 *                 /                  \ This is to same memery and enhance memery allocation performence.
 *   _________________________     __________________
 *  | data | P | C1 | C2 | ^ |    |data| P | C1 | ^ |
 *  |______|___|____|____|___|    |____|___|____|___|
 *           ...       ...                    ...                   
 *         ...           ...                    ...
 *       ...               ...                     ...
 *
 *
 * **************************************************************************/

const int MAX_TREE_SIZE   = 1000;
const int INIT_TREE_SIZE  = 1;
typedef int TElemType;
typedef struct PTNode{
    TElemType       data;
    int             parent;             // Index of parent node.
    unsigned int    setID;              // only valid if this is root
    int             numChilds;
    int             memCtrl;            // Memery Control;
    int             height;             // The height of this tree. Consider this node as root node.
    struct PTNode **parChildrenArray;   // pointer array.
}PTNode;

typedef int TDynSetElemType;
typedef struct TDynamicSetElem{
    TDynSetElemType  *data;
    PTNode           *node;      // The node of this elem.
}TDynamicSetElem;

typedef int TDynamicSetDataType;
typedef struct TDynamicSet{
    TDynamicSetDataType    *data;
    PTNode                 *root;
}TDynamicSet;

typedef struct TDynamicSetCP{
    TDynamicSetElem        *allSetsElemArray;
    unsigned int            numAllSetsElems;
    TDynamicSet            *sets;
    unsigned int            numSets;
}TDynamicSetCP;

/******************************************************************************/

TDynamicSetCP* CreateTDynSetsCP (ALGraph *graph);
TDynamicSetCP* MiniSpanTree_Kruskal_Tree (ALGraph *grapha);
void InitTDynamicSets (TDynamicSetCP *dynSetsCP, int numSets);
void TMergeSet (TDynamicSetCP *dynSetsCP, ArcGraph *arcGraph, int curArc);
void TDoMergeSet (TDynamicSetCP *dynSetsCP, int setID1, int setID2);
int  Union_Find (TDynamicSetCP *dynSetsCP, int elemIndex);
void AddChildToNode (PTNode *parent, PTNode *child);
void UpdateTreeHeight (PTNode *oldParent, PTNode *delNode);
#endif

/************* end of file: MiniSpanTree_Kruskal_TreeImpl.h ********************/

/*******************************************************************************/
/************ file: MiniSpanTree_Kruskal_TreeImpl.cpp **************************/
/*******************************************************************************/
#include <iostream>
#include "MiniSpanTree_Kruskal_TreeImpl.h"
#include "graph.h"
using namespace std;

typedef PTNode *PPTNode;

TDynamicSetCP* MiniSpanTree_Kruskal_Tree (ALGraph *graph)
{
    ArcGraph *arcGraph;
    arcGraph = GetArcsToArray (graph);   // Memery allocated in GetArcsToArray;
    SortArcs (arcGraph, graph->arcnum);  // Sort the arcs and store it in arcGraph

    TDynamicSetCP *dynSetsCP;             // The Dynamic Set Control Point
    dynSetsCP = CreateTDynSetsCP (graph);
    // Init all the dynamic sets.
    InitTDynamicSets (dynSetsCP, graph->vexnum);
   
    int curArc;
    for (curArc = 0; curArc < graph->arcnum && dynSetsCP->numSets > 1; curArc++)
    {
        TMergeSet (dynSetsCP, arcGraph, curArc);
    }
    return dynSetsCP;
}

void TMergeSet (TDynamicSetCP *dynSetsCP, ArcGraph *arcGraph, int curArc)
{
    int elemIndex1 = arcGraph[curArc].VStart;
    int elemIndex2 = arcGraph[curArc].VEnd;
    int setID1, setID2;
   
    setID1 = Union_Find (dynSetsCP, elemIndex1);
    setID2 = Union_Find (dynSetsCP, elemIndex2);

    // Check if it really need to merge.
    if ( setID1 != setID2 )
    {
        TDoMergeSet (dynSetsCP, setID1, setID2);
        cout<< "arc: "<< elemIndex1 + 1 <<" <-> "<<elemIndex2 + 1<<" Added. "
            << "Arc Weight: "<<arcGraph[curArc].weight<<endl;
    }
    return;
}

/*
 * Func Name    :  Union_Find  
 * Desc         : 
 *                 O(h) = O(log n) ;  h is height of tree,
 *                 When loop from bottom to root node, we could let each node point directly to root.
 *                 This will reduce the Uion_Find complexity for other nodes.
 * Input        :  
 *      -
 * Output       :  
 *      -
 * Return Value :  
 * Remarks      :  
 * */
int Union_Find (TDynamicSetCP *dynSetsCP, int elemIndex)
{
    int setID;
    PTNode *pnode = dynSetsCP->allSetsElemArray[elemIndex].node;
    while (pnode->parChildrenArray[0])
    {
        pnode = pnode->parChildrenArray[0];
    }
    setID = pnode->setID;

    /* Support optimization of Union_Find */
    PTNode *root = pnode;
    pnode = dynSetsCP->allSetsElemArray[elemIndex].node;
    while (pnode->parChildrenArray[0])
    {
        PTNode *oldParent = pnode->parChildrenArray[0];
        AddChildToNode (root, pnode); // Add pnode as child of root. 
       
        // pnode is the deleted node, update oldParent child and height.
        UpdateTreeHeight (oldParent, pnode);
        pnode = oldParent;     // Go on
    }

    return setID;
}

/*
 *  Update the oldParent->parChildrenArray since delNode is deleted.
 *  1) If delNode is in index i, then move index i+1,...,numChilds forward, and decrease numChilds by 1.
 *  2) Update the height of oldParent if the deleted node is the highest node.
 * */
void UpdateTreeHeight (PTNode *oldParent, PTNode *delNode)
{
    if ( oldParent == delNode->parChildrenArray[0] )
    {
        /* oldParent is still delNode's parent,
         * AddChildToNode didn't actually remove delNode from oldParent to new parent.
         * so do not need to do anything. */
        return;
    }
   
    // Update children list and Height.
    int i,j;
    int numChilds = oldParent->numChilds;
    int maxHeightOfChildren = 0;   // Record the max height of other children.
    /* The height of the deleted one.
     * The */
    int delNodeHeight = delNode->height;
    for (i = 1; i <= numChilds; i++)
    {
        int height = oldParent->parChildrenArray[i]->height;
        if (oldParent->parChildrenArray[i] != delNode)
        {
            if (height > maxHeightOfChildren)
                maxHeightOfChildren = height;
        }
        else  // oldParent->parChildrenArray[i] == delNode
        {
            for (j = i; j < numChilds; j++)
            {
                int height = oldParent->parChildrenArray[j]->height;
                oldParent->parChildrenArray[j] = oldParent->parChildrenArray[j+1];
                if (height > maxHeightOfChildren)
                    maxHeightOfChildren = height;
            }
            oldParent->parChildrenArray[numChilds] = NULL;
            oldParent->numChilds--;
            break;
        }
    }
   
    /* Update the height of oldParent if the deleted node is the heighest child.*/
    if (maxHeightOfChildren < delNodeHeight)
        oldParent->height = maxHeightOfChildren;
}

/*
 * 1. Add child to parent.
 *    Increase parent->parChildrenArray if needed.
 * 2. Change child->parChildrenArray[0] to new parent.
 * */
void AddChildToNode (PTNode *parent, PTNode *child)
{
    if (parent == child->parChildrenArray[0])
    {
        /* child is already child of parent
         * Do need to do anything.
         * */
        return;
    }
    PTNode *oldParent = child->parChildrenArray[0];
    parent->numChilds += 1;
    int numChilds = parent->numChilds;
   
    /* Memery Optimization */
    if ( numChilds > parent->memCtrl )
    {
        if (numChilds > MAX_TREE_SIZE )
        {
            cout <<"Tree size over load, MAX_TREE_SIZ : "<<MAX_TREE_SIZE<<endl;
            exit (1);
        }
        if ( 2 * parent->memCtrl <  MAX_TREE_SIZE)
        {
            /* Realloc memery by 2 times. */
            parent->parChildrenArray = (PTNode **) realloc (parent->parChildrenArray, 2 * parent->memCtrl);
            parent->memCtrl *= 2;
        }
        else
        {
            parent->parChildrenArray = (PTNode **) realloc (parent->parChildrenArray, MAX_TREE_SIZE);
            parent->memCtrl = MAX_TREE_SIZE;
        }
    }
    /* End of Memery optimization */

    /* Add this child to this tree.
     * the i'th child will be put to index i. Because index 0 is parent.
     * * */
    parent->parChildrenArray[numChilds] = child;
    /* parent is now the new parent of node child */
    child->parChildrenArray[child->parent] = parent;
}

void TDoMergeSet (TDynamicSetCP *dynSetsCP, int setID1, int setID2)
{
    // Merge two sets.
    PTNode *pSmallSetRoot;
    unsigned int height1 = dynSetsCP->sets[setID1].root->height;
    unsigned int height2 = dynSetsCP->sets[setID2].root->height;
    unsigned int LargeSetID;
   
    /* Move from 'small' tree to 'big' tree
     * The height only need to increase by 1 if the two trees have same height.
     * */
    if (height1 >= height2)
    {
        pSmallSetRoot = dynSetsCP->sets[setID2].root;
        LargeSetID = setID1;
       
        if (height1 = height2)
            dynSetsCP->sets[setID1].root->height += 1;
    }
    else
    {
        pSmallSetRoot = dynSetsCP->sets[setID1].root;
        LargeSetID = setID2;
    }

    /* Add pSmallSetRoot to LargeSetID root */
    AddChildToNode (dynSetsCP->sets[LargeSetID].root, pSmallSetRoot);
}

TDynamicSetCP* CreateTDynSetsCP (ALGraph *graph)
{
    TDynamicSetCP *dynSetsCP = new TDynamicSetCP;
    dynSetsCP->sets = new TDynamicSet[graph->vexnum];
    dynSetsCP->allSetsElemArray = new TDynamicSetElem[graph->vexnum];
   
    return dynSetsCP;
}

void InitTDynamicSets (TDynamicSetCP *dynSetsCP, int numSets)
{
    int i,j;
    dynSetsCP->numSets = numSets;
    dynSetsCP->numAllSetsElems = numSets;
    for (i = 0; i < numSets; i++)
    {
        dynSetsCP->allSetsElemArray[i].data = NULL;
        dynSetsCP->allSetsElemArray[i].node = new PTNode;
        dynSetsCP->allSetsElemArray[i].node->setID = i;
        dynSetsCP->allSetsElemArray[i].node->parent = 0;       // The index of parent is always 0.
        dynSetsCP->allSetsElemArray[i].node->numChilds = 0;
      
        dynSetsCP->allSetsElemArray[i].node->parChildrenArray =
            (PTNode**) new PPTNode[INIT_TREE_SIZE + 1]; // Parent + children

        dynSetsCP->allSetsElemArray[i].node->memCtrl = INIT_TREE_SIZE;
        for ( j = 0; j < dynSetsCP->allSetsElemArray[i].node->numChilds+ 1; j++)
            dynSetsCP->allSetsElemArray[i].node->parChildrenArray[j] = NULL;
      
        //It is root, no parent. 
        dynSetsCP->allSetsElemArray[i].node->parChildrenArray[dynSetsCP->allSetsElemArray[i].node->parent] = NULL;
       
        dynSetsCP->sets[i].root    = dynSetsCP->allSetsElemArray[i].node;

        dynSetsCP->sets[i].root->height  = 1;
    }
    return;
}
/*************** MiniSpanTree_Kruskal_TreeImpl.cpp  ****************************/

/****************************** main.cpp ***************************************/
#include <iostream>
#include "graph.h"
//#include "MiniSpanTree_Kruskal_ArrayImpl.h"
#include "MiniSpanTree_Kruskal_TreeImpl.h"
using namespace std;

int main()
{
    ALGraph *graph;
    graph = CreateALGraph ();
   // cout << "MiniSpanTree_Kruskal_Array: "<<endl;
   // MiniSpanTree_Kruskal_Array (graph);
    cout << "**********************************************"<<endl
         << "MiniSpanTree_Kruskal_Tree: "<<endl;
    MiniSpanTree_Kruskal_Tree (graph);
}
/*******************************end of file main.cpp **************************/