算法基础之Prim算法求最小生成树
2023-12-18 19:29:45
Prim算法求最小生成树
-
核心思想:Prim 算法 类似于dijkstra算法 更新距离时改为到**集合(生成树)**的距离
-
最小生成树长这样 每次迭代放一个最近(有边)点,一条最短边进生成树
-
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 510, INF = 0x3f3f3f3f; int g[N][N]; //稠密图 int d[N]; //记录到集合距离 int n,m,res; //res记录集合内总权值 bool st[N]; int Prim(){ memset(d,0x3f,sizeof d); d[1] = 0; for(int i=0;i<n;i++) { int t = -1; //找最近的点 for(int j = 1;j<=n;j++) //找最近的点 { if(!st[j] && (t==-1 || d[t] > d[j])) //找最近的点 { t = j; } } if(d[t] == INF) return INF; //最短的距离是INF 说明没有联通的点 res += d[t]; //t加入集合 总权值加上t的 st[t] = true; for(int j=1;j<=n;j++) d[j] = min(d[j] , g[t][j]); //用t更新其他店距集合的距离 } 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; }
-
文章来源:https://blog.csdn.net/Pisasama/article/details/135069236
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!