bingchaji.txt

树结构实现得并查集数据结构

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 **************************/