生成树
生成树是连通图的最小连通子图。所谓最小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。按照该定义，n个顶点的连通网络的生成树有n个顶点，n-1条边。
最小生成树
设G=(V,E)是一个无向连通图,生成树上各边的权值之和称为该生成树的代价，在G的所有生成树中，代价最小的生成树称为最小生成树(minimal spanning tree)
普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是两个利用MST性质构造最小生成树的经典算法。
MST性质
最小生成树具有MST性质:假设G=(V,E)是一个无向连通图，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V-U,则必存在一颗包含边(u,v)的最小生成树。
Prim算法
Prim算法的基本思想是:设G = (V,E)是一个无项联通网，令T = (U,TE)是G的最小生成树。T的初始状态为U={v0},(v0∈V)，TE={ },然后重复执行下述操作：在所有的u∈U，v∈V-U的边中找一条代价最小的边(u,v)并入集合TE,同时v并入U,直至U=V为止。此时TE中必有n-1条边，则T就是一颗最小生成树。Prim算法的基本思想伪代码如下:
1.初始化:U={ v0};TE={ } ;
2.重复下述操作直到U=V：
2.1 在E中寻找最短边(u,v),且满足u∈U,v∈V-U
2.2 U = U +{ v }
2.3 TE = TE +{ (u,v) }
设置一个数组shortEdge[n]表示候选最短边集，数组元素包括adjvex和lowcast两个域，分别表示候选最短边的邻接点和权值.
Prim算法用伪代码描述为:
1.初始化辅助数组shortEdge[n];
2.输出顶点v0,将顶点0加入集合U中；
3.重复执行下列操作n-1次；
3.1 在shortEdge[n].lowcast中选取最短边及对应的临界点编号k；
3.2 输出顶点k和对应的权值；
3.3 将顶点k加入集合U中；
3.4 调整数组shortEdge[n];
Prim实现函数代码如下:
#include<bits/stdc++.h>
using namespace std;
#define inf 0x7fffffff//无穷大
#define maxn 5005
int cost[maxn][maxn],minn;
int n,m,v2[maxn],tot=1,now,ans;
bool v1[maxn];//v1为标记数组，v2为顶点到当前顶级的权值。
void getcost()
{
scanf("%d%d",&n,&m);//读入点和边
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cost[i][j]=inf;//初始化，将全部边设为无穷大
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);//读入起始点,目标点和位权
if(cost[u][v]>w)//表示两个顶点是联通的.
cost[u][v]=cost[v][u]=w;//无向图只有一条路,双向
}//初始化cost数组,v2表示起始点到个点的距离
for(int i=1;i<=n;i++)
v2[i]=cost[1][i];
v1[1]=1;//找出与1节点相连的边并进行标记
}
int prim()
{
while(tot<n)//最小生成树的概念,只用n-1条边就行
{
minn=inf;
tot++; //循环一个加一
for(int i=1;i<=n;i++){
if(!v1[i]&&v2[i]<minn){
minn=v2[i];//最小值
now=i;//顶点编号
}
}//找出与顶点联通且是最小边
ans+=minn;//更新答案
for(int i=1;i<=n;i++)
if(!v1[i]&&v2[i]>cost[now][i])//在没有标记的点中,找出一条
//自己到自己的距离为无穷大
v2[i]=cost[now][i];//更新与已知边的最短距离,不一定要1号顶点,
//此时v2不再表示1号顶点到个顶点的距离
v1[now]=1;//在找出与now节点相连的边并进行标记
}
return ans;
}
int main()
{
getcost();
printf("%d",prim());
return 0;
}
代码说明:
第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）
接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi.
输出包含一个数，即最小生成树的各边的长度之和；
输入数据
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出结果7
PS:题目来自于洛谷
