最小生成树(Prim、Kruskal)算法，秒懂！

article/2025/9/16 13:35:21

前言

在数据结构与算法的图论中，(生成)最小生成树算法是一种常用并且和生活贴切比较近的一种算法。但是可能很多人对概念不是很清楚，什么是最小生成树?

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。

通俗易懂的讲就是最小生成树包含原图的所有节点而只用最少的边和最小的权值距离。因为n个节点最少需要n-1个边联通，而距离就需要采取某种策略选择恰当的边。

学习最小生成树实现算法之前我们要先高清最小生成树的结构和意义所在。咱么首先根据一些图更好的祝你理解。

一个故事

在城市道路规划中，是一门很需要科学的研究(只是假设学习不必当真)。在公路时代城市联通的主要矛盾是时间慢，而造价相比运输时间是次要矛盾。所以在公路时代我们尽量使得城市能够直接联通，缩短城市联系时间，而稍微考虑建路成本！随着科技发展、高级铁路、信息传输相比公路运输快非常非常多，从而事件的主要矛盾从运输时间转变为造价成本，故有时会关注联通所有点的路程(最短)，这就用到最小生成树算法。

城市道路铺设可能经历以下几个阶段。

  • 初始，各个城市没有高速公路(铁路)。
  • 政府打算各个城市铺设公路(铁路)，每个城市都想成为交通枢纽，快速到达其他城市，但每个城市都有这种想法，如果实现下去造价太昂贵。并且造成巨大浪费。
  • 最终国家选择一些主要城市进行联通，有个别城市只能稍微绕道而行，而绕道太远的、人流量多的国家考虑新建公路(铁路)，适当提高效率。

在这里插入图片描述

不过上面铁路规划上由于庞大的人口可能不能够满足与"有铁路"这个需求，人们对速度、距离、直达等条件一直在追求中……

但是你可以想象这个场景：有些东西造假非常非常昂贵，使用效率非常高，我这里假设成黄金镶钻电缆 铺设，所以各个城市只要求不给自己落下，能通上就行(没人敢跳了吧)。

要从有环图中选取代价和最小的路线一方面代价最小(总距离最小最省黄金)另一方面联通所有城市。

然而根据上图我们可以得到以下最小生成树,但是最么生成这个最小生成树，就是下面要讲的了。

请添加图片描述

而类似的还有局部区域岛屿联通修桥，海底通道这些高成本的都多多少少会运用。

Kruskal算法

上面介绍了最小生成树是什么，现在需要掌握和理解最小生成树如何形成。给你一个图，用一个规则生成一个最小生成树。而在实现最小生成树方面有prim和kruskal算法，这两种算法的策略有所区别，但是时间复杂度一致。

Kruskal算法，和前面讲到的并查集关系很大，它的主要思想为：

先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。

简而言之，Kruskal算法进行调度的单位是边,它的信仰为:所有边能小则小，算法的实现方面要用到并查集判断两点是否在同一集合。

而算法的具体步骤为：

  1. 将图中所有边对象(边长、两端点)依次加入集合(优先队列)q1中。初始所有点相互独立。
  2. 取出集合(优先队列)q1最小边，判断边的两点是否联通。
  3. 如果联通说明两个点已经有其它边将两点联通了，跳过，如果不连通，则使用union（并查集合并）将两个顶点合并，这条边被使用(可以储存或者计算数值)。
  4. 重复2，3操作直到集合（优先队列）q1为空。此时被选择的边构成最小生成树。

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

Prim算法

除了Kruskal算法以外，普里姆算法（Prim算法）也是常用的最小生成树算法。虽然在效率上差不多。但是贪心的方式和Kruskal完全不同。

prim算法的核心信仰是：从已知扩散寻找最小。它的实现方式和Dijkstra算法相似但稍微有所区别，Dijkstra是求单源最短路径，而每计算一个点需要对这个点重新更新距离，而prim不用更新距离。直接找已知点的邻边最小加入即可！prim和kruskal算法都是从边入手处理。

