2011年软考程序员考试复习笔试知识点整理(10)

 　　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