摘要
树结构实现得并查集数据结构，用来求无向图的最小生成树。
基本操作：
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 **************************/
树结构实现得并查集数据结构，用来求无向图的最小生成树。
基本操作：
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 **************************/
