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

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

　　14、最小生成樹算法之Prim算法(C++實(shí)現(xiàn))

　　在無(wú)向帶權(quán)連通圖G中，如果一個(gè)連通子樹包含所有頂點(diǎn)，并且連接這些頂點(diǎn)的邊權(quán)之和最小，那么這個(gè)連通子圖就是G的最小生成樹。求最小生成樹的一個(gè)常見算法是Prim算法，該算法的基本思想是：

　　1)設(shè)置兩個(gè)集合V和S，任意選擇一個(gè)頂點(diǎn)作為起始頂點(diǎn)，將起始頂點(diǎn)放入集合S，其余頂點(diǎn)存入集合V中;

　　2)然后使用貪心策略，選擇一條長(zhǎng)度最短并且端點(diǎn)分別在S和V中邊(即為最小生成樹的中的一條邊)，將這條邊在V中的端點(diǎn)加入到集合S中;

　　3)循環(huán)執(zhí)行第2)步直到S中包含了所有頂點(diǎn)。

　　根據(jù)以上思想我們很快可以給出一個(gè)O(N^3)的算法，即選擇一條最短邊需要O(N^2)的時(shí)間復(fù)雜度，具體實(shí)現(xiàn)代碼如下：

　　/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

　　// O(N^3)

　　#include

　　using namespace std;

　　//用鄰接矩陣表示無(wú)向圖

　　#define N 6 //節(jié)點(diǎn)個(gè)數(shù)

　　#define M 100000//最大值，表示不可達(dá)

　　int matrix[N][N]=

　　{

　　M,6,1,5,M,M,

　　6,M,5,M,3,M,

　　1,5,M,5,6,4,

　　5,M,5,M,M,2,

　　M,3,6,M,M,6,

　　M,M,4,2,6,M

　　};

　　void prim()

　　{

　　bool flag[N]; //標(biāo)記某個(gè)點(diǎn)是否當(dāng)前生成樹集合中

　　int i,j;

　　//初始化集合

　　for(i = 0; i

　　flag[i] =false;

　　flag[0] = true;

　　int count = 1;

　　while(count++< N)

　　{

　　int min =M;

　　int e1 = -1,e2 = -1;

　　for(i = 0; i< N; ++i)

　　{

　　if(flag[i])

　　{

　　for(j= 0; j < N; ++j)

　　{

　　if(!flag[j])

　　{

　　if(matrix[i][j] < min)

　　{

　　min = matrix[i][j];

　　e1 = i;

　　e2 = j;

　　}

　　}

　　}

　　}

　　}

　　cout<

　　flag[e2] =true;

　　}

　　}

　　int main(int argc, char* *argv)

　　{

　　prim();

　　system("pause");

　　return 0;

　　}

　　///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

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

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

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