更多：2011年軟考程序員考試復習筆試知識點整理匯總

　　15、最小生成樹之kruskal算法

　　最小生成樹兩個重要的算法：Prim 和 Kruskal。

　　Prim：時間復雜度O(n^2)，適用于邊稠密的網絡。

　　Kruskal：時間復雜度為O(e*log(e))，適用于邊稀疏的網絡。

　　kruskal算法的時間復雜度主要由排序方法決定，其排序算法只與帶權邊的個數有關，與圖中頂點的個數無關，當使用時間復雜度為O(eloge)的排序算法時，克魯斯卡算法的時間復雜度即為O(eloge)，因此當帶權圖的頂點個數較多而邊的條數較少時，使用克魯斯卡爾算法構造最小生成樹效果最好!Kruskal

　　從所有邊中找到一個最小的邊，且將改變放入后不會生成圈，重復n-1次后求出最小生成樹。我們首先將所有邊排序，然后從小到大判斷，如果不產生圈就加入樹中，當加入n-1條邊時停止。為了判斷是否組成圈，我們要用到并查集，相關知識可以在本站或任一本競賽書中找到，這里不贅述。算法復雜度是(eloge+eα)，α是做一次并查集的復雜度，可以認為是常數。

　　/*

　　并查集的一個特性:

　　用一個數組p[]表示每一個元素的父級元素

　　最父級的元素的父級元素是一個負數,這個負數的絕對值是這個集合下的元素的個數

　　*/

　　#include

　　#include

　　usingnamespace std;

　　constint N=1001; //定義能處理的最大點的個數

　　template

　　structEdge

　　{

　　int from;

　　int to;

　　T cost;

　　};

　　template

　　booloperator <(const Edge & a,const Edge & b)

　　{

　　return a.cost

　　}

　　/*

　　軟考程序員考試歷年真題重點題總結及答案

　　2011年上半年軟考報名時間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)