最小生成树详解(模板 + 例题)

article/2025/9/16 13:42:04

作为一个伪ACMer,先来首广为人知的打油诗:
模拟只会猜题意，贪心只能过样例，数学上来先打表，规律一般是DP，组合数学碰运气，计算几何瞎暴力，图论一顿套模板，数论只会GCD,递归递推伤不起，搜索茫然TLE，分治做得像枚举，暴力枚举数第一，数据结构干瞪眼，怒刷水题找信心。

在这里插入图片描述

文章目录

    • 1、什么是树
    • 2、最小生成树
    • 3、最小生成树的应用
    • 4、实现最小生成树的两种算法
      • 4.1 prim (普里姆算法)
      • 4.2 kruskal (克鲁斯卡尔算法)
    • 5、总结

1、什么是树

如果一个无向连通图不包含回路(连通图中不存在环),那么就是一个树。

在这里插入图片描述

2、最小生成树

一个图中可能存在多条相连的边,我们一定可以从一个图中挑出一些边生成一棵树。这仅仅是生成一棵树,还未满足最小,当图中每条边都存在权重时,这时候我们从图中生成一棵树(n - 1 条边)时,生成这棵树的总代价就是每条边的权重相加之和。

在这里插入图片描述

一个有N个点的图，边一定是大于等于N-1条的。图的最小生成树，就是在这些边中选择N-1条出来，连接所有的N个点。这N-1条边的边权之和是所有方案中最小的。

3、最小生成树的应用

要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

4、实现最小生成树的两种算法

4.1 prim (普里姆算法)

算法分析:

Prim算法每次循环都将一个蓝点u变为白点，并且此蓝点u与白点相连的最小边权min[u]还是当前所有蓝点中最小的。这样相当于向生成树中添加了n-1次最小的边，最后得到的一定是最小生成树。

我们通过对下图最小生成树的求解模拟来理解上面的思想。蓝点和虚线代表未进入最小生成树的点、边；白点和实线代表已进入最小生成树的点、边。

初始时所有点都是蓝点，min[1]=0,min[2、3、4、5]=∞。权值之和MST=0。

在这里插入图片描述

第一次循环自然是找到min[1]=0最小的蓝点1。将1变为白点，接着枚举与1相连的所有蓝点2、3、4，修改它们与白点相连的最小边权。

在这里插入图片描述

min[2]=w[1][2]=2;
min[3]=w[1][3]=4;
min[4]=w[1][4]=7；
第二次循环是找到min[2]最小的蓝点2。将2变为白点，接着枚举与2相连的所有蓝点3、5，修改它们与白点相连的最小边权。

在这里插入图片描述

min[3]=w[2][3]=1;
min[5]=w[2][5]=2;

第三次循环是找到min[3]最小的蓝点3。将3变为白点，接着枚举与3相连的所有蓝点4、5，修改它们与白点相连的最小边权。

在这里插入图片描述

min[4]=w[3][4]=1;
由于min[5]=2 < w[3][5]=6;所以不修改min[5]的值。
最后两轮循环将点4、5以及边w[2][5],w[3][4]添加进最小生成树。

在这里插入图片描述

最后权值之和MST=6。这n次循环，每次循环我们都能让一个新的点加入生成树，n次循环就能把所有点囊括到其中；每次循环我们都能让一条新的边加入生成树，n-1次循环就能生成一棵含有n个点的树；每次循环我们都取一条最小的边加入生成树，n-1次循环结束后，我们得到的就是一棵最小的生成树。这就是Prim采取贪心法生成一棵最小生成树的原理。算法时间复杂度：O (N2)。

精彩例题:

在这里插入图片描述
在这里插入图片描述

题目链接:https://www.acwing.com/problem/content/860/

Code:

	// prim 算法求最小生成树 #include <cstdio>#include <string>#include <cstring>#include <iostream>#include <algorithm>#define INF 0x3f3f3f3fusing namespace std;const int maxn = 505;int a[maxn][maxn];int vis[maxn],dist[maxn];int n,m;int u,v,w;long long sum = 0;int prim(int pos) {dist[pos] = 0;// 一共有 n 个点,就需要 遍历 n 次,每次寻找一个权值最小的点,记录其下标for(int i = 1; i <= n; i ++) {int cur = -1;for(int j = 1; j <= n; j ++) {if(!vis[j] && (cur == -1 || dist[j] < dist[cur])) {cur = j;}}// 这里需要提前终止if(dist[cur] >= INF) return INF;sum += dist[cur];vis[cur] = 1;for(int k = 1; k <= n; k ++) {// 只更新还没有找到的最小权值if(!vis[k]) dist[k] = min(dist[k],a[cur][k]);}}return sum;}int main(void) {scanf("%d%d",&n,&m);memset(a,0x3f,sizeof(a));memset(dist,0x3f,sizeof(dist));for(int i = 1; i <= m; i ++) {scanf("%d%d%d",&u,&v,&w);a[u][v] = min(a[u][v],w);a[v][u] = min(a[v][u],w);}int value = prim(1);if(value >= INF) puts("impossible");else printf("%lld\n",sum);return 0;}

