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

　　上面的算法有三個(gè)循環(huán)，時(shí)間復(fù)雜度為O(N^3)，考慮到由于使用的是貪心策略，則每添加一個(gè)新頂點(diǎn)到集合S中的時(shí)候，才會(huì)改變V中每個(gè)點(diǎn)到S中點(diǎn)的最小邊的長(zhǎng)度。因此可以用一個(gè)數(shù)組nearest[N](N為頂點(diǎn)個(gè)數(shù))記錄在生成最小數(shù)的過(guò)程中，記錄V中每個(gè)點(diǎn)的到S中點(diǎn)的最小變長(zhǎng)，用另外一個(gè)數(shù)組adjecent[N]記錄使得該邊最小的對(duì)應(yīng)的鄰接點(diǎn)。那么O(N)的時(shí)間了找到最短的邊，并且能在O(N)的時(shí)間里更新nearest[N]和adjecent[N]。因此可以得到O(N^2)的算法。

　　源碼實(shí)現(xiàn)如下：

　　//O(N^2)

　　#include

　　using namespace std;

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

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

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

　　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()

　　{

　　//記當(dāng)前生成樹(shù)的節(jié)點(diǎn)集合為S

　　//未使用的節(jié)點(diǎn)結(jié)合為V

　　bool flag[N]; //標(biāo)記某個(gè)點(diǎn)是否在S中

　　int nearest[N];//記錄V中每個(gè)點(diǎn)到S中鄰接點(diǎn)的最短邊

　　intadjecent[N];//記錄與V中每個(gè)點(diǎn)最鄰接近的點(diǎn)

　　int i,j,min;

　　//初始化集合

　　for(i = 0; i

　　flag[i] =false;

　　flag[0] = true;

　　for(i = 1; i

　　{

　　nearest[i] =matrix[0][i];

　　adjecent[i] =0;

　　}

　　int count = N;

　　while(--count)

　　{

　　min = M;

　　j = 0;

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

　　{

　　if(!flag[i] && nearest[i] < min)

　　{

　　min =nearest[i];

　　j =i;

　　}

　　}

　　cout<

　　flag[j] =true;

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

　　{

　　if(!flag[i] && matrix[i][j]

　　{

　　nearest[i] = matrix[i][j];

　　adjecent[i] = j;

　　}

　　}

　　}

　　}

　　int main(int argc, char* *argv)

　　{

　　prim();

　　system("pause");

　　return 0;

　　}

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

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

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

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