本文主要是介绍最小生成树 - 朴素Prim算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
朴素Prim算法适用于稠密图 O(n^2)
最小生成树当中是不允许有自环的
输入格式
第一行包含两个整数n和m。
接下来m行，每行包含三个整数u，v，w，表示点u和点v之间存在一条权值为w的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出impossible.
数据范围
1<n< 5001 ≤m ≤ 105
图中涉及边的边权的绝对值均不超过10000。
输入样例
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例
6
// 最小生成树 —朴素Prim
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;const int N=510,INF=0x3f3f3f3f;
int n,m;
int g[N][N];
int dist[N];
bool st[N];int prim()
{memset(dist,0x3f,sizeof dist);int res=0;for(int i=0;i<n;i++){int t=-1;//找到集合外距离集合最近的点for(int j=1;j<=n;j++)if(!st[j] && (t==-1||dist[t]>dist[j]))t=j;if(i && t==INF) return INF;//先累加再更新if(i) res+=dist[t];//用 t 来更新其它的点for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);st[t]=true;}return res;
}int main()
{cin>>n>>m;memset(g,0x3f,sizeof g);while(m--){int a,b,c;cin>>a>>b>>c;g[a][b]=g[b][a]=min(g[a][b],c);}int t=prim();if(t==INF) puts("impossible");else cout<<t<<endl;return 0;
}这篇关于最小生成树 - 朴素Prim算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