对于具体算法具体步骤，大致为：

  1. 寻找图中任意点，以它为起点，它的所有边V加入集合(优先队列)q1,设置一个boolean数组bool[]标记该位置(边有两个点，每次加入没有被标记那个点的所有边)。
  2. 从集合q1找到距离最小的那个边v1并 判断边是否存在未被标记的一点p ，如果p不存在说明已经确定过那么跳过当前边处理，如果未被标(访问)记那么标记该点p,并且与p相连的未知点(未被标记)构成的边加入集合q1， 边v1(可以进行计算距离之类，该边构成最小生成树) .
  3. 重复1，2直到q1为空，构成最小生成树 ！

大体步骤图解为：
在这里插入图片描述

在这里插入图片描述

因为prim从开始到结束一直是一个整体在扩散，所以不需要考虑两棵树合并的问题，在这一点实现上稍微方便了一点。

当然，要注意的是最小生成树并不唯一，甚至同一种算法生成的最小生成树都可能有所不同，但是相同的是无论生成怎样的最小生成树：

  • 能够保证所有节点连通(能够满足要求和条件)
  • 能够保证所有路径之和最小(结果和目的相同)
  • 最小生成树不唯一，可能多样的

在这里插入图片描述

代码实现

上面分析了逻辑实现。下面我们用代码简单实现上述的算法。

prim

