kruskal算法实现最小生成树(图模型+小根堆+并查集)

生成树，是原连通图的极大无环子图，而最小生成树则是所有权值之和最小的这种图。

kruskal算法的入手点是边。它每次取出这个图中权值最小的一条边，并得到这条边关联的两个顶点v1、v2，

接着验证v1、v2之间是否存在通路，如果存在通路则舍弃它，如果不存在则将这两个顶点压入最小生成树中。

在我的程序中，实现取图中权值最小的边用的是小根堆，实现判断两个顶点v1、v2是否存在通路用的是并查集，因为存在通路意味着两个顶点属于同个集合。

小根堆模块

int heapNum=0; //记录堆的结点个数

//堆的结点结构
struct Heap
{
	int sta,en;
	int weight;
} heap[100];


//下滑操作
void siftDown(int start,int end)
{
	//将start号结点向下调整直到end
	int i=start,j=2*i;
	heap[0]=heap[i]; //用heap[0]来临时保存i结点的值
	while(j<=end)
	{
		//有右孩子并且右孩子比左孩子小时，将j保存右孩子
		if(j<end&&heap[j].weight>heap[j+1].weight) ++j;
		//比j号结点小时，不需调整
		if(heap[0].weight<=heap[j].weight) 
			break;
		else
		{
			//向下调整
			heap[i]=heap[j];
			i=j;
			j=2*j;
		}
	}
	heap[i]=heap[0];
}

void siftUp(int start)
{
	int j=start,i=j/2;
	heap[0]=heap[j];
	while(j>0)
	{
		if(heap[i].weight<=heap[0].weight)
			break;
		else
		{
			//向上调整工作
			heap[j]=heap[i];
			j=i;
			i=i/2;
		}
	}
	heap[j]=heap[0];
}

//插入操作的实现
bool insert(Heap temp)
{
	++heapNum;
	heap[heapNum]=temp;
	siftUp(heapNum);
	
	return true;
}

//删除操作
bool removeMin(Heap& temp)
{
	//保留下根结点
	temp=heap[1];
	heap[1]=heap[heapNum]; //填补树根

	--heapNum;
	siftDown(1,heapNum); //将根结点下滑到尾部
	return true;
}

并查集模块

int parent[100];

//查找i所在的集合的元首，并对该树形结构进行优化
int collaspingFind(int i)
{
	int r=i;
	for(;parent[r]>=0;r=parent[r]);

	while(i!=r)
	{
		int s=parent[i];
		parent[i]=r;
		i=s;
	}
	return r;
}

void weightedUnion(int i,int j)
{
	int temp=parent[i]+parent[j];

	//负数值大的反而小，树i的结点较小时
	if(parent[j]<parent[i])
	{
		parent[i]=j;  //将i的父亲设为j
		parent[j]=temp;
	}
	else
	{
		parent[j]=i;
		parent[i]=temp;
	}
}

图模块

struct LinkNode
{
	int vex; //邻接的结点在数组中的编号
	LinkNode* next;
	int weig; //结点的权值
};

//定义图结点的最大个数
const int MaxSize=10;

bool visitedMini[10]={false};

struct Node
{
	int data;
	LinkNode* head;
	//将结点邻接的链表头置为空
	Node(){ head=0;}
} Adj[MaxSize],miniTree[MaxSize]; //Adj数组表示原来的图
								//miniTree表示最小生成树

//建立图的算法
void createLink(int& numNode)
{
	int numLink=0;
	LinkNode* ptr;

	cin>>numNode;

	for(int i=1;i<=numNode;++i)
	{
		cin>>Adj[i].data;
		cin>>numLink;

		//头插入建表
		for(int j=0;j<numLink;++j)
		{
			ptr=new LinkNode;
			cin>>ptr->vex;
			cin>>ptr->weig;

			ptr->next=Adj[i].head;
			Adj[i].head=ptr;
		}
	}
}

//图的深度优先访问
void DFS(int v)
{
	LinkNode* ptr=0;
	visitedMini[v]=true;
	cout<<miniTree[v].data<<" ";

	ptr=miniTree[v].head;
	//每个邻接点都有机会访问
	while(ptr!=0)
	{
		//没访问过时递归访问
		if(!visitedMini[ptr->vex]) 
			DFS(ptr->vex);
		ptr=ptr->next; //到下个邻接点
	}
}

最小生成树的实现模块

//将图中的所有边存入堆中
void inHeap(int& numNode)
{
	LinkNode* ptr=0;

	for(int v=1;v<=numNode;++v)
	{
		ptr=Adj[v].head;
		//每个邻接点都有机会访问
		while(ptr!=0)
		{
			//将图中的边和所关联的两个结点压入堆中
			Heap temp;
			temp.sta=v;
			temp.en=ptr->vex;
			temp.weight=ptr->weig;

			//只放入sta<en的顺序的边，来避免将边重复放入
			if(temp.sta<temp.en)
				insert(temp);

			ptr=ptr->next; //到下个邻接点
		}
	}
}

//将两个结点及其对应关系插入最小生成树中
void insertTree(int st,int en,int weig)
{
	LinkNode* ptr=new LinkNode;
	ptr->vex=en;
	ptr->weig=weig;

	ptr->next=miniTree[st].head;
	miniTree[st].head=ptr;
}

//求最小生成树的算法
void kruskal()
{
	int nodeNum=0;
	createLink(nodeNum);

	//初始化并查集
	for(int i=1;i<=nodeNum;++i)
		parent[i]=-1;

	//将所有边存入堆中
	inHeap(nodeNum);

	int cntNum=1;
	while(cntNum<nodeNum)
	{
		Heap temp;
		//取堆中权值最小的结点
		removeMin(temp);

		int stRoot=collaspingFind(temp.sta);
		int enRoot=collaspingFind(temp.en);
		if(stRoot!=enRoot)
		{
			weightedUnion(stRoot,enRoot);
			//将这两个点存入最小生成树中
			miniTree[temp.sta].data=Adj[temp.sta].data;
			miniTree[temp.en].data=Adj[temp.en].data;

			insertTree(temp.sta,temp.en,temp.weight);
			insertTree(temp.en,temp.sta,temp.weight);

			++cntNum;
		}
	}
}