4.2 kruskal (克鲁斯卡尔算法)

Kruskal（克鲁斯卡尔）算法是一种巧妙利用并查集来求最小生成树的算法。

算法描述:

在描述 kruskal 算法时先了解一下连通块的概念, 我们将无向图中相互连通的一些点称为处于同一个连通块中。

在这里插入图片描述

从上图我们可以清晰的看到,有 3 个连通块(1,2),(3),(4,5,6)。

Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序（一般使用快排），并认为每一个点都是孤立的，分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。直到选取了n-1条边为止。

Kruskal（克鲁斯卡尔）算法开始时，认为每一个点都是孤立的，分属于n个独立的集合。

在这里插入图片描述

5个集合{ {1}，{2}，{3}，{4}，{5} }

生成树中没有边
Kruskal每次都选择一条最小的边，而且这条边的两个顶点分属于两个不同的集合。将选取的这条边加入最小生成树，并且合并集合。
第一次选择的是<1,2>这条边，将这条边加入到生成树中，并且将它的两个顶点1、2合并成一个集合。

在这里插入图片描述

4个集合{ {1，2}，{3}，{4}，{5} }
生成树中有一条边{ <1,2> }
第二次选择的是<4,5>这条边，将这条边加入到生成树中，并且将它的两个顶点4、5合并成一个集合。

在这里插入图片描述

3个集合{ {1，2}，{3}，{4，5} }
生成树中有2条边{ <1,2> ，<4,5>}
第三次选择的是<3,5>这条边，将这条边加入到生成树中，并且将它的两个顶点3、5所在的两个集合合并成一个集合

在这里插入图片描述

2个集合{ {1，2}，{3，4，5} }
生成树中有3条边{ <1,2> ，<4,5>，< 3，5>}
第四次选择的是<2,5>这条边，将这条边加入到生成树中，并且将它的两个顶点2、5所在的两个集合合并成一个集合。

在这里插入图片描述

1个集合{ {1，2，3，4，5} }
生成树中有4条边{ <1,2> ，<4,5>，< 3，5>，<2,5>}
算法结束，最小生成树权值为19。

通过上面的模拟能够看到，Kruskal算法每次都选择一条最小的，且能合并两个不同集合的边，一张n个点的图总共选取n-1次边。因为每次我们选的都是最小的边，所以最后的生成树一定是最小生成树。每次我们选的边都能够合并两个集合，最后n个点一定会合并成一个集合。通过这样的贪心策略，Kruskal算法就能得到一棵有n-1条边，连接着n个点的最小生成树。

精彩例题:

在这里插入图片描述
在这里插入图片描述

题目链接:https://www.acwing.com/problem/content/861/

Code:

	// Kruskal 算法求最小生成树 #include <cstdio>#include <string>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int maxn = 2e5 + 10; struct node {int x,y,z;}edge[maxn];bool cmp(node a,node b) {return a.z < b.z;}int fa[maxn];int n,m;int u,v,w; long long sum;int get(int x) {return x == fa[x] ? x : fa[x] = get(fa[x]);}int main(void) {scanf("%d%d",&n,&m);for(int i = 1; i <= m; i ++) {scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);}for(int i = 0; i <= n; i ++) {fa[i] = i;}sort(edge + 1,edge + 1 + m,cmp);// 每次加入一条最短的边for(int i = 1; i <= m; i ++) {int x = get(edge[i].x);int y = get(edge[i].y);if(x == y) continue;fa[y] = x;sum += edge[i].z;}int ans = 0;for(int i = 1; i <= n; i ++) {if(i == fa[i]) ans ++;}if(ans > 1) puts("impossible");else printf("%lld\n",sum);return 0;}

5、总结

从上面的两道模板可得知,解决最小生成树的问题一般有两种方式:prim 和 Kruskal ,那么,什么时候选择哪种策略就成为了我们应该思考的一个问题:
稀疏图一般选择 prim,采用 邻接矩阵 进行存储边之间的关系。
稠密图一般选择 Kruskal ,采用邻接表进行存储边之间的关系(更多采用结构体的方式)。

参考链接:https://www.cnblogs.com/SeanOcean/p/10975694.html


http://chatgpt.dhexx.cn/article/BFys0PHc.shtml

相关文章

Linux开启/关闭防火墙

