更多：2011年軟考程序員考試復習筆試知識點整理匯總

　　14、最小生成樹算法之Prim算法(C++實現)

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

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

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

　　3)循環執行第2)步直到S中包含了所有頂點。

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

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

　　// O(N^3)

　　#include

　　using namespace std;

　　//用鄰接矩陣表示無向圖

　　#define N 6 //節點個數

　　#define M 100000//最大值，表示不可達

　　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]; //標記某個點是否當前生成樹集合中

　　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;

　　}

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

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

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

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