克魯斯卡爾（Ｋｒｕｓｋａｌ）算法的實現與分析

摘要：克魯斯卡爾（Kruskal）算法是實現圖的最小生成樹最常用的算法。本文主要介紹克魯斯卡爾（Kruskal）算法的實現方法，并對克魯斯卡爾（Kruskal）算法的效率進行分析。

關鍵詞：克魯斯卡爾（Kruskal）算法；算法實現；算法分析

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2008)11-20311-02

1 克魯斯卡爾（Kruskal）算法的基本思想

設有一個有n個頂點的連通網絡N={V，E}，最初先構造一個只有n個頂點，沒有邊的非連通圖T={V，Oslash;}，圖中每個頂點自成一個連通分量。當在E中選到一條具有最小權值的邊時，若該邊的兩個頂點落在不同的連通分量上，則將此邊加入到T中；否則將此邊舍去，重新選擇一條權值最小的邊。如此重復下去，直到所有頂點在同一個連通分量上為止。

算法的基本框架：利用最小堆（MinHeap）和并查集（DisjointSets）來實現克魯斯卡爾（Kruskal）算法。

2 應用克魯斯卡爾（Kruskal）算法構造最小生成樹的實例

建立最小生成樹的實現過程：

出堆順序：（0，5，10）選中，（2，3，12）選中，（1，6，14）選中，（1，2，16）選中，（3，6，18）舍棄，（3，4，22）選中，（4，6，24）舍棄，（4，5，25）選中。

鄰接矩陣表示：

3 克魯斯卡爾（Kruskal）算法的實現

首先，利用最小堆來存放E中的所有的邊，堆中每個結點的格式為：

在構造最小生成樹的過程中，最小堆中存放剩余的邊，并且利用并查集的運算檢查依附于一條邊的兩個頂點tail、head是否在同一個連通分量（即并查集的同一個子集合）上，是則舍去這條邊；否則將此邊加入T，同時將這兩個頂點放在同一個連通分量上。隨著各邊逐步加入到最小生成樹的邊集合中，各連通分量也在逐步合并，直到形成一個連通分量為止。

最小生成樹類定義：

Cons tint MAXINT= 機器可表示的最大數

class MinSpanTree;

class MSTEdgeNode {//生成樹邊結點類定義

friend class MinSpanTree;

private:

int tail， head; //生成樹各邊的兩頂點

float cost; //生成樹各邊的代價

};

class MinSpanTree { //生成樹的類定義

public:

MinSpanTree ( int sz = NumVertices -1 ) : MaxSize (sz)， n (0)

{ edgevalue = new MSTEdgeNode[MaxSize]; }

int Insert ( MSTEdgeNode item );//將item加到最小生成樹中

protected:

MSTEdgeNode *edgevalue; //邊值數組

int MaxSize， n; //最大邊數，當前邊數

};

利用克魯斯卡爾（Kruskal）算法建立最小生成樹：

void Graph ::Kruskal ( MinSpanTree T ) {

MSTEdgeNodee; //邊結點輔助單元

MinHeap H(CurrentEdges);

int NumVertices = VerticesList.last; //頂點個數

UFSets F (NumVertices); //并查集F 并初始化

for ( int u = 0; u < NumVertices; u++ ) //鄰接矩陣

for ( int v = u +1; v < NumVertices; v++ )

if ( Edge[u][v] != MAXNUM ) { //所有邊

e.tail = u;e.head = v;

e.cost = Edge[u][v];H.Insert (e);//插入堆

}

int count = 1; //最小生成樹加入邊數的計數

while ( count < NumVertices ) {

H.RemoveMin ( e ); //從堆中退出一條邊

u = F.Find ( e.tail ); //檢測兩端點的根

v = F.Find ( e.head );

if ( u != v ) {//根不同不在同一連通分量

F.Union ( u， v ); //合并

T.Insert ( e ); //該邊存入最小生成樹 T

count++;

}

}

}

4 克魯斯卡爾（Kruskal)算法分析

在建立最小堆時需要檢測鄰接矩陣，計算的時間代價為O(n2)。且做了e次堆插入操作，每次插入調用了一個堆調整算法FilterUp()算法，因此堆插入需要的時間代價為O(elog2e)。

在構造最小生成樹時，最多調用了e次出堆操作RemoveMin()，2e次并查集的Find()操作，n-1次Union()操作，計算時間分別為O(elog2e)，O(elog2n)和O(n)。

總的計算時間為O(elog2e+elog2n+n2+n)。

參考文獻：

[1] (美)D E 克努特.管紀文，等，譯.計算機程序設計技巧3[M].北京:國防工業出版社，1999.185-190.

[2] 許卓群，等.數據結構[M].北京:高等教育出版社，1993.103-108.

[3] 嚴蔚敏，等.數據結構[M].北京:清華大學出版社，2004.207-215.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文