一、概述
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 <iostream>
#include <cstdio>
#include <algorithm>
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;i++){
lowcost[i] = matrix[source][i];
nearest[i] = source;
}
int min_cost; //最小权值
int min_cost_index; //最小权值对应的边的未在最小生成树的那一点
sum = 0;
for(int i=1;i<vertex_num;i++){ //寻找除起点以外的n-1个点
min_cost = INF;
for(int j=0;j<vertex_num;j++){
if(visited[j]==false && lowcost[j]<min_cost){
min_cost = lowcost[j];
min_cost_index = j; //定位顶点
}
}
visited[min_cost_index] = true; //将已进入最小代价生成树的结点标志位true
sum += lowcost[min_cost_index];
for(int j=0;j<vertex_num;j++){ //以找到的最小下标为起点更新lowcost数组
if(visited[j]==false && matrix[min_cost_index][j]<lowcost[j]){
lowcost[j] = matrix[min_cost_index][j];
nearest[j] = min_cost_index;
}
}
}
}
int main()
{
int u,v,w;
cout<<"请输入顶点数：";
cin>>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<<"请依次输入边：
";
for(int i=0;i<arc_num;i++){
cin>>u>>v>>w;
matrix[u][v] = matrix[v][u] = w;
}
cout<<"请输入起始点：";
cin>>source;
prim(source);
cout<<"以"<<source<<"为起点的最小生成树的权和为："<<sum<<endl;
cout<<"最小生成树各边为：
";
for(int i=0;i<vertex_num;i++){
if(i != source){ //source不能是边(u,v)的终点
cout<<nearest[i]<<"---"<<i<<endl; //nearest[v]保存边（u，v）的另一个顶点u
}
}
return 0;
}
四、沙场练兵
题目一、Highways(1)
题目二、Highways(2)
2017/7/24更新题目二代码
#include<iostream>
#include <cstdio>
using namespace std;
#define N 10005
#define INF 0x7fffffff
int 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]<min_cost){
min_cost = lowcost[j];
min_cost_index = j;
}
}
visited[min_cost_index] = true;
sum = max(sum,min_cost);
for(int j=1;j<=vertex_num;j++){
if(!visited[j] && matrix[min_cost_index][j]<lowcost[j]){
lowcost[j] = matrix[min_cost_index][j];
}
}
}
}
int main()
{
int T;
cin>>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<<sum<<endl;
}
return 0;
}