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

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

　　15、最小生成樹(shù)之kruskal算法

　　最小生成樹(shù)兩個(gè)重要的算法：Prim 和 Kruskal。

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

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

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

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

　　/*

　　并查集的一個(gè)特性:

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

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

　　*/

　　#include

　　#include

　　usingnamespace std;

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

　　template

　　structEdge

　　{

　　int from;

　　int to;

　　T cost;

　　};

　　template

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

　　{

　　return a.cost

　　}

　　/*

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

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

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