第8章图 template <class Type> void MinHeap<Type>: Insert( const Type &ele )i Currents ize++; if( CurrentSize ==HMaxsSize )return FilterUp( Currentsize ) template <class Type> void MinHeap<Type>: RemoveMin( Type &Min)i if( Currentsize <0) Min= pHeap[0; pHeap[0]= pHeap CurrentSize]: Filter Down(0, CurrentSize ) template <class Type> void MinHeap<Type>: Output(( for ( int 1=0; i < CurrentSize; i++ )cout < pHeap<< cout < endl void Graph: InitGraph()i Edge0JoJ=-1; Edge[oJ[= 28; Edge[oJ2=-1: Edge0J3=-1; Edge[o4=-1: Edge o5=10; Edge[ 6=1; Edge[1][1]=-1: Edge[ 1][2]=16; Edge[1 3]=-1; Edge[1[4]=-1; Edge[15]=-1: Edge[ 1[6]=14; Edge[2[2]=-1;Edge[2l]=12;Edge[2l4]=-1;Edge[2l5]=-1;dge[2][6=-1; Edge[3][3]=-1;Edge[3[4]=22;Edge[3][S]=-1;Fdge[3[6=18 Edge[4[4]=-1;Edge[4[5]=25;Edge[4]6 Edge[55]=-1; Edge[5 [6]=-1; Edge66]=-1; for( int i=1; i <; i++) for intj=0;j<1j++)Edge[0= Edge[0; void Graph: Kruskal)i GraphEdge int VerticesNum= Get VerticesNum ( MinHeap< GraphEdge> heap( VerticesNum"VerticesNum ) for (i=0; 1< Vertices Num; i++) for(j=i+l;j<VerticesNum: j++) e head =i;e tail =j;ecost=Edge[[]: heap. Insert(e )第 8 章 图 104 template <class Type> void MinHeap<Type> :: Insert ( const Type &ele ) { CurrentSize++; if ( CurrentSize == HMaxSize ) return; pHeap[CurrentSize] = ele; FilterUp ( CurrentSize ); } template <class Type> void MinHeap<Type> :: RemoveMin ( Type &Min ) { if ( CurrentSize < 0 ) return; Min = pHeap[0]; pHeap[0] = pHeap[CurrentSize--]; FilterDown ( 0, CurrentSize ); } template <class Type> void MinHeap<Type> :: Output ( ) { for ( int i = 0; i <= CurrentSize; i++ ) cout << pHeap[i] << " "; cout << endl; } void Graph :: InitGraph( ) { Edge[0][0] = -1; Edge[0][1] = 28; Edge[0][2] = -1; Edge[0][3] = -1; Edge[0][4] = -1; Edge[0][5] = 10; Edge[0][6] = -1; Edge[1][1] = -1; Edge[1][2] = 16; Edge[1][3] = -1; Edge[1][4] = -1; Edge[1][5] = -1; Edge[1][6] = 14; Edge[2][2] = -1; Edge[2][3] = 12; Edge[2][4] = -1; Edge[2][5] = -1; Edge[2][6] = -1; Edge[3][3] = -1; Edge[3][4] = 22; Edge[3][5] = -1; Edge[3][6] = 18; Edge[4][4] = -1; Edge[4][5] = 25; Edge[4][6] = 24; Edge[5][5] = -1; Edge[5][6] = -1; Edge[6][6] = -1; for ( int i = 1; i < 6; i++ ) for ( int j = 0; j < i; j ++ ) Edge[i][j] = Edge[j][i]; } void Graph :: Kruskal( ) { GraphEdge e; int VerticesNum = GetVerticesNum ( ); int i, j, count; MinHeap<GraphEdge> heap ( VerticesNum *VerticesNum ); UFSets set ( VerticesNum ); for ( i = 0; i < VerticesNum; i++ ) for ( j = i + 1; j < VerticesNum; j++ ) if ( Edge[i][j] > 0 ) { e.head = i; e.tail = j; e.cost = Edge[i][j]; heap.Insert ( e );