一文带你学会最小生成树，不要等到面试再临时抱佛脚了

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

在这里插入图片描述

一、引言

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

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

如同下图所示：
在这里插入图片描述

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

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

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

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

PS：Kruskal 算法链接：最小生成树——Kruskal 算法

二、Prim 算法是什么

普里姆算法（Prim算法），图论中的一种算法，通过 <stron> 的行为，可在加权连通图里搜索最小生成树。</stron>

该算法于1930年由捷克数学家 沃伊捷赫·亚尔尼克 发现；并在1957年由美国计算机科学家 罗伯特·普里姆 独立发现

我们以下面的小区为例，通过 Prim 算***给我们一条连接所有小区的最短路径

在这里插入图片描述

三、Prim 算法本质

对于 Prim 算法来说，整体使用了贪心的思想

在这里插入图片描述

简单的来说，我们需要从上述图中随机挑选一个点，找到最小的边，然后释放其连接的点，再去找到最小的边，周而复始......

PS：每个边只入队一次

我们随机选中 A小区 这个节点，将其所有的边 2、3、6 释放出来，我们的边集合为 2、3、6，找到最小的边 2 用掉，释放 E小区
我们选中 E小区 这个节点，将其所有的边 7、12 释放出来，我们的边集合为 3、6、7、12，找到最小的边 3 用掉，释放 B小区
我们选中 B小区 这个节点，将其所有的边 10 释放出来，我们的边集合为 6、7、10、12，找到最小的边 6 用掉，释放 D小区
我们选中 D小区 这个节点，将其所有的边 1 释放出来，我们的边集合为 1、7、10、12，找到最小的边 1 用掉，释放 C小区

这样，我们所有的点已经找出来了

可以看到我们的最小生成树为：12

我们对比一下上期讲到的 Kruskal 算法：Kruskal 算法
在这里插入图片描述
我们可以看到，得到的路径都是一样的，证明 Kruskal 和 Prim 算法求出的最小生成树相同

四、Prim 算法实现

对于 Prim 算法，主要利用贪心的思想，由点去寻找边，解锁点的循环.....

4.1 比较器的实现（按照边的权重排序）

public static class MyEdgeComparator implements Comparator<Edge> {

        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight - o2.weight;
        }
    }

4.2 Prim 算法

    public Set<Edge> prim(Graph graph) {
        // 解锁的边
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new MyEdgeComparator());

        // 该点是否走过
        Set<Node> setNodeVis = new HashSet<>();


        // 挑选的边
        Set<Edge> setEdge = new HashSet<>();

        for (Node node : graph.nodes.values()) {
            // 该点没有被走过
            if (!setNodeVis.contains(node)) {
                // 将该点标记为已经被走过
                setNodeVis.add(node);
                // 加入该点解锁的边
                for (Edge edge : node.edges) {
                    priorityQueue.add(edge);
                }

                // 由边找点
                while (!priorityQueue.isEmpty()) {
                    Edge edge = priorityQueue.poll();
                    Node to = edge.to;
                    // 看当前点是否被访问过
                    if (!setNodeVis.contains(to)) {
                        // 最终的结果
                        setEdge.add(edge);
                        // 没有访问的话，加入访问标记，并且将其所有的边给放进去
                        setNodeVis.add(to);
                        for (Edge edge1 : to.edges) {
                            priorityQueue.add(edge1);
                        }
                    }
                }
            }
            // 大家可以思考一下这里的 break 存在的意义是什么
            break;
        }
        return setEdge;
    }

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