字节面试官让我讲讲最小生成树,我真的忍不住笑了

字节面试官让我讲讲最小生成树,我真的忍不住笑了大家有没有在生活中遇到这种事情你们县城需要在几个小区之间进行修路 由于政府资金紧张 不可能所有的小区之间都进行修路 而是利用最少的资金修一条可以连接所有小区的路如同下图所示 当然 上述只是一个抽象化的例子 而我们实际生活中 每个小区间的距

大家好,欢迎来到IT知识分享网。

大家有没有在生活中遇到这种事情

你们县城需要在几个小区之间进行修路,由于政府资金紧张,不可能所有的小区之间都进行修路,而是利用最少的资金修一条可以连接所有小区的路

如同下图所示:

字节面试官让我讲讲最小生成树,我真的忍不住笑了

当然,上述只是一个抽象化的例子,而我们实际生活中,每个小区间的距离也是不一样的,我们怎么使用最小的资金去连接所有的小区呢?

这就牵扯到我们今天的老大哥们:Kruskal 算法和 Prim 算法

这两种算法分别从边和点产生最小生成树,保证了资金的最小性

本篇文章,我们一起走近 Kruskal 算法,探究一下该算法是怎么通过边来确定最小生成树

二、Kruskal 算法是什么

克鲁斯卡尔Kruskal)算法是求连通网的最小生成树的一种方法。与普里姆Prim)算法不同,它的时间复杂度为 O(eloge)(e为网中的边数),所以,适合于求边稀疏的最小生成树 。

因为我们的 Kruskal 算法是以边为单位,所以求一些边稀疏的最小生成树,时间复杂度比较小

我们以下面的小区为例,通过 Kruskal 算法会给我们一条连接所有小区的最短路径

字节面试官让我讲讲最小生成树,我真的忍不住笑了

三、Kruskal 算法本质

对于 Kruskal 算法来说,整体使用了 贪心 + 并查集 的思路

有不熟悉并查集的童鞋可以看一下这篇:三分钟带你学会并查集【含状态压缩】

字节面试官让我讲讲最小生成树,我真的忍不住笑了

简单来说,我们需要将所有的边放入一个堆中,按照边的大小进行排序,如下所示:1、2、3、6、7、10、12

  • 我们把第一个边 1 取出,将 C小区 和 D小区 合并,目前集合:{C、D}
字节面试官让我讲讲最小生成树,我真的忍不住笑了

  • 我们把第二个边 2 取出,将 A小区 和 E小区 合并,目前集合:{C、D},{A、E}
字节面试官让我讲讲最小生成树,我真的忍不住笑了

  • 我们把第三个边 3 取出,将 A小区 和 B小区 合并,目前集合:{C、D},{A、B、E}
字节面试官让我讲讲最小生成树,我真的忍不住笑了

  • 将第四个边 6 取出,将 A小区 和 D小区 合并,目前集合:{A、B、E、C、D}
字节面试官让我讲讲最小生成树,我真的忍不住笑了

  • 将第五个边 7 取出,将 B小区 和 E小区 合并,由于 {A、B、E、C、D} 在一个集合,不进行合并,跳过该边
  • 将第六个边 10 取出,将 B小区 和 C小区 合并,由于 {A、B、E、C、D} 在一个集合,不进行合并,跳过该边
  • 依次类推…….

最终我们会得到一个路径,这也就是我们的最小生成树

由图得知,我们最小的资金需要:12

四、Kruskal 算法实现

对于 Kruskal 算法,我们需要实现两部分

  • 并查集
  • 贪心

1、并查集

这里简单的放下并查集的两个关键步骤

合并

 // 合并 public void union(Node node1, Node node2) { // 找到两个节点的父节点 Node node1Parent = getParentNode(node1); Node node2Parent = getParentNode(node2); // 看看是不是一个父亲 if (node1Parent != node2Parent) { // node1、node2父亲的节点数量 int size1 = size.get(node1Parent); int size2 = size.get(node2Parent); // 谁的节点多,少的就挂在多的下面,进行合并 if (size1 >= size2) { parent.put(node1Parent, node2Parent); size.put(node1Parent, size1 + size2); size.remove(node2Parent); } else { parent.put(node2Parent, node1Parent); size.put(node2Parent, size1 + size2); size.remove(node2Parent); } } }

查询

 public boolean isSame(Node node1, Node node2) { return getParentNode(node1) == getParentNode(node2); } public Node getParentNode(Node node) { // 为了路径压缩 Stack<Node> stack = new Stack<>(); while (parent.get(node) != node) { stack.add(node); node = parent.get(node); } while (!stack.isEmpty()) { parent.put(stack.pop(), node); } return node; }

2、Kruskal 算法

并查集的初始化

 // 赋予初始值 public void makeSets(Collection<Node> list) { for (Node node : list) { // 初始时,每个节点的父节点均是自己,集合的数量为1 parent.put(node, node); size.put(node, 1); } }

比较器(按照边的权重排序)

 public static class EdgeComparator implements Comparator<Edge> { @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } }

Kruskal 算法

 public static Set<Edge> kruskalMST(Graph graph) { Union union = new Union(); // 初始化并查集 union.makeSets(graph.nodes.values()); // 建堆,按照边的权重进行排序 PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator()); // 放入边 for (Edge edge : graph.edges) { priorityQueue.add(edge); } Set<Edge> edges = new HashSet<>(); // 从最小的开始 while (!priorityQueue.isEmpty()) { Edge edge = priorityQueue.poll(); // 看一下是否是一个集合的 if (!union.isSame(edge.from, edge.to)) { // 可以选取这条边,合并这两个点 edges.add(edge); union.union(edge.from, edge.to); } } return edges; }

以上图的描述均使用图的形象化描述:图的形象化描述

五、总结

通过以上的描述,我们可以解决我们开头说的那个问题:你们县城需要在几个小区之间进行修路,由于政府资金紧张,不可能所有的小区之间都进行修路,而是利用最少的资金修一条可以连接所有小区的路

同时,对于 Kruskal 的代码也需要多写几遍

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/93178.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信