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

前言

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

一、引言

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

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

如同下图所示:

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

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

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

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

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

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

二、Prim 算法是什么

普里姆算法(Prim算法),图论中的一种算法,通过 点去找边 的行为,可在加权连通图里搜索最小生成树。

该算法于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;
    }
复制代码

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

五、总结

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

同时,对于 Prim 的代码也需要多写几遍,多想想 Kruskal 和 Prim 的区别

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

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

回答一下 break 的问题:防止森林现象的存在

本期的内容就到这里,下期会讲述最短路径 Dijkstra

上一篇:Git 分支管理


下一篇:Maya绘制摆动的链子的实例教程