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;

　　}[NextPage]

　　上面的算法有三个循环，时间复杂度为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<

　　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;

　　}

[NextPage]

　　#include

　　#include

　　#define MAXVEX 30

　　#define MAXCOST 1000

　　/*

　　每一步扫描数组lowcost，在V-U中找出离U最近的顶点，令其为k，并打印边(k,closest[k]), 然后修改lowcost和closest，标记k已经假如U。c表示图邻接矩阵，弱不存在边(i,j),则c[i][j]的值为一个大于任何权而小于无限打的阐述，这里用MAXCOST表示

　　*/

　　/*一直图的顶点为{1,2,...,n},c[i][j]为(i,j)的权，打印最小生成树的每条边*/

　　void prim (int c[MAXVEX][MAXVEX], int n)

　　{

　　int i,j,k,min,lowcost[MAXVEX],closest[MAXVEX];

　　for(i=2;i<=n;i++) /*从顶点1开始*/

　　{

　　lowcost[i]=c[1][i];

　　closest[i]=1;

　　}

　　closest[1]=0;

　　for(i=2;i<=n;i++) /*从U之外求离U中某一顶点最近的顶点*/

　　{

　　min=MAXCOST;

　　j=1;

　　k=i;

　　while(j<=n)

　　{

　　if(lowcost[j]

　　{

　　min=lowcost[j];

　　k=j;

　　}

　　j++;

　　}

　　printf("(%d,%d)",closest[k],k); /*打印边*/

　　closest[k]=0;/* k假如到U中 */

　　for(j=2;j<=n;j++)

　　if(closest[j]!=0 && c[k][j]

　　{

　　lowcost[j]=c[k][j];

　　closest[j]=k;

　　}

　　}

　　}

 [NextPage]

　　问题：--------------------------------------

　　1) 为何两个for循环都是从下标2开始的?尤其是第二个想不通。

　　答：因为Prim算法可以任选起点，通常选定点1为起点，也就是说点1一开始就在U里面了，自然不必出现在第二个循环(在V-U中寻找点)中。

　　2) lowcost数组顾名思义知道是存放最小代价信息的数组，但是具体的说lowcost放着是什么的最小代价，比如“lowcost[i]=c[1][i];”表示的是什么意思(我要带i的语言描述)?

　　答：存放的是当前从点集U到点集V-U的最短边长，lowcost[i] = c[1][i]是初始化，开始时点集U中只有点1，因此当前点集U到点集V-U的各最短边长lowcost[i]就等于点1到点i的边权。

　　3) closest[i]=1 又是什么含意呢?

　　答：closest[i]记录对应lowcost[i]的边的起点，因为lowcost[i]是当前终点为i的各条边中的最小值，再加上一个closest[i]记录起点，就能确定最小生成树的边了。closest[i] = 1是初始化，自然每一个边都是从点1出发的。

　　4) 求教第二个for循环的整层循环是写什么，我要每一行的注释。到底是在作什么??

　　答：

　　for (i=2;i<=n;i++) /*从U之外求离U中某一顶点最近的顶点*/

　　{

　　min=MAXCOST; // 这一段是在U之外找最小值，closest[j] != 0表示是U之外

　　j=1;

　　k=i;

　　while (j<=n)

　　{

　　if(lowcost[j]

　　{

　　min=lowcost[j];

　　k=j;

　　}

　　j++;

　　}

　　printf("(%d,%d)",closest[k],k); /*打印边，这里就看出closest[k]的用途了嘛*/

　　closest[k]=0; /*将点k加入集合U */

　　for(j=2;j<=n;j++) //更新最短边和相应起点

　　{

　　if (closest[j]!=0&& c[k][j]

　　{

　　lowcost[j]=c[k][j]; //更新最小权值

　　closest[j]=k; //记录新边的起点

　　}

　　}

　　}