一、概念解释
首先解释几个概念：-
连通图：在无向图中，若任意两个顶点vi与vj都有路径相通，则称该无向图为连通图。
-
强连通图：在有向图中，若任意两个顶点vi与vj都有路径相通，则称该有向图为强连通图。
-
连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
-
生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
- 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。
(转自勿在浮沙筑高台)
简单来说，最小生成树就是在连通图中找出一颗树，这棵树满足这样的要求：1、可以将图中的所有顶点都连通；2、这颗树的边的权重和是最小的(具体到实际问题上，边的权重可能是成本、路程等)
求最小生成树一般有两种算法，一种是Prim算法，另一种则是Kruskal算法。
二、Prim算法
Prim使用的是贪心的思想，与Dijkstra有异曲同工之处。它的原理是，先从图中任意选择一个起点，并记录下与这个点直接相连的点对应的边的权值，然后找到这些边中权值最小的，并将这个权值加到最终结果中，同时在vis数组里将选定的起点标记。然后然后我们将“起点”转移到刚才选择的权值最小边所对应的另一个顶点，重复上述过程，再找出一条与新起点直接相连的权值最小边，把它的权值加到最终结果中......不断重复以上过程共n-1次，即可找出最小生成树。代码如下：
//low[]用来记录最小权值,vis[]为标记数组，标记已经走过的点
int prim()
{
int mini;
int rsl=0;
mst(vis,0);
vis[1]=1;int pos=1; //先以1为起点
for(int i=1;i<=n;i++)
low[i]=gra[pos][i]; //存储与1相连的边的权值
low[pos]=0;vis[pos]=1; //1到1的距离为0；1作为起点，可认为已在树里
for(int i=1;i<n;i++)
{
mini=INF;
for(int j=2;j<=n;j++)
if(!vis[j]&&mini>low[j]){ //查找与1相连的权值最小的边，
mini=low[j]; //将这一条边的另一个顶点加入树中，
pos=j; //同时，将pos改为这条边的另一个顶点，
} //下一次找权值最小的边时从这一个点开始
vis[pos]=1; //因为被找到的点已经加入了树中，所以vis[pos]=1；
if(mini!=INF)
rsl+=mini;
for(int j=2;j<=n;j++)
if(!vis[j]&&low[j]>gra[pos][j])
low[j]=gra[pos][j]; ////计算、更新与已经加入树中的点相连的边的最小权值
}
return rsl;
} Prim与Dijkstra的相同之处在于，两者都用到了贪心思想，且都有点与点之间的转移。但不同之处在于，Dijkstra是求从一个点到另一个点的最短路，而Prim是求最小权值的树。这就决定了两者之间的一个区别，即Dijkstra的dis[]数组用于存放起点到每一个点的最短距离，而Prim的dis[]数组用于存放当前点到与它直接相连的点的最小权值。(我怎么觉得我在说废话)
再来一道Prim的模板题→HDU1233 还是畅通工程
这题只需要直接套用模板即可，没什么需要注意的地方。可以通过这道题感受一下Prim怎么用。
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define INF 0x3f3f3f3f
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int gra[105][105];
int low[105];
bool vis[105];
int n;
int prim()
{
int mini;
int rsl=0;
mst(vis,0);
vis[1]=1;int pos=1;
for(int i=1;i<=n;i++)
low[i]=gra[pos][i];
low[pos]=0;vis[pos]=1;
for(int i=1;i<n;i++)
{
mini=INF;
for(int j=2;j<=n;j++)
if(!vis[j]&&mini>low[j]){
mini=low[j];
pos=j;
}
vis[pos]=1;
if(mini!=INF)
rsl+=mini;
for(int j=2;j<=n;j++)
if(!vis[j]&&low[j]>gra[pos][j])
low[j]=gra[pos][j];
}
return rsl;
}
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
for(int i=1;i<=n;i++)
gra[i][i]=0;
int tot=(n*(n-1))/2;
for(int i=0;i<tot;i++)
{
int a,b;
int u,v,len;
scanf("%d %d %d",&u,&v,&len);
gra[u][v]=gra[v][u]=len;
}
int ans=prim();
cout<<ans<<endl;
}
return 0;
}三、Kruskal算法
与Prim的基于顶点不同，Kruskal是一种基于边的算法。它的原理是，首先将一个连通图的所有边存起来，然后根据权值从小到大对这些边进行排序。然后每次按权值从小到大的顺序取出一条边，检查这条边的两个顶点是否在同一个集合内，若是，则这条边弃之不用且永远不会被使用(否则会产生闭环)；否则，选用这条边，作为最小生成树的其中一条边(即将两个这条边对应的两个顶点合并入一个集合中)。而在检查与合并的过程中，为了保证效率，我们可以使用并查集来实现。代码如下：
typedef struct{
int from,to,wei;
}edge; //y用一个结构体表示边
edge arr[5000];
bool cmp(edge a,edge b) //用于边的排序
{
return a.wei<b.wei;
}
void init()
{
for(int i=1;i<=n;i++){
pre[i]=i;
}
}
int findr(int x)
{
if(x==pre[x])
return x;
return pre[x]=findr(pre[x]); //找根节点同时进行压缩，提高往后查询时的效率
}
int kruskal()
{
int rsl=0;int num=0;
init();
for(int i=1;i<=m;i++)
{
int fx=findr(arr[i].from);
int fy=findr(arr[i].to); //找根节点
if(fx!=fy) //如果不在一个集合内，则合并
{
pre[fx]=fy;
rsl+=arr[i].wei;
num++;
}
}
if(num==n-1)
return rsl;
else
return -1;
}来一道Kruskal的模板题→HDU1875畅通工程再续
代码如下：
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <iostream>
#define INF 0x3f3f3f3f
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,m,idx1;
typedef struct{
int from,to;
double len;
}edge;
typedef struct{
double x,y;
}point;
point p[105];
edge e[5000];
int pre[105];
double get_len(point pa,point pb)
{
return sqrt((pa.x-pb.x)*(pa.x-pb.x)+(pa.y-pb.y)*(pa.y-pb.y));
}
bool cmp(edge e1,edge e2)
{
return e1.len<e2.len;
}
void init()
{
for(int i=1;i<=n;i++){
pre[i]=i;
}
}
int findr(int x)
{
if(x==pre[x])
return x;
return pre[x]=findr(pre[x]);
}
double kruskal()
{
double rsl=0;int num=0;
init();
for(int i=1;i<=idx1;i++)
{
int fx=findr(e[i].from);
int fy=findr(e[i].to);
if(fx!=fy)
{
pre[fx]=fy;
rsl+=e[i].len;
num++;
}
}
if(num==n-1)
return rsl;
else
return -1;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
double x,y;point tmp;
for(int i=1;i<=n;i++){
scanf("%lf %lf",&x,&y);
tmp.x=x;tmp.y=y;
p[i]=tmp;
}
idx1=1;
m=(n*(n-1))/2;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
edge temp;
temp.from=i;
temp.to=j;
temp.len=get_len(p[i],p[j]);
if(temp.len<=1000&&temp.len>=10)
e[idx1++]=temp;
}
}
sort(e,e+idx1,cmp);
double ans=kruskal();
if(ans==-1)
cout<<"oh!"<<endl;
else
printf("%.1lf\n",ans*100);
}
return 0;
} 两种算法的图解，可参考此文章→图的基本算法（最小生成树