算法基础系列第三章

2024-07-09 21:28| 来源: 网络整理| 查看: 265

🔔五道习题手把手拿捏普利姆算法以及克鲁斯卡尔算法 💓最小生成树算法大纲🌟最小生成树的基本概念🌻自由树和生成树🌻最小生成树 💓普利姆算法(prim)——模板题🌟通俗演示🌟例题描述🌟参考代码(C++版本)🌟算法模板🌟疑难杂症剖析 💓克鲁斯卡尔算法(Kruskal)——模板题🌟通俗演示🌟例题描述🌟参考代码(C++版本)🌟算法模板🌻疑难杂症剖析 💓例题一🌟解题报告🌻解题思路🌻参考代码（C++版本） 💓例题二🌟解题报告🌻解题思路🌻参考代码(C++版本)🌻疑难杂症剖析 💓例题三🌟解题报告🌻解题思路🌻参考代码(C++版本)🌻疑难杂症剖析 💓总结谢谢友友们耐心观看啦~，若有偏颇，欢迎及时私信指出喔💖💖💖基础算法持续更新中ing~

咱们先看看蓝桥杯对最小生成树的考察范围如下

考察范围

圈定的范围是考Prim算法和Kruskal算法。那接下来咱们就开始逐步了解最小生成树以及可爱的Prim算法和Kruskal算法吧 💓最小生成树算法大纲

最小生成树算法大纲

🌟最小生成树的基本概念 🌻自由树和生成树

自由树（树）： 1、自由树就是一个无回路的连通图（没有确定根） 2、n个顶点就一定有n-1条边

生成树： 1、包含全部顶点 2、n-1条边全部在图中

图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。

🌻最小生成树如果图G是一个连通图，G上的一棵各边权值之和最小的带权生成树，称为G的最小生成树。 💓普利姆算法(prim)——模板题 🌟通俗演示

Prim算法演示

🌟例题描述

Prim算法例题 🎇🎇🎇传送门🎇🎇🎇

因为这是用来做分析的模板题，题目要求里就很直接明了的指出，要咱们求最小生成树的树边权重之和。现在就可以直接去观察数据范围，可以看出是稠密图，那么我们可爱的Prim算法就可以掏出来啦~ 🌟参考代码(C++版本) #include #include #include #include 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); //res中存放最小生成树的树边权重之和 int res = 0; for(int i = 0; i < n;i++) { int t = -1; for(int j = 1; j dist[j])) t = j; //如果不是第一个点以及距离最小的点距离是正无穷，说明当前距离最近的点，到集合的距离都是正无穷，即当前图不连通 if(i && dist[t] == INF) return INF; if(i) res += dist[t]; //用t去更新其他点 for(int j = 1; j

【本文地址】

算法基础系列第三章

算法基础系列第三章

今日新闻

推荐新闻