C++U7-10-最小生成树

news/2024/9/23 10:32:38

本节课作业讲解视频：

链接：https://pan.baidu.com/s/1lLlmhShdat9HuJWx7Rp_tA?pwd=0000
提取码：0000

 

 

最小生成树是一种在无向图中寻找特定结构的算法结果，它具有多种实际应用。以下是关于最小生成树的一些主要应用：

  1. 网络布局问题：
    • 在一个连通加权无向图中，最小生成树算法可以帮助找到一个包含所有顶点的最小权重树，从而在地图上实现有效的布局。这种布局能够确保连接所有点的路径的总成本最低。
  2. 地图着色问题：
    • 在地图着色问题中，最小生成树算法可以用于优化颜色分配。通过构建最小生成树，可以确保相邻区域的颜色不同，同时最小化所需的颜色数量。
  3. 车辆路径优化问题：
    • 在物流和运输行业中，最小生成树算法被用于优化车辆的行驶路径。这有助于降低运输成本，使车辆能够更高效地完成配送任务。
  4. 通信网络设计：
    • 在设计通信网络时，最小生成树算法有助于构建高效的数据传输网络。这种网络能够在不同的节点之间快速传输数据，同时确保传输成本最低。
  5. 电力系统设计：
    • 在电力系统的设计中，最小生成树算法被用于构建高效的输电网络。它确保了电能从发电厂到各个用户的传输过程中损耗最小。
  6. 城市光缆铺设：
    • 当需要在多个城市之间铺设光缆时，最小生成树算法可以帮助找到一种方案，使得所有城市之间都能实现通信，并且铺设光缆的总费用最低。

总结来说，最小生成树算法在多个领域都有广泛的应用，特别是在需要优化连接成本或传输效率的场合。通过构建最小生成树，可以确保在满足连通性的同时，实现成本的最小化。

 

 

 

 

 

Kruskal算法是一种用于解决最小生成树问题的贪心算法。最小生成树是一个无向连通带权图的一棵子图，它包含原图中的所有顶点，并且所有的边都是原图中的边，同时子图中边的权值之和最小。

Kruskal算法的基本思想是按照边的权值从小到大进行排序，然后从中选择边，但选择的边不能形成一个环。算法步骤如下：

  1. 初始化：创建一个空的图G'，该图包含原图G的所有顶点，但没有任何边。
  2. 创建一个空的集合S，用于存放已选择的边。
  3. 对原图G中的所有边按照权值进行升序排序。
  4. 遍历排序后的边列表，对于每条边e(u, v)：
    a. 如果顶点u和v在当前的图G'中不连通（即它们不在同一个连通分量中），则将边e添加到图G'和集合S中。
    b. 如果顶点u和v在当前的图G'中已经是连通的（即它们在同一个连通分量中），则跳过边e，不将其添加到图G'和集合S中。
  5. 重复步骤4，直到图G'包含n-1条边（n是顶点的数量），或者所有的边都已经遍历过。
  6. 最终的图G'就是原图G的最小生成树，集合S中的边就是最小生成树的边集。

为了判断两个顶点是否在同一连通分量中，可以使用并查集（Union-Find）数据结构。并查集可以高效地处理一些不交集的合并及查询问题。在Kruskal算法中，并查集用于判断添加某条边后是否会形成环。

需要注意的是，Kruskal算法的时间复杂度主要取决于边的排序，因此其时间复杂度为O(mlogm)，其中m是边的数量。如果使用Fibonacci堆来优化查找最小边的操作，时间复杂度可以降低到O(mloga)，其中a是边的权值的最大值与最小值之比。然而，在实际应用中，由于排序操作的高效性，简单的排序通常已经足够快了。

 

 算法步骤 视频：【数据结构——两分钟搞定最小生成树Kruskal算法】 https://www.bilibili.com/video/BV1do4y1v7KZ/?share_source=copy_web&vd_source=d28947bf5669866688dc057b3c41b450

 

 

[【最小生成树】最小生成树]

 

 

