2011年軟考程序員考試復(fù)習(xí)筆試知識點整理(11)

　　更多：2011年軟考程序員考試復(fù)習(xí)筆試知識點整理匯總

　　15、最小生成樹之kruskal算法

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

　　Prim：時間復(fù)雜度O(n^2)，適用于邊稠密的網(wǎng)絡(luò)。

　　Kruskal：時間復(fù)雜度為O(e*log(e))，適用于邊稀疏的網(wǎng)絡(luò)。

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

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

　　/*

　　并查集的一個特性:

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

　　最父級的元素的父級元素是一個負(fù)數(shù),這個負(fù)數(shù)的絕對值是這個集合下的元素的個數(shù)

　　*/

　　#include

　　#include

　　usingnamespace std;

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

　　template

　　structEdge

　　{

　　int from;

　　int to;

　　T cost;

　　};

　　template

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

　　{

　　return a.cost

　　}

　　/*

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

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

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