Prim算法求最小生成树
首先在介绍这个算法之前我们要之明确一下什么是最小生成树的概念：
由 V 中的全部 n 个顶点和 E 中 n?1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图G 的最小生成树。
换言之，我们不能生成环且要让边权值和最小！
【Prim算法求最小生成树】
这里先介绍一个Prim算法：
Prim算法的思想和朴素版Dijkstra算法很像，我们也是去找当前集合外（这个集合就是我们的最小生成树）的离集合最近的点，我们用dist来表示
然后找到这个离集合最近的点之后，将这个的边权加入res，我们不用在乎这个点是和集合中的哪个点是连通的，我们只要知道这个连通的存在性即可
然后用当前的这个点去更新别的点到集合的距离，要注意这里更新的方法和Dijkstra略有不同，而且为了防备负权环的存在，我们要先把当前点入集合，最后再进行更新
然后迭代n次直到将所有的点都放入集合中
先上代码：
#include
#define maxn 510
using namespace std;
int g[maxn][maxn],INF = 0x3f3f3f3f;
int n,m;
int dist[maxn];
bool st[maxn];
int prim()
{
//这里是需要初始化所有集合外的点到集合的最短距离为无穷
memset(dist , 0x3f , sizeof dist);
int res = 0;
//这里要迭代n次，每次把一个集合外的点纳入集合
for(int i = 0;
i
//这里是在找到那个集合外的离集合最近的点
for(int j = 1;
j<=n;
j++)
if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
//如果离集合最近的点是无穷，说明根本不能连到集合，当然第一个点除外
if(i && dist[t] == INF) return INF;
st[t] = true;
//因为第一个点的dist是无穷，所以不用加，而且只有一个点是没有边权的
if(i) res += dist[t];
//用放进去的点来更新其他点到集合的最短距离
//且因为可能有负权环，所以要先入集合，最后更新
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 u,v,w;
cin >> u >> v >> w;
g[u][v] = g[v][u] = min(g[u][v] , w);
}
int t = prim();
if(t == INF) cout << "impossible" << '\n';
else cout << t << '\n';
return 0;
}
分析：这里有几个比较值得注意的点我们讲一下
·我们题目中是有可能出现重边的，所以我肯定要保留最小的那个边权，所以要先初始化取min
·我们要知道有时候是可能不存在最小生成树的，因为所有的点本身可能没有全部连通，判断方法就是看此时离集合最近的点的dist是不是无穷
·并且，第一个点具有特殊性，它是第一个点，dist还未被更新，肯定是无穷的，但是不能就这样说不连通，而且此时只是一个点还没有一条边，所以res也不需要加此时的dsit；
推荐阅读
- Python学习|Python 使用穷举法求两个数的最大公约数。
- 小程序渐变色吸顶
- 神经网络|目标检测算法YOLOv4详解
- python|经典非局部均值滤波(NLM)算法python实现(1)
- 图像处理|【OpenCv】图像分割——分水岭算法
- 与君共勉|【数据结构与算法】最小生成树与最短路径问题
- java|对数器验证算法正确性----bug寻找，文章中含有测试源码
- 人工智能|“2021年度全球十大人工智能治理事件”（数据、算法、伦理受关注，AI发展需治理同行）
- 图像处理|【OpenCv】图像分割——聚类算法
- 课程设计实验报告|本科课程【数据结构与算法】实验6 - 创建哈希表、最短路径（Dijkstra算法）