//圖的鄰接矩陣表示,求最小生成樹算法

#include "iostream.h"
#include "stdio.h"
#include "assert.h"
//#include "sqlist.h"
#include "minheap.h"
#include "USET.H"
//#include "minspantree.h"
#include "Graph.h"



const int MaxNumEdges = 50;							//最大邊數(shù)
//int DefaultSize = 100;
#ifndef SetMaxVertices
#define SetMaxVertices
const int MaxNumVertices=10;							//最大頂點數(shù)
#endif


template <class NameType, class DistType>
MinSpanTree& Graph< NameType, DistType>::Kruskal ( MinSpanTree &T ) {	//克魯斯卡爾算法
   MSTEdgeNode e;
   MinHeap<MSTEdgeNode> H (CurrentEdges );	//最小堆
   int NumVertices = VerticesList.Length();			//圖中頂點個數(shù)
   UFSets F (NumVertices);			//連通分量
   for ( int u=0; u<NumVertices; u++ ) 			//建立最小堆的數(shù)據(jù)
	 for ( int v=u+1; v<NumVertices; v++ )
	   if ( Edge[u][v] != 0 ) {		//插入新邊值結點到最小堆中
	   e.tail=u;e.head=v;e.key=Edge[u][v];
		 H.Insert (e);
	   }
   int count = 1;					//生成樹邊計數(shù)
   while ( count < NumVertices ) {			//反復執(zhí)行, 取n-1條邊
	 H.RemoveMin (e );				//從最小堆中退出具最小權值的邊
	 int u = F.Find ( e.tail );
	 int v = F.Find ( e.head );			//取兩頂點所在集合的根
	 if ( u != v ) {				//不是同一集合, 說明不連通
	   F.Union ( u, v );
	   T.addEdge(e.tail,e.head,e.key);
	   count++;	//合并, 連通它們, 該邊加入生成樹
	 }
   }
   return T;
}



		void main()
		{

         Graph <char,int>  g(10);
		 MinSpanTree T;
		 cin>>g;
		 g.DFS();
		 cout<<endl;
		 g.Kruskal(T);
		 cout<<T;


		}