package 图论;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;public class prim {public static void main(String[] args) {int minlength=0;//最小生成树的最短路径长度int max=66666;String cityname[]= {"北京","武汉","南京","上海","杭州","广州","深圳"};int city[][]= {{ max, 8, 7, max, max, max, max }, //北京和武汉南京联通{ 8, max,6, max,9, 8,max }, //武汉——北京、南京、杭州、广州{ 7, 6, max, 3,4, max,max }, //南京——北京、武汉、上海、杭州{ max, max,3, max,2, max,max }, //上海——南京、杭州{ max, 9,4, 2,max, max,10 }, //杭州——武汉、南京、上海、深圳{ max, 8,max, max,max, max,2 }, //广州——武汉、深圳{ max, max,max, max,10,2,max }//深圳——杭州、广州};// 地图boolean istrue[]=new boolean[7];//南京Queue<side>q1=new PriorityQueue<side>(new Comparator<side>() {public int compare(side o1, side o2) {// TODO Auto-generated method stubreturn o1.lenth-o2.lenth;}});for(int i=0;i<7;i++){if(city[2][i]!=max){istrue[2]=true;q1.add(new side(city[2][i], 2, i));}}		while(!q1.isEmpty()){side newside=q1.poll();//抛出if(istrue[newside.point1]&&istrue[newside.point2]){continue;}else {if(!istrue[newside.point1]){istrue[newside.point1]=true;minlength+=city[newside.point1][newside.point2];System.out.println(cityname[newside.point1]+" "+cityname[newside.point2]+" 联通");for(int i=0;i<7;i++){if(!istrue[i]){q1.add(new side(city[newside.point1][i],newside.point1,i));}}}else {istrue[newside.point2]=true;minlength+=city[newside.point1][newside.point2];System.out.println(cityname[newside.point2]+" "+cityname[newside.point1]+" 联通");for(int i=0;i<7;i++){if(!istrue[i]){q1.add(new side(city[newside.point2][i],newside.point2,i));}}}}}System.out.println(minlength);		}static class side//边{int lenth;int point1;int point2;public side(int lenth,int p1,int p2) {this.lenth=lenth;this.point1=p1;this.point2=p2;}}}

输出结果：

上海 南京 联通
杭州 上海 联通
武汉 南京 联通
北京 南京 联通
广州 武汉 联通
深圳 广州 联通
28

Kruskal:
package 图论;import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;import 图论.prim.side;
/** 作者：bigsai(公众号)*/
public class kruskal {static int tree[]=new int[10];//bing查集public static void init() {for(int i=0;i<10;i++)//初始{tree[i]=-1;}}public static int search(int a)//返回头节点的数值{if(tree[a]>0)//说明是子节点{return tree[a]=search(tree[a]);//路径压缩}elsereturn a;}public static void union(int a,int b)//表示 a，b所在的树合并小树合并大树(不重要){int a1=search(a);//a根int b1=search(b);//b根if(a1==b1) {//System.out.println(a+"和"+b+"已经在一棵树上");}else {if(tree[a1]<tree[b1])//这个是负数，为了简单减少计算，不在调用value函数{tree[a1]+=tree[b1];//个数相加  注意是负数相加tree[b1]=a1;       //b树成为a的子树，直接指向a；}else{tree[b1]+=tree[a1];//个数相加  注意是负数相加tree[a1]=b1;       //b树成为a的子树，直接指向a；}}}public static void main(String[] args) {// TODO Auto-generated method stubinit();int minlength=0;//最小生成树的最短路径长度int max=66666;String cityname[]= {"北京","武汉","南京","上海","杭州","广州","深圳"};boolean jud[][]=new boolean[7][7];//加入边需要防止重复 比如 ba和ab等价的int city[][]= {{ max, 8, 7, max, max, max, max }, { 8, max,6, max,9, 8,max }, { 7, 6, max, 3,4, max,max }, { max, max,3, max,2, max,max }, { max, 9,4, 2,max, max,10 }, { max, 8,max, max,max, max,2 }, { max, max,max, max,10,2,max }};// 地图boolean istrue[]=new boolean[7];//南京Queue<side>q1=new PriorityQueue<side>(new Comparator<side>() {//优先队列存边+public int compare(side o1, side o2) {// TODO Auto-generated method stubreturn o1.lenth-o2.lenth;}});for(int i=0;i<7;i++){for(int j=0;j<7;j++){if(!jud[i][j]&&city[i][j]!=max)//是否加入队列{jud[i][j]=true;jud[j][i]=true;q1.add(new side(city[i][j], i, j));}}}while(!q1.isEmpty())//执行算法{side newside=q1.poll();int p1=newside.point1;int p2=newside.point2;if(search(p1)!=search(p2)){union(p1, p2);System.out.println(cityname[p1]+" "+cityname[p2]+" 联通");minlength+=newside.lenth;}}System.out.println(minlength);}static class side//边{int lenth;int point1;int point2;public side(int lenth,int p1,int p2) {this.lenth=lenth;this.point1=p1;this.point2=p2;}}
}

输出结果

上海 杭州 联通
广州 深圳 联通
南京 上海 联通
武汉 南京 联通
北京 南京 联通
武汉 广州 联通
28

总结

最小生成树算法理解起来也相对简单，实现起来也不是很难。Kruskal和Prim主要是贪心算法的两种角度。一个从整体开始找最小边，遇到关联不断合并，另一个从局部开始扩散找身边的最小不断扩散直到生成最小生成树。在学习最小生成树之前最好学习一下dijkstra算法和并查集，这样在实现起来能够快一点，清晰一点。

力扣1584就是一个最小生成树的入门题，不过哪个有点区别的就是默认所有点是联通的，所以需要你剪枝优化。这里就不带大家一起看啦，有问题下面也可交流！

最后，如果你那天真的获得一大笔资金去修建这么一条昂贵的黄金路线，可以适当采取此方法，另外剩下的大批，苟富贵，勿相忘。。

另外，我将自己csdn写的原创整理成258页数据结构与算法pdf，大家可以关注下面👇👇回复【666】免费获取！


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

相关文章

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

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

作为一个伪ACMer,先来首广为人知的打油诗: 模拟只会猜题意&#xff0c;贪心只能过样例&#xff0c;数学上来先打表&#xff0c;规律一般是DP&#xff0c;组合数学碰运气&#xff0c;计算几何瞎暴力&#xff0c;图论一顿套模板&#xff0c;数论只会GCD,递归递推伤不起&#xff0…
阅读更多...
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;先生成…
阅读更多...
推荐文章

Copyright @ 2022~2023