【ACM】最小生成树（Prim算法）

本文主要是介绍【ACM】最小生成树（Prim算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法分析：
prim算法适合稠密图，时间复杂度为O(n^2),时间复杂度与边的条数无关。
概念：
边带有权值的图称为带权图或者网，带权图的生成树也是带权的，生成树T各边的权值总和称为该树的权。
1.最小生成树（MST）：权值最小的生成树。
2.构造最小生成树应该满足一下两个性质：
尽可能的选取权值小的边，但是不能构成回路。
选取n-1条恰当的边连通n个顶点。

MST性质：
假设G=(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V-U，则必存在一棵包含边(u,v)的最小生成树。（U是待完成的最小生成树的点的集合）

基本思路：
假设G=(V，E)是连通的，TE是G上最小生成树中边的集合。算法的开始状态是U={u0}（u0∈V），TE={}。重复执行以下的操作：
在所有的u∈U，v∈V-U的边(u,v)∈E中找一条权值最小的边(u0,v0)加入集合TE中，同时v0放入U中，直到V=U为止。

模板代码：

#include <cstring>
#include <cstdio>
#include <algorithm>
#define maxn 1005using namespace std;
const int INF = 0x3f3f3f3f;int sum;
int _cout;
int e[maxn][maxn];
bool vis[maxn]; //记录每一个结点是否已经在最小生成树中，如果已经被放入，则为true
int dis[maxn];  //保存临时距离的数组
int min_w;int main()
{int n,m; //n表示结点的数量，m表示给出的信息量；int t1,t2,t3; //设置3个临时变量int node; //保存临时结点while(scanf("%d %d",&n,&m) == 2){//数组初始化memset(vis,false,sizeof(vis));sum = 0;_cout = 0;//初始化邻接矩阵，对角线上的元素表示点自身，所以初始化为0，其他的初始化为一个极大值for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i == j)e[i][j] = 0;elsee[i][j] = INF;}} //读取数据for(int i=1;i<=m;i++){scanf("%d %d %d",&t1,&t2,&t3);//无向图对称化处理e[t1][t2] = t3;e[t2][t1] = t3;}for(int i=1;i<=n;i++){dis[i] = e[1][i]; //先把1结点放进最小生成树，dis数组记录了从1结点到其他结点的权值}vis[1] = true;//下面开始构建最小生成树for(int i=2;i<=n;i++)  //第一个结点已经放入最小生成树，因此遍历起始点从2开始{min_w = INF;     //把最小权重表示为一个最大值，因为在下面的比较中会存在权重为INF的边for(int j=1;j<=n;j++){if(dis[j] < min_w && !vis[j]){min_w = dis[j];   //遍历找到最小权值边node = j; //保存并更新具有最小权值的结点}}vis[node] = true;sum += min_w;for(int j=1;j<=n;j++){/*每次插入一个点都要进行更新dis数组的值，dis数组保存的是当前最小生成树的所有结点中到结点j的最小权值*/if(!vis[j] && dis[j] > e[node][j])dis[j] = e[node][j];}}printf("%d\n",sum);}return 0;
}