bingchaji.txt

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

摘要
树结构实现得并查集数据结构，用来求无向图的最小生成树。
基本操作：
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，请发信到[e-mail];

文件结构
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++];
}