图论学习 Prim算法求最小生成树
作者:
travel2.0
,
2024-01-27 10:23:01
,
所有人可见
,
阅读 54
Prim算法求最小生成树
个人见解:为什么用不到堆优化版的,可能卡数据的比较少吧,
类似Dijkstra 和spfa的关系
算法分析:
1.稠密图,邻接矩阵存储,无向图,两边都要存储;
2.初始化,自己分析一下,灵活处理重边和自环,负环问题;
3.核心算法:
(1)初始化任意一点到集合的距离为无穷大;
(2)第一层循环目的:确保将 1~n个点都放入集合中(无最小生成树除外)
(2)(第一次任意找点)第二层循环第一个的目的:
找到一个离集合最近的点,放入集合中;
(3)第二层循环第二个循环的目的:用t更新一下点到集合的最短距离(集合里的点也可以更新,不影响)!!!注意自环是负环的影响;
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 550;
int g[N][N],st[N];
int dist[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[j]<dist[t]))
t = j;
}
//第一个点要特判一下;
if(i && dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f;//无最小生成树;
if(i) res +=dist[t];//第一个点时,res = 0,等价于dist[t] = 0,res +=0;
st[t] = 1;
for(int j = 1;j <= n;j++){
dist[j] = min(dist[j],g[t][j]);
}
}
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 res = prim();
if(res == 0x3f3f3f3f) puts("impossible");
else cout<<res<<endl;
return 0;
}