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

 　　上面的算法有三个循环，时间复杂度为O(N^3)，考虑到由于使用的是贪心策略，则每添加一个新顶点到集合S中的时候，才会改变V中每个点到S中点的最小边的长度。因此可以用一个数组nearest[N](N为顶点个数)记录在生成最小数的过程中，记录V中每个点的到S中点的最小变长，用另外一个数组adjecent[N]记录使得该边最小的对应的邻接点。那么O(N)的时间了找到最短的边，并且能在O(N)的时间里更新nearest[N]和adjecent[N]。因此可以得到O(N^2)的算法。

　　源码实现如下：

　　//O(N^2)

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

　　{

　　//记当前生成树的节点集合为S

　　//未使用的节点结合为V

　　bool flag[N]; //标记某个点是否在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