?? p279.cpp
字號:
#include "P190.cpp"#include "P223.cpp"#include "P263.cpp"template <class NameType, class DistType>void Graph< NameType, DistType>::Kruskal ( MinSpanTree &T ) { //克魯斯卡爾算法 MSTEdgeNode e; MinHeap<MSTEdgeNode> H (CurrentEdges ); //最小堆 int NumVertices = VerticesList.Length(); //圖中頂點個數 UFSets F (NumVertices); //連通分量 for ( int u=0; u<NumVertices; u++ ) //建立最小堆的數據 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; //生成樹邊計數 while ( count < NumVertices ) { //反復執行, 取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++; //合并, 連通它們, 該邊加入生成樹 } }}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -