最小生成樹之Prim算法

　　Prim算法用于求無向圖的最小生成樹

　　設(shè)圖G =(V，E)，其生成樹的頂點(diǎn)集合為U。

　�、�、把v0放入U(xiǎn)。

　�、�、在所有u∈U，v∈V-U的邊(u，v)∈E中找一條最小權(quán)值的邊，加入生成樹。

　　③、把②找到的邊的v加入U(xiǎn)集合。如果U集合已有n個(gè)元素，則結(jié)束，否則繼續(xù)執(zhí)行②。

　　其算法的時(shí)間復(fù)雜度為O(n^2)

　　Prim算法實(shí)現(xiàn)：

　　(1)集合：設(shè)置一個(gè)數(shù)組set(i=0,1,..,n-1),初始值為 0,代表對(duì)應(yīng)頂點(diǎn)不在集合中(注意：頂點(diǎn)號(hào)與下標(biāo)號(hào)差1)

　　(2)圖用鄰接陣表示，路徑不通用無窮大表示，在計(jì)算機(jī)中可用一個(gè)大整數(shù)代替。

　　采用堆可以將復(fù)雜度降為O(m log n)，如果采用Fibonaci堆可以將復(fù)雜度降為O(n log n + m)

　　算法實(shí)現(xiàn)

　　#include

　　#define MaxNum 765432100;

　　using namespace std;

　　ifstream fin("Prim.in");

　　ofstream fout("Prim.out");

　　int p,q;

　　bool is_arrived[501];

　　int Length,Vertex,SetNum,State;

　　int Map[501][501],Dist[501];

　　int FindMin()

　　{

　　int p;

　　int Minm,Temp;

　　Minm=MaxNum;

　　Temp=0;

　　2011計(jì)算機(jī)等級(jí)二級(jí)C語言五套模擬試題及答案

　　計(jì)算機(jī)等級(jí)考試二級(jí)C語言歷年真題匯總(2005-2010)

　　2011年計(jì)算機(jī)等級(jí)考試二級(jí)C語言常見問題匯總

　　計(jì)算機(jī)等級(jí)考試二級(jí)C語言常見知識(shí)點(diǎn)總結(jié)