Linux开启/关闭防火墙

一、查看防火墙状态&#xff1a; systemctl status firewalldinactive表示防火墙为关闭状态。 二、开启防火墙&#xff1a; systemctl start firewalld启动后无任何提示&#xff0c;再次查看防火墙状态&#xff0c;可以看到变成active&#xff0c;成功启动。 三、关闭防火墙…
阅读更多...
linux服务器查看防火墙是否关闭,linux查看防火墙是否关闭了的方法

linux服务器查看防火墙是否关闭,linux查看防火墙是否关闭了的方法

linux查看防火墙是否关闭了的方法 发布时间&#xff1a;2020-04-02 10:49:28 来源&#xff1a;亿速云 阅读&#xff1a;62 作者&#xff1a;小新 今天小编给大家分享的是linux查看防火墙是否关闭了的方法&#xff0c;很多人都不太了解&#xff0c;今天小编为了让大家更加了解li…
阅读更多...
linux操作系统关闭防火墙,linux操作系统关闭防火墙的方法

linux操作系统关闭防火墙,linux操作系统关闭防火墙的方法

防火墙是一项协助确保信息安全的设备，会依照特定的规则，允许或是限制传输的数据通过。简单的来说防火墙的作用就是保护你的网络免受非法用户的侵入，虽然防火墙是为了你网络安全而存在，但是同时也限制了你上网操作，有很多人会选择关闭防火墙，windows操作系统的防火墙好关闭…
阅读更多...
linux为什么要关闭防火墙,Linux怎么样关闭防火墙

linux为什么要关闭防火墙,Linux怎么样关闭防火墙

Linux系统下面自带了防火墙iptables&#xff0c;iptables可以设置很多安全规则。但是如果配置错误很容易导致各种网络问题&#xff0c;那么如果要关闭禁用防火墙怎么操作呢?下面就让学习啦小编给大家说说Linux怎么关闭防火墙吧。 Linux关闭防火墙的方法 如果启动的iptables防火…
阅读更多...
linux防火墙的开启、关闭、永久关闭

linux防火墙的开启、关闭、永久关闭

防火墙是什么&#xff1f;我们为什么需要关闭防火墙&#xff1f; 防火墙就是一个保护我们系统的软件服务&#xff0c;默认开启&#xff0c;但是我们在实际开发中&#xff0c;如果需要使用宿主机来连接虚拟机里面的redis, mysql&#xff0c;nginx&#xff0c;tomcat等服务&#…
阅读更多...
linux防火墙能关吗,linux防火墙怎么样关闭

linux防火墙能关吗,linux防火墙怎么样关闭

有没有什么方法可以关闭linux防火墙呢?方法是有的&#xff0c;小编来告诉你!下面由学习啦小编给你做出详细的linux防火墙关闭方法介绍!希望对你有帮助! linux防火墙关闭方法一&#xff1a; 1) 重启后生效 开启&#xff1a; chkconfig iptables on 关闭&#xff1a; chkconfig …
阅读更多...
Linux防火墙关闭（重启）操作（centos）

Linux防火墙关闭（重启）操作（centos）

1:查看防火墙状态 systemctl statu firewalld 此状态表示防火墙禁用状态 此状态表示防火墙处于开启状态 2:暂时关闭防火墙 systemctl stop firewalld 3:启用防火墙&#xff08;关闭状态使用&#xff09; systemctl start firewalld 4:重启防火墙&#xff08;输入命令后防火墙先…
阅读更多...
Linux 开启关闭防火墙操作

Linux 开启关闭防火墙操作

1. linux中防火墙相关操作 1.1 查看防火墙状态 systemctl status firewalld如下所示表示防火墙是运行状态&#xff0c; 8080&#xff0c; 3306&#xff0c; 6379表示我开放了这个端口给外部访问 或者 firewall-cmd --state1.2 暂时关闭防火墙(重启服务器防火墙会重新开启) …
阅读更多...
【Linux】如何关闭Linux防火墙

【Linux】如何关闭Linux防火墙

在访问linux时&#xff0c;如果linux防火墙是开启状态&#xff0c;则无法访问其提供的服务&#xff0c;为此&#xff0c;需要将Linux的防火墙关闭&#xff0c;命令如下[1]&#xff1a; 查看防火墙状态 firewall -cmd --state关闭防火墙 systemctl stop firewalld.serv…
阅读更多...
linux防火墙关闭启用增减端口号命令

linux防火墙关闭启用增减端口号命令

查看防火墙信息 firewall-cmd --list-all 查看防火墙状态 firewall-cmd --state systemctl status firewalld 添加端口号到防火墙中&#xff0c;永久有效是写入配置文件&#xff0c;可以不加--permanent但重启服务器后会失效 firewall-cmd --permanent --add-port18082/tcp …
阅读更多...
Linux防火墙的关闭

