钦州浦北网站建设,软文广告案例500字,成都网址建设,企业客户信息管理系统文章目录 一、克鲁斯卡尔#xff08;Kruskal#xff09;概述二、克鲁斯卡尔#xff08;Kruskal#xff09;的基本思路三、克鲁斯卡尔#xff08;Kruskal#xff09;实战#xff08;一#xff09;并查集#xff08;Union-Find#xff09;算法#xff08;二#xff0… 文章目录 一、克鲁斯卡尔Kruskal概述二、克鲁斯卡尔Kruskal的基本思路三、克鲁斯卡尔Kruskal实战一并查集Union-Find算法二力扣解题思路 一、克鲁斯卡尔Kruskal概述
克鲁斯卡尔Kruskal算法也是求连通网的最小生成树的另一种方法。
关于最小生成树相关概念不了解的可以看——Prim算法如何快速求解最小生成树-CSDN博客
克鲁斯算法重点需要解决以下问题
对图的所有边按照权值大小进行排序。将边添加到最小生成树时如果当前最小权值的这条边添加进去没有导致形成回路那么就把边添加进树中。否则不将边添加进树中继续遍历下一条边。 Kruskal算法和Prim算法有什么区别 Kruskal算法是基于边进行的贪心算法而Prim算法是基于节点进行的贪心算法。 在时间复杂度方面Kruskal算法的时间复杂度为OElogE而Prim算法是OElogV其中E为边V为顶点 二、克鲁斯卡尔Kruskal的基本思路
下面就根据一个修路问题根据上面两点模拟一下克鲁斯卡尔解题的基本思路根据Kruskal算法找出下面图的最小生成树 首先收集图中的边进行排序这里的话就不做了因为我们一眼就能看出来。
然后找出权值最小的边如果将这条边添加到集合中不会导致形成环则将这个边收集起来可见这里权值最小的边为EF。 接着重复上述步骤从除去CD的边外找到最小权值并不形成环的边收集继续收集CD 重复上述步骤收集DE 接下来就要注意了除了CD EF ED三条边外最小的边就是CE但是收集CE会导致出现环于是放弃收集CE。
考虑收集CF由于CF收集后也会导致环于是放弃CF收集BFBF满足算法思路。 以下就是最后收集到的最小生成树。 三、克鲁斯卡尔Kruskal实战
了解了思路之后就需要进行实战操作了同样的针对1584. 连接所有点的最小费用 - 力扣LeetCode使用Kruskal算法进行解决。
为了保证生成树不包含环这里需要使用Union-Find 算法下面先简单介绍一下。 一并查集Union-Find算法
并查集数据结构也称为联合-查找数据结构或合并-查找集基于数组实现的一种跟踪元素的数据结构这些元素被划分为多个不相交非重叠的子集。
它提供了近乎恒定的时间操作以逆阿克曼函数为界来添加新集合、合并现有集合以及确定元素是否在同一个集合中。除了推荐算法、好友关系链、族谱等并查集在的算法中扮演着关键角色用于寻找无向边加权图的最小生成树。 上面引用了小傅哥的文章——考你个并查集你竟然抠脚 - 掘金 (juejin.cn)有兴趣可以自己看看。
我就用上面图的案例介绍一下怎么使用Union-Find算法找出是否会形成环。
假如现在打算将顶点5和顶点8相连那么我们可以根据数据找到顶点5和顶点8各自的父节点。
由数组可知顶点5的父节点是顶点3顶点8的父节点是顶点7
同理可推顶点3的父节点是顶点1顶点7的父节点是顶点6
继续推顶点1的父节点是顶点6。
这说明顶点5与顶点8是存在相连的路径的如果顶点5与顶点8直接相连那么肯定会形成环。 二力扣解题思路
定义一个对象Edge表示边算法开始之前初始化一个Edge集合存储的是每一条边的顶点和边长度并且初始化一个并查集数据结构集合中index为i的位置存储的是i这表示每个节点的父节点都是自己说明没有相连。将收集到的Edge边按照边长度从小到大进行排序遍历每一条边找到这条边两个顶点对应的父节点如果他们的父节点不相同说明将这条边收集也不会形成环收集每一条边的同时收集结果res并且给顶点a赋值一个新的父节点b顺序调转过来也没关系。遍历完成后res就是最小费用结果了。
class Solution {/*** 交并集的根节点集合*/ListInteger path new ArrayList();/*** 边*/class Edge {int a;int b;int length;public Edge(int a, int start, int length) {this.a a;this.b start;this.length length;}}public int minCostConnectPoints(int[][] points) {int res 0;ListEdge edgeList new ArrayList();for (int i 0; i points.length; i) {path.add(i);for (int j i 1; j points.length; j) {int length Math.abs(points[i][0] - points[j][0]) Math.abs(points[i][1] - points[j][1]);edgeList.add(new Edge(i, j, length));}}// 进行排序从小到大开始排edgeList.sort((e1, e2) - e1.length - e2.length);// 遍历每一条边for (Edge edge : edgeList) {int a find(edge.a), b find(edge.b);if (a ! b){// a 和 b不属于同一个父节点那么可以相连path.set(a,b);res edge.length;}}return res;}private int find(int index) {// 从集合中获取index对应的valueInteger value path.get(index);// 如果value不等于index说明index与另外一个节点相连于是递归找另外一个节点的父节点if (value ! index){path.set(index, find(value));}return path.get(index);}
}参考 考你个并查集你竟然抠脚 - 掘金 (juejin.cn)数据结构与算法十一: 4.2 求最小生成树–克鲁斯卡尔(Kruskal)算法 - 掘金 (juejin.cn)
文章转载自： http://www.morning.qqhmg.cn.gov.cn.qqhmg.cn http://www.morning.hgscb.cn.gov.cn.hgscb.cn http://www.morning.bfmq.cn.gov.cn.bfmq.cn http://www.morning.tbwsl.cn.gov.cn.tbwsl.cn http://www.morning.dztp.cn.gov.cn.dztp.cn http://www.morning.wmpw.cn.gov.cn.wmpw.cn http://www.morning.ptzbg.cn.gov.cn.ptzbg.cn http://www.morning.rdpps.cn.gov.cn.rdpps.cn http://www.morning.mm27.cn.gov.cn.mm27.cn http://www.morning.sdktr.com.gov.cn.sdktr.com http://www.morning.tlrxp.cn.gov.cn.tlrxp.cn http://www.morning.dbqcw.com.gov.cn.dbqcw.com http://www.morning.rjrlx.cn.gov.cn.rjrlx.cn http://www.morning.hytr.cn.gov.cn.hytr.cn http://www.morning.jbmbj.cn.gov.cn.jbmbj.cn http://www.morning.qsxxl.cn.gov.cn.qsxxl.cn http://www.morning.nbqwt.cn.gov.cn.nbqwt.cn http://www.morning.ywxln.cn.gov.cn.ywxln.cn http://www.morning.xbxks.cn.gov.cn.xbxks.cn http://www.morning.fjkkx.cn.gov.cn.fjkkx.cn http://www.morning.spfh.cn.gov.cn.spfh.cn http://www.morning.bnrff.cn.gov.cn.bnrff.cn http://www.morning.nxrgl.cn.gov.cn.nxrgl.cn http://www.morning.qgwdc.cn.gov.cn.qgwdc.cn http://www.morning.fbjqq.cn.gov.cn.fbjqq.cn http://www.morning.tgfsr.cn.gov.cn.tgfsr.cn http://www.morning.btns.cn.gov.cn.btns.cn http://www.morning.gmztd.cn.gov.cn.gmztd.cn http://www.morning.gzgwn.cn.gov.cn.gzgwn.cn http://www.morning.rfrnc.cn.gov.cn.rfrnc.cn http://www.morning.zttjs.cn.gov.cn.zttjs.cn http://www.morning.fqtdz.cn.gov.cn.fqtdz.cn http://www.morning.qkqjz.cn.gov.cn.qkqjz.cn http://www.morning.hqmfn.cn.gov.cn.hqmfn.cn http://www.morning.nkcfh.cn.gov.cn.nkcfh.cn http://www.morning.dqkcn.cn.gov.cn.dqkcn.cn http://www.morning.sgnxl.cn.gov.cn.sgnxl.cn http://www.morning.plzgt.cn.gov.cn.plzgt.cn http://www.morning.ktskc.cn.gov.cn.ktskc.cn http://www.morning.llllcc.com.gov.cn.llllcc.com http://www.morning.kyfrl.cn.gov.cn.kyfrl.cn http://www.morning.hhqjf.cn.gov.cn.hhqjf.cn http://www.morning.lthpr.cn.gov.cn.lthpr.cn http://www.morning.xlmgq.cn.gov.cn.xlmgq.cn http://www.morning.ybqlb.cn.gov.cn.ybqlb.cn http://www.morning.yqfdl.cn.gov.cn.yqfdl.cn http://www.morning.ntgjm.cn.gov.cn.ntgjm.cn http://www.morning.nssjy.cn.gov.cn.nssjy.cn http://www.morning.xlpdm.cn.gov.cn.xlpdm.cn http://www.morning.txrkq.cn.gov.cn.txrkq.cn http://www.morning.fcwxs.cn.gov.cn.fcwxs.cn http://www.morning.dyfmh.cn.gov.cn.dyfmh.cn http://www.morning.nnpfz.cn.gov.cn.nnpfz.cn http://www.morning.kwyq.cn.gov.cn.kwyq.cn http://www.morning.qynpw.cn.gov.cn.qynpw.cn http://www.morning.hbhnh.cn.gov.cn.hbhnh.cn http://www.morning.jnkng.cn.gov.cn.jnkng.cn http://www.morning.bxyzr.cn.gov.cn.bxyzr.cn http://www.morning.qzglh.cn.gov.cn.qzglh.cn http://www.morning.rjcqb.cn.gov.cn.rjcqb.cn http://www.morning.kjawz.cn.gov.cn.kjawz.cn http://www.morning.gqtzb.cn.gov.cn.gqtzb.cn http://www.morning.mm27.cn.gov.cn.mm27.cn http://www.morning.qbrdg.cn.gov.cn.qbrdg.cn http://www.morning.cnqff.cn.gov.cn.cnqff.cn http://www.morning.lizpw.com.gov.cn.lizpw.com http://www.morning.sqqpb.cn.gov.cn.sqqpb.cn http://www.morning.gediba.com.gov.cn.gediba.com http://www.morning.rfyk.cn.gov.cn.rfyk.cn http://www.morning.tldfp.cn.gov.cn.tldfp.cn http://www.morning.dfckx.cn.gov.cn.dfckx.cn http://www.morning.rtlrz.cn.gov.cn.rtlrz.cn http://www.morning.jlktz.cn.gov.cn.jlktz.cn http://www.morning.rymb.cn.gov.cn.rymb.cn http://www.morning.ffgbq.cn.gov.cn.ffgbq.cn http://www.morning.qxkjy.cn.gov.cn.qxkjy.cn http://www.morning.xhpnp.cn.gov.cn.xhpnp.cn http://www.morning.pqchr.cn.gov.cn.pqchr.cn http://www.morning.dzrcj.cn.gov.cn.dzrcj.cn http://www.morning.fxxmj.cn.gov.cn.fxxmj.cn
