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

电玩女神 2023-10-02 16:51 16阅读 0赞

> 你好，我是小黄，一名独角兽企业的Java开发工程师。  
> 感谢茫茫人海中我们能够相遇，  
> 俗话说：当你的才华和能力，不足以支撑你的梦想的时候，请静下心来学习，  
> 希望优秀的你可以和我一起学习，一起努力，实现属于自己的梦想。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

#### 文章目录 ####

*  一、引言
 *  二、Kruskal 算法是什么
 *  三、Kruskal 算法本质
 *  四、Kruskal 算法实现
 *   *  1、并查集
     *  2、Kruskal 算法
 *  五、总结

## 一、引言 ##

鸽了一周的我又回来了…

小黄去过生日了~

带你们看下生日蛋糕

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_20_color_FFFFFF_t_70_g_se_x_16]

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

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

如同下图所示：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_10_color_FFFFFF_t_70_g_se_x_16]  
当然，上述只是一个抽象化的例子，而我们实际生活中，每个小区间的距离也是不一样的，我们怎么使用最小的资金去连接所有的小区呢？

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

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

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

当然，有人可能有疑惑，为什么不一次性把 **Prim** 算法也讲了，结尾我会告诉答案的

## 二、Kruskal 算法是什么 ##

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

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

我们以下面的小区为例，通过 **Kruskal** 算法会给我们一条连接所有小区的最短路径  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_8_color_FFFFFF_t_70_g_se_x_16]

## 三、Kruskal 算法本质 ##

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

有不熟悉并查集的童鞋可以看一下这篇：[三分钟带你学会并查集【含状态压缩】][Link 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_8_color_FFFFFF_t_70_g_se_x_16 1]

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

*  我们把第一个边 `1` 取出，将 `C小区` 和 `D小区` 合并，目前集合：`{C、D}`  
    ![在这里插入图片描述][9e0168a1e93d47b79b3b383e247182e6.png]
 *  我们把第二个边 `2` 取出，将 `A小区` 和 `E小区` 合并，目前集合：`{C、D}`，`{A、E}`  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_8_color_FFFFFF_t_70_g_se_x_16 2]
 *  我们把第三个边 `3` 取出，将 `A小区` 和 `B小区` 合并，目前集合：`{C、D}`，`{A、B、E}`  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_8_color_FFFFFF_t_70_g_se_x_16 3]
 *  将第四个边 `6` 取出，将 `A小区` 和 `D小区` 合并，目前集合：`{A、B、E、C、D}`  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_8_color_FFFFFF_t_70_g_se_x_16 4]
 *  将第五个边 `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;
        }

以上图的描述均使用图的形象化描述：[图的形象化描述][Link 2]

## 五、总结 ##

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

同时，对于 `Kruskal` 的代码也需要多写几遍，博主写这篇博客的时候，又忘记了怎么写（逃

*  [1584. 连接所有点的最小费用【模板题目】][1584.]

![在这里插入图片描述][b3d9a4b9779349ff8b4feb1c80ceb8fc.png]

对源代码有兴趣的小伙伴，可以关注 **爱敲代码的小黄** 公众号，回复：**算法源码** 即可获得算法源码

回答一下一开始的问题：**有人可能有疑惑，为什么不一次性把 Prim 算法也讲了**

答：**下期讲 Prim，可以水一期（逃**

本期的内容就到这里，下期会讲述最小生成树 **Prim** 算法

我是一名独角兽企业的Java开发工程师，希望可以点个关注呀，有问题可以留言或者私信加我微信：hls1793929520，我们下期再见！

![在这里插入图片描述][f56dab9358d59e78cdf7352e966dc172.png]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: https://img-blog.csdnimg.cn/c618d4225cf04e86aa1d8c2c6c680192.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/312103b938c74c34a19777de252e7e45.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_10_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/dae2d1a017fb447dae21e92225322073.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_10,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_8_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/4f1a30ecb2064bd5983874ed3c7c21a4.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_8,color_FFFFFF,t_70,g_se,x_16
[Link 1]: https://blog.csdn.net/qq_40915439/article/details/120401368
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_8_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/0961dd13a8ab467ab99ba95583b09ca7.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_8,color_FFFFFF,t_70,g_se,x_16
[9e0168a1e93d47b79b3b383e247182e6.png]: https://img-blog.csdnimg.cn/9e0168a1e93d47b79b3b383e247182e6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_8_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/88b04d6b519241e791b95785b90b28f7.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_8,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_8_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/df79e91780304b9b978aef9e7b061df6.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_8,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_8_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/0daa947f65594769847bb88e5e1242a6.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_8,color_FFFFFF,t_70,g_se,x_16
[Link 2]: https://blog.csdn.net/qq_40915439/article/details/120713128
[1584.]: https://leetcode-cn.com/problems/min-cost-to-connect-all-points/submissions/
[b3d9a4b9779349ff8b4feb1c80ceb8fc.png]: https://img-blog.csdnimg.cn/b3d9a4b9779349ff8b4feb1c80ceb8fc.png
[f56dab9358d59e78cdf7352e966dc172.png]: https://img-blog.csdnimg.cn/img_convert/f56dab9358d59e78cdf7352e966dc172.png