//最小生成樹算法
/*
#include "iostream.h"
#include "minheap.h"
#include "USET.h"
*/

extern const int MaxNumVertices;

#define MAXINT 32767		// 機器可表示的, 問題中不可能出現(xiàn)的大數(shù)

class MinSpanTree;			//最小生成樹的前視類聲明99

class MSTEdgeNode
{			//最小生成樹邊結(jié)點的類聲明
public:
	friend class MinSpanTree;
	friend ostream& operator <<(ostream& strm, MSTEdgeNode e);
     int tail, head;				//兩頂點位置
     int key;					//邊上的權(quán)值
};

class MinSpanTree {				//最小生成樹的類定義
public:
   MinSpanTree ( int sz = MaxNumVertices-1 ) : MaxSize (sz), n (0),cost(0) { edgeValue = new MSTEdgeNode[MaxSize]; }
   void addEdge(int ,int ,int );
   friend ostream& operator <<(ostream& strm, MinSpanTree t);
private:
   MSTEdgeNode *edgeValue;			//用邊值數(shù)組表示樹
   int MaxSize, n,cost;				//數(shù)組的最大元素個數(shù)和當前個數(shù)
};


void MinSpanTree::addEdge(int tail,int head,int dist)//向生成樹邊值數(shù)組內(nèi)存放
{
	   edgeValue[n].tail = tail;  
	   edgeValue[n].head = head;  
	   edgeValue[n].key = dist;
	   cost=cost+dist;	   
	   n++;
}
ostream& operator <<(ostream& strm, MSTEdgeNode e)
{
	strm<<"("<<e.tail<<","<<e.head<<")";
	return strm;
}
ostream& operator <<(ostream& strm, MinSpanTree t)
{
	for (int i=0;i<t.n;i++)
		strm<<t.edgeValue[i];
	strm<<endl;
	strm<<"Total Cost="<<t.cost<<endl;
	return strm;
}