Linux防火墙的关闭

查看防火墙的状态 打开终端输入如下命令 systemctl status firewalld 如图所示&#xff1a;running表示防火墙目前处于打开状态 输入命令进行关闭防火墙&#xff1a; systemctl stop firewalld 如图所示正常的用户是没有权限的&#xff0c;需要输入管理员的密码才能够进行关闭防…
阅读更多...
python随机抽取样本1500个_（python）随机抽样

python随机抽取样本1500个_（python）随机抽样

随机抽样法就是调查对象总体中每个部分都有同等被抽中的可能,是一种完全依照机会均等的原则进行的抽样调查,被称为是一种“等概率”.随机抽样有四种基本形式,即简单随机抽样、等距抽样、类型抽样和整群抽样. 非随机抽样的定义&#xff1a;指抽样时不是遵循随机原则,而是按照研究…
阅读更多...
抽样技术--简单随机抽样

抽样技术--简单随机抽样

文章目录 简单随机抽样简单估计量及其性质对总体均值的估计简单随机抽样简单例子 对总体总量的估计例子 对总体比例的估计例子 比率估计量及其性质辅助变量比率估计量总体均值的期望咋算总体均值的方差咋算总体总值的期望咋算总体总值的方差咋算比率估计量的方差咋算Y与X的总体…
阅读更多...
R - 简单随机抽样

R - 简单随机抽样

本文使用的包 library(tidyverse) library(moderndive)使用的数据集&#xff0c;总共有2400个红球和白色球&#xff1a; bowl此处采用简单随机抽样&#xff0c;从2400个球中估算出红球所占比例。采用不同的抽取方法&#xff0c;一组是一次性抽取30个&#xff0c;重复1000次&a…
阅读更多...
随机抽样java_java实现从一个群体中随机抽样一定数量样本

随机抽样java_java实现从一个群体中随机抽样一定数量样本

说明 版权所有&#xff0c;仿冒必究 转载时请标明出处&#xff0c;尊重他人劳动成果&#xff0c;谢谢 此算法是我个人研究的&#xff0c;经过测试证明我的算法还是不错的。 PS&#xff1a;这里的时间可能有点偏小&#xff0c;实际用时是2秒左右&#xff0c;我没有去研究原因了。…
阅读更多...
ArcGIS 分类随机抽样

ArcGIS 分类随机抽样

前言 现有栅格分类图, 图中像素值代表分类编号, 取值范围为0~7。 要在每个类别中抽取100个点, 输出成带有类别的shape文件。 提取每类的随机点(流程图) 0 已有数据 一副栅格影像, 像素值代表该点的类别。 1 对类别进行循环 设置1~7的循环, 循环变量名为index。在之后的流…
阅读更多...
java随机抽样算法_随机抽样一致性（RANSAC）算法详解

java随机抽样算法_随机抽样一致性（RANSAC）算法详解

随机抽样一致性(RANSAC)算法能够有效的剔除特征匹配中的错误匹配点。 实际上&#xff0c;RANSAC能够有效拟合存在噪声模型下的拟合函数。实际上&#xff0c;RANSAC算法的核心在于将点划分为“内点”和“外点”。在一组包含“外点”的数据集中&#xff0c;采用不断迭代的方法&am…
阅读更多...
SPSS——随机抽样

SPSS——随机抽样

简单随机抽样 设定随机种子&#xff08;Transform→Random Number Generators&#xff09; 【方法一】 选择个案&#xff08;Data→Select Cases&#xff09; 将随机抽样的样本重新生成新的数据集&#xff0c;Approximately&#xff08;按百分比抽样&#xff09;&#xff0c;Ex…
阅读更多...
excel如何随机抽样

excel如何随机抽样

目录 现成数据中取数——excel-数据-数据分析-抽样【方法】【案例】【步骤】【注意】 二维数据需要拍平&#xff0c;才能取数——利用power query【方法】【案例】【步骤】 现成数据中取数——excel-数据-数据分析-抽样 【方法】 非数值型数据&#xff1a;1&#xff09;先生成…
阅读更多...
【抽样技术】CH2 简单随机抽样

【抽样技术】CH2 简单随机抽样

目录 前言 一、定义 二、概述 1.总体 2.单元 3.抽样比 4.样本抽取原则 5.在抽样理论中的地位与作用 三、参数估计 1.参数表示 2.对总体特征的估计思路 3.对总体均值的估计 &#xff08;1&#xff09;引理 &#xff08;2&#xff09;对总体均值的估计 4.方差和协方…
阅读更多...
推荐文章

Copyright @ 2022~2023