【算法分析】
【kruskal】为了造出一棵最小生成树，我们从最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了 n−1 条边，即形成了一棵树，判断是否出现环可以使用并查集。【prim】Prim 算法同样基于上述推论，但思路略有不同。Prim 算法总是维护最小生成树的一部分，即不断向一棵“子最小生成树”中添加节点，直至得到最终结果。最初，Prim 算法仅确定 1 号节点属于最小生成树。
在任意时刻，设已经确定属于最小生成树的部分的节点集合为 T，剩余节点集合为 S。Prim 算法每次找到两个端点分别属于结合 S , T 的权值最小的边 (x,y,z)，然后把点 x 从集合 S 中删除，加入到集合 T，并把 z 累加到答案中。
类比 Dijkstra 算法，我们可以用一个标记数组标记节点是否属于 T。每次从未标记的节点中选出 d 值最小的，把他标记（加入 T ），同时扫描其所有出边，更新另一个端点的 d 值。【参考代码】
//kruskal
#include<bits/stdc++.h>
using namespace std;const int maxn = 2e5 + 9;
struct node {int x, y, z;
}a[maxn];
int fa[5009];
int get(int x) {if (fa[x] == x) return x;return fa[x] = get(fa[x]);
}
void merge(int x, int y) {fa[get(x)] = get(y);
}
bool cmp(node A, node B) {return A.z < B.z;
}
int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) fa[i] = i;for (int i = 0; i < m; i++) {cin >> a[i].x >> a[i].y >> a[i].z;}sort(a, a + m, cmp);int ans = 0, edge = 0;for (int i = 0; i < m; i++) {if (get(a[i].x) == get(a[i].y)) continue;merge(a[i].x, a[i].y);edge++;ans += a[i].z;}if (edge == n - 1) cout << ans;else cout << "orz";return 0;
}
//prim
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int a[5009][5009];
int d[5009], vis[5009];
int n, m;
bool prim() {memset(d, 0x3f, sizeof(d));memset(vis, 0, sizeof(vis));d[1] = 0;for (int i = 1; i <= n; i++) { //每次向集合T中加入一个点int x = 0;for (int j = 1; j <= n; j++) { //找到离T集合最近的点if (!vis[j] && d[j] < d[x]) x = j;}if (x == 0) return false; //没有找到点，说明其他点都与T集合不连通vis[x] = 1; //标记，相当于把点x加入T集合for (int y = 1; y <= n; y++) { //去更新S集合的点到T集合的距离if(!vis[y]) d[y] = min(d[y], a[x][y]);}}return true;
}
int main() {cin >> n >> m;memset(a, 0x3f, sizeof(a));for (int i = 0; i < m; i++) {int x, y, z;cin >> x >> y >> z;a[x][y] = min(a[x][y], z);a[y][x] = min(a[y][x], z);}if (prim()) {int ans = 0;for (int i = 2; i <= n; i++) ans += d[i];cout << ans;}else cout << "orz";return 0;
}
View Code

 

 

[【最小生成树】畅通工程]

 

 

【算法分析】
【kruskal】为了造出一棵最小生成树，我们从最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了 n−1 条边，即形成了一棵树，判断是否出现环可以使用并查集。【prim】Prim 算法同样基于上述推论，但思路略有不同。Prim 算法总是维护最小生成树的一部分，即不断向一棵“子最小生成树”中添加节点，直至得到最终结果。最初，Prim 算法仅确定 1 号节点属于最小生成树。
在任意时刻，设已经确定属于最小生成树的部分的节点集合为 T，剩余节点集合为 S。Prim 算法每次找到两个端点分别属于结合 S , T 的权值最小的边 (x,y,z)，然后把点 x 从集合 S 中删除，加入到集合 T，并把 z 累加到答案中。
类比 Dijkstra 算法，我们可以用一个标记数组标记节点是否属于 T。每次从未标记的节点中选出 d 值最小的，把他标记（加入 T ），同时扫描其所有出边，更新另一个端点的 d 值。【参考代码】
//kruskal
#include<bits/stdc++.h>
using namespace std;const int maxn = 2e5 + 9;
struct node {int x, y, z;
}a[maxn];
int fa[5009];
int get(int x) {if (fa[x] == x) return x;return fa[x] = get(fa[x]);
}
void merge(int x, int y) {fa[get(x)] = get(y);
}
bool cmp(node A, node B) {return A.z < B.z;
}
int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) fa[i] = i;for (int i = 0; i < m; i++) {cin >> a[i].x >> a[i].y >> a[i].z;}sort(a, a + m, cmp);int ans = 0, edge = 0;for (int i = 0; i < m; i++) {if (get(a[i].x) == get(a[i].y)) continue;merge(a[i].x, a[i].y);edge++;ans += a[i].z;}if (edge == n - 1) cout << ans;else cout << "no";return 0;
}
//prim
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int a[5009][5009];
int d[5009], vis[5009];
int n, m;
bool prim() {memset(d, 0x3f, sizeof(d));memset(vis, 0, sizeof(vis));d[1] = 0;for (int i = 1; i <= n; i++) { //每次向集合T中加入一个点int x = 0;for (int j = 1; j <= n; j++) { //找到离T集合最近的点if (!vis[j] && d[j] < d[x]) x = j;}if (x == 0) return false; //没有找到点，说明其他点都与T集合不连通vis[x] = 1; //标记，相当于把点x加入T集合for (int y = 1; y <= n; y++) { //去更新S集合的点到T集合的距离if(!vis[y]) d[y] = min(d[y], a[x][y]);}}return true;
}
int main() {cin >> n >> m;memset(a, 0x3f, sizeof(a));for (int i = 0; i < m; i++) {int x, y, z;cin >> x >> y >> z;a[x][y] = min(a[x][y], z);a[y][x] = min(a[y][x], z);}if (prim()) {int ans = 0;for (int i = 2; i <= n; i++) ans += d[i];cout << ans;}else cout << "no";return 0;
}
View Code

 

 

Prim算法是一种在图论中用于在加权连通图中搜索最小生成树的算法。以下是关于Prim算法的详细解释：

定义

Prim算法是一种贪心算法，用于在加权连通图中找到一棵包含所有顶点的最小生成树。这意味着，由该算法搜索到的边子集所构成的树中，不仅包括了连通图里的所有顶点，而且其所有边的权值之和也是最小的。

历史背景

  • Prim算法最初由捷克数学家沃伊捷赫·亚尔尼克（Vojtěch Jarník）于1930年发现。
  • 随后，在1957年，美国计算机科学家罗伯特·普里姆（Robert C. Prim）独立发现了该算法。
  • 由于艾兹格·迪科斯彻（Edsger Dijkstra）在1959年也发现了类似的算法，因此在某些场合，Prim算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

算法步骤

  1. 输入：一个加权连通图，其中顶点集合为V，边集合为E。
  2. 初始化：
    • 选择V中的任一节点作为起始点，加入集合U（已访问节点的集合）。
    • 初始化一个距离数组dist[]，用于记录从起始点到其他所有节点的最短距离（初始时，除了起始点外，其他节点的距离都设为无穷大）。
    • 初始化一个最小边集合MST，开始时为空。
  3. 重复以下操作，直到U = V：
    • 在集合E中选取一条边(u, v)，其中u在U中，v不在U中，且这条边的权值在所有满足条件的边中是最小的。
    • 将v加入集合U中，并将边(u, v)加入MST中。
    • 更新dist[]数组，考虑通过新加入的节点v，是否可以更新起始点到其他节点的最短距离。
  4. 输出：使用集合U和MST来描述所得到的最小生成树。

时间复杂度

  • 使用邻接矩阵图表示的简易实现中，Prim算法的时间复杂度为O(V^2)，其中V是顶点的数量。
  • 使用简单的二叉堆与邻接表来表示的话，Prim算法的运行时间可缩减为O(ElogV)，其中E是边的数量。
  • 如果使用较为复杂的斐波那契堆，则可将运行时间进一步缩短为O(E+VlogV)。

应用场景

Prim算法广泛应用于各种需要找到最小成本网络或路径的问题中，例如城市规划、通信网络建设、电路设计等。在这些场景中，通过Prim算法可以找到连接所有点所需的最短总路径或最低成本路径。

 
 算法步骤参考视频：【数据结构——四分钟搞定Prim算法】 https://www.bilibili.com/video/BV1Cv4y1s7kU/?share_source=copy_web&vd_source=d28947bf5669866688dc057b3c41b450

 

 

[【最小生成树】最小生成树]

 

//prim
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int a[5009][5009];
int d[5009], vis[5009];
int n, m;
bool prim() {memset(d, 0x3f, sizeof(d));memset(vis, 0, sizeof(vis));d[1] = 0;for (int i = 1; i <= n; i++) { //每次向集合T中加入一个点int x = 0;for (int j = 1; j <= n; j++) { //找到离T集合最近的点if (!vis[j] && d[j] < d[x]) x = j;}if (x == 0) return false; //没有找到点，说明其他点都与T集合不连通vis[x] = 1; //标记，相当于把点x加入T集合for (int y = 1; y <= n; y++) { //去更新S集合的点到T集合的距离if(!vis[y]) d[y] = min(d[y], a[x][y]);}}return true;
}
int main() {cin >> n >> m;memset(a, 0x3f, sizeof(a));for (int i = 0; i < m; i++) {int x, y, z;cin >> x >> y >> z;a[x][y] = min(a[x][y], z);a[y][x] = min(a[y][x], z);}if (prim()) {int ans = 0;for (int i = 2; i <= n; i++) ans += d[i];cout << ans;}else cout << "orz";return 0;
}
View Code

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.ryyt.cn/news/46810.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈，一经查实，立即删除！

相关文章

NSIS 入门教程 (三)

NSIS 入门教程 (三)

引言在教程的第二部分中，我们为安装程序增加了一个卸载程序，并查看了一些其他的向导页面以及安装部分的选择。第三部分的目标是使安装程序的外观更加现代化。更现代的外观为了给安装程序一个更现代的外观，我们要启用现代用户界面。要提升我们的安装程序（基于“secondinstal…
阅读更多...
惠普塔式服务器数据恢复

惠普塔式服务器数据恢复

惠普塔式服务器，5块1000GB的SAS硬盘组成raid5磁盘阵列服务器检测： 硬盘掉线服务器崩溃，其中一块硬盘掉线很久，现又有一块硬盘掉线。 故障分析： 服务器底层数据检测发现数据并没有明显的同步痕迹。将服务器内的硬盘按照顺序编号并贴好标签后取出服务器盘位，对物理硬盘进行…
阅读更多...
泓优阁整理的一些轻创业的项目分享

泓优阁整理的一些轻创业的项目分享

对于当代年轻人来说，除了工作，很多人想去低成本创业，或改善自己的生活，或图谋未来的发展，那么以下一些轻创业项目分享给大家。1，品牌代购 随着经济水平的提高和互联网的普及，代购行业也逐渐成为新的创业热点，它为人们提供了方便的购物服务，也能实现工作之余客观的收入…
阅读更多...
IBM服务器数据恢复

IBM服务器数据恢复

服务器数据恢复背景： 一台X3850服务器，这台服务器在运行过程中突然崩溃，服务器崩溃前从未进行过维护，不清楚硬件状况，服务器操作系统为linux，运行oracle数据库。 经检测，初步判定该服务器上共有5块硬盘，其中4块硬盘组成riad5磁盘阵列，1块硬盘位热备盘，其中raid5磁盘阵…
阅读更多...
服务器硬盘磁头损坏，盘片划伤数据恢复

服务器硬盘磁头损坏，盘片划伤数据恢复

服务器硬盘故障： Dell服务器，raid阵列上有一块硬盘出现故障，经过检测发现硬盘问题，后续在无尘台开盘处理，发现盘片损伤严重；初步判断也存在硬件故障。服务器硬盘数据恢复过程： 1、发现开盘的盘面有规则的同心圆状划痕，这是典型的磁头出现故障而划伤盘面的情况，这种情况…
阅读更多...
Orleans初体验

Orleans初体验

Orleans：是一个跨平台框架，用于构建可靠且可缩放的分散式应用。 分布式应用定义为跨多个进程的应用，通常使用对等通信来超越硬件边界。 从单个本地服务器扩展到了云中数千个分布式、高度可用的应用。 将熟悉的概念和 C# 习语扩展到了多服务器环境。 在设计上可弹性缩放。 当…
阅读更多...
9. Mybatis 小技巧

9. Mybatis 小技巧

1. #{ } 和 $#{ } 和 ${ } 的区别 #{ }：先编译sql语句，再给占位符传值，底层是PreparedStatement实现。可以防止sql注入，比较常用。 ${}：先进行sql语句拼接，然后再编译sql语句，底层是Statement实现。存在sql注入现象。只有在需要进行sql语句关键字拼接的情况下才会用到。…
阅读更多...
DK盾VPS，您的专属云上堡垒

DK盾VPS，您的专属云上堡垒

【探索未来网络的无限可能 —— DK盾VPS，您的专属云上堡垒】 在数字化浪潮中，稳定、高效、安全的网络服务是企业与个人用户追求卓越的关键。DK盾VPS，作为新一代虚拟专用服务器的杰出代表，正以卓越的性能和全方位的安全防护，引领着云服务的新潮流。 【性能卓越，畅享极速体…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 尧图建网站 广利置业