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

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

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

　　//O(N^2)

　　#include

　　using namespace std;

　　#define N 6 //節(jié)點個數(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()

　　{

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

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

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

　　int nearest[N];//記錄V中每個點到S中鄰接點的最短邊

　　intadjecent[N];//記錄與V中每個點最鄰接近的點

　　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;

　　}

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

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

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

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