第8章图 求解过程中并查集与堆的变化 ④⑥ 选(345)山区4区30国68]选566)①3山区4②B ④⑥ D② 23 选(127)[3山[249 选(357)⑥3山 ②④⑤ 21310 ④ 山 ⑥选(3.6.)在同一连通分量上,不加②⑥选(249,结束 最后得到的生成树如下 6 并查集的存储表示 完整的程序如下 #include <iostream. h? template <class Type> class MinHeap i num MaxHeapsize=503: MinHeap( int Maxsize MaxHeap Size ) MinHeap( type array[, int n ) void Insert( const Type &ele ) void RemoveMin( Type &Min ) void Output O private void Filter Down( int start, int end ) void FilterUp( int end )i Type "pl int Currentsize; class UFSets i
第 8 章 图 101 求解过程中并查集与堆的变化： 最后得到的生成树如下 完整的程序如下: #include <iostream.h> template <class Type> class MinHeap { public: enum { MaxHeapSize = 50 }; MinHeap ( int Maxsize = MaxHeapSize ); MinHeap ( Type Array[ ], int n ); void Insert ( const Type &ele ); void RemoveMin ( Type &Min ); void Output (); private: void FilterDown ( int start, int end ); void FilterUp ( int end ); Type *pHeap; int HMaxSize; int CurrentSize; }; class UFSets { public: 3 1 -6 3 3 5 1 3 11 3 5 7 2 4 9 3 6 8 2 3 10 ① ② ③ ④ ⑤ ⑥ 6 7 7 5 9 ③ ④ 1 3 11 5 6 6 1 2 7 3 5 7 选(3,4,5) 2 4 9 2 3 10 3 6 8 ③ ④ ⑤ ⑥ 选(5,6,6) 1 3 11 1 2 7 3 5 7 2 4 9 2 3 10 3 6 8 ③ ④ ⑤ ⑥ 选(1,2,7) ① ② ③ ④ ⑤ 选(3,5,7) ⑥ ① ② 1 3 11 2 4 9 2 3 10 3 6 8 ③ ④ ⑤ ⑥ 选(3,6,8), 在同一连通分量上, 不加 ① ② 1 3 11 2 3 10 2 4 9 ③ ④ ⑤ ⑥ 选(2,4,9), 结束 ① ② 1 3 11 2 3 10 0 1 2 3 4 5 6 并查集的存储表示
第8章图 i MaxUnionSize =503; UFSets( int MaxSize= MaxUnionSize ) FSetso delete []m pArent; 3 void Union( int Rootl, int Root ) int Find( int x ) r at m sIze: 中 m pArent class Graph i enum Max VerticesNum=50: Graph( int Vertices=0) Current Vertices= Vertices; InitGraph0: J void InitGraph 0; int Get Vertices(i return Current Vertices; 3 private int Edge Max Vertices Num Max VerticesNum: int Current Vertices class GraphEdge i head, tail int operator <= GraphEdge &ed ) GraphEdge : operator <= GraphEdge &ed)i return this ->cost <=ed cos UFSets: UFSets( int MaxSize)i m sIze MaxSize m_pArent=new int[m_sIze for( int i=0; i <m_sIze; i++)m pArent[=-1; void UFSets: Union( int Rootl, int Root)i m pArent[ Root2]=rootI;
第 8 章 图 102 enum { MaxUnionSize = 50 }; UFSets ( int MaxSize = MaxUnionSize ); ~UFSets () { delete [ ] m_pParent; } void Union ( int Root1, int Root2 ); int Find ( int x ); private: int m_iSize; int *m_pParent; }; class Graph { public: enum { MaxVerticesNum = 50 }; Graph( int Vertices = 0) { CurrentVertices = Vertices; InitGraph(); } void InitGraph (); void Kruskal (); int GetVerticesNum () { return CurrentVertices; } private: int Edge[MaxVerticesNum][MaxVerticesNum]; int CurrentVertices; }; class GraphEdge { public: int head, tail; int cost; int operator <= ( GraphEdge &ed ); }; GraphEdge :: operator <= ( GraphEdge &ed ) { return this->cost <= ed.cost; } UFSets :: UFSets ( int MaxSize ) { m_iSize = MaxSize; m_pParent = new int[m_iSize]; for ( int i = 0; i < m_iSize; i++ ) m_pParent[i] = -1; } void UFSets :: Union ( int Root1, int Root2 ) { m_pParent[Root2] = Root1; }