一、概述

MST（Minimum Spanning Tree，最小生成树）问题有两种通用的解法，Prim算法就是其中之一，它是从点的方面考虑构建一颗MST。

 

二、算法描述

大致思想：有一带权连通图G = （U，E），即图G顶点集合为U 、边集为E。①首先在集合U中任意选择一点作为起始点a，将该点加入空集V，即初始状态下，生成树只有一个顶点，没有边；②再从集合U-V中找到另一点b使得边（a，b）是所有这样（只有一个点在构造中的生成树上）形成的边中代价最小的，此时将b点也加入集合V；现在的集合V={a，b}，再从集合U-V中找到另一点c使得边（a，c）或（b，c）是所有这样（只有一个点在构造中的生成树上）形成的边中代价最小的，此时将c点加入集合V；以此类推，直至所有顶点全部被加入V，此时就构建出了一颗MST。③因为有N个顶点，所以该MST就有N - 1条边，每一次向集合V中加入一个点，就意味着找到一条MST的边。

换种说法：有一带权连通图G = （U，E），即图G顶点集合为U 、边集为E。①首先在集合U中任意选择一点作为起始点a，将该点加入空集V，即初始状态下，生成树只有一个顶点，没有边；②再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一颗MST。③因为有N个顶点，所以该MST就有N - 1条边，每一次向集合V中加入一个点，就意味着找到一条MST的边。

为了实现Prim算法，我们需要依照思想设置一些辅助数组。

• int lowcost[v]  表示以v为终点的边（u，v）的权值，v 是当前尚未选入生成树的顶点；
• int nearest[v]  保存边（u，v）的另一个顶点u，u 在生成树上；
• bool visited[i] 标志某个顶点当前是否已被选入在生成树上。

初始设置如下：

• lowcost[v] 均为+∞；
• nearest[v] 均为起始点a。

 

三、代码实现

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define N 100	#define INF 0x7fffffff 	//INF相当于int型数据的最大值 int matrix[N][N];		//作为图的邻接矩阵 int lowcost[N];			//lowcost[v]表示以v为终点的边（u，v）的权值，v是当前尚未选入生成树的顶点int nearest[N];			//nearest[v]保存边（u，v）的另一个顶点u，u在生成树上bool visited[N];		//visited[v]标志某个顶点当前是否已被选入在生成树上int sum;							//记录权值和 int vertex_num,arc_num,source;		//顶点数、边数、起始点 void prim(int source)		//起点{	memset(lowcost,INF,sizeof(lowcost));	memset(visited,false,sizeof(visited));	visited[source] = true;	for(int i=0;i
        
         >vertex_num;	for (int i = 0; i < vertex_num; i++)       	 for (int j = 0; j < vertex_num; j++)            	matrix[i][j] = INF;	cout<<"请输入边数：";	cin>>arc_num;	cout<<"请依次输入边：\n";	for(int i=0;i
         
          >u>>v>>w;		matrix[u][v] = matrix[v][u] = w;	}	cout<<"请输入起始点：";	cin>>source; 	prim(source);	cout<<"以"<
          <<"为起点的最小生成树的权和为："<
          
           <
          
         
        
       
      
     

 

四、沙场练兵

题目一、

题目二、

 

2017/7/24更新题目二代码

 

#include
     
      #include 
      
       using namespace std;#define N 10005#define INF 0x7fffffffint lowcost[N],nearest[N], matrix[N][N];bool visited[N];int vertex_num, sum;void prim(){	memset(visited,false,sizeof(visited));	memset(lowcost,INF,sizeof(lowcost));	visited[1] = true;	for(int i=1;i<=vertex_num;i++){		lowcost[i] = matrix[1][i];	}	int min_cost, min_cost_index;	for(int i=2;i<=vertex_num;i++){		min_cost = INF;		for(int j=1;j<=vertex_num;j++){			if(!visited[j] && lowcost[j]
       
        >T;	while(T--){		sum = 0;		cin>>vertex_num;		for(int i=1;i<=vertex_num;i++){			for(int j=1;j<=vertex_num;j++){				cin>>matrix[i][j];					//i到j的距离 			}		}		prim();		cout<
        
         <