minspantree.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

#ifndef MINSPANTREE_H
#define MINSPANTREE_H
#include "Heap.h"
#include "UFSets.h"
#include"Graphlnk.h"
#include<iostream>
using namespace std;
const float maxValue = 99999999.0;  				//机器可表示的、问题中不可能出现的大数

template <class T, class E>
	struct MSTEdgeNode {						//最小生成树边结点的类声明

		int tail, head;							//两顶点位置

   		E key;									//边上的权值,为结点关键码

		MSTEdgeNode() : tail(-1), head(-1), key(0) {}		//构造函数		

		MSTEdgeNode<T,E> & operator=(const MSTEdgeNode<T,E> &x)
		{
			tail=x.tail;
			head=x.head;
			key=x.key;
			return *this;
		}

		friend bool operator<(MSTEdgeNode<T,E> &n1,MSTEdgeNode<T,E> &n2)
		{
			return n1.key<n2.key;
		}
		friend bool operator>(MSTEdgeNode<T,E> &n1,MSTEdgeNode<T,E> &n2)
		{
			return n1.key>n2.key;
		}
		friend bool operator==(MSTEdgeNode<T,E> &n1,MSTEdgeNode<T,E> &n2)
		{
			return n1.key==n2.key;
		}
		friend bool operator<=(MSTEdgeNode<T,E> &n1,MSTEdgeNode<T,E> &n2)
		{
			return n1.key<=n2.key;
		}
	};

	template <class T, class E>
	class MinSpanTree {							//最小生成树的类定义
	protected:
		MSTEdgeNode<T,E> *edgevalue;			//用边值数组表示树
   		int maxSize, n;							//数组的最大元素个数和当前个数
	public:
   		MinSpanTree(int sz = DefaultSize-1) : maxSize(sz), n(0) { 
 			edgevalue = new MSTEdgeNode<T,E>[sz]; 
   		}

   		bool Insert(MSTEdgeNode<T,E>& item);			//将边item插入到树中，若树中节点已满，则返回false;

		void output();							//自定义函数，顺序输出所有边
	};
	template<class T,class E>
	bool MinSpanTree<T,E>::Insert(MSTEdgeNode<T,E> & item)
	{	
		if(n==maxSize)
			return false;
		edgevalue[n]=item;
		n++;
		return true;
	}

	template<class T,class E>
	void MinSpanTree<T,E>::output()
	{
		for(int i=1;i<=n;i++)
		{
			cout<<"Edge "<<i<<" : "<<"head = "<<edgevalue[i-1].head<<" ; tail = "<<edgevalue[i-1].tail<<" ; key = "<<edgevalue[i-1].key<<endl;
		}
	}

	template <class T, class E>
	void Kruskal(Graphlnk<T,E>& G, MinSpanTree<T,E>& MST) {
		MSTEdgeNode<T,E> ed;  int u, v, count;		//边结点辅助单元
		int n = G.NumberOfVertices();				//顶点数
	   	int m = G.NumberOfEdges();					//边数
		MinHeap <E,MSTEdgeNode<T,E>> H(m); 			//最小堆,关键码类型为E
   		UFSets F(n);								//并查集
		for (u = 0; u < n; u++)
 			for (v = u+1; v < n; v++)
		    		if (G.getWeight(u,v) != 0) {
					ed.tail = u;  ed.head = v;		//插入堆
					ed.key = G.getWeight(u, v);
  					H.Insert(ed);  
		    		} 
 	   	count = 1;									//最小生成树加入边数计数
		while (count < n) {							//反复执行, 取n-1条边
			H.RemoveMin(ed);						//从最小堆中退出具最小权值的边ed
			u = F.Find(ed.tail);
			v = F.Find(ed.head);					//取两顶点所在集合的根u与v
			if (u != v) {							//不是同一集合, 说明不连通
				F.Union(u, v);						//合并, 连通它们
				MST.Insert(ed);						//该边存入最小生成树
				count++; 
			}
   		}
	};
#endif