图的最小生成树：Prim算法--解锁一批边，解锁一批节点

图的最小生成树：Prim算法–解锁一批边，解锁一批节点

提示：系列图的文章
提示：大厂笔试面试都可能不咋考的数据结构：图

由于图的结构比较难，出题的时候，很难把这个图的数据搞通顺，而且搞通顺了题目也需要耗费太多时间，故笔试面试都不会咋考
笔试大厂考的就是你的贪心取巧策略和编码能力，这完全不必用图来考你，其他的有大量的选择
面试大厂考你的是优化算法的能力，但是图没啥可以优化的，只要数据结构统一，它的算法是固定死的，所以不会在面试中考！
万一考，那可能都是大厂和图相关的业务太多，比如美团高德地图啥的，这种考的少。

但不管考不考，我们要有基础，要了解图的数据结构和算法。万一考了呢，准备以备不时之需。

图的数据结构比较难，算法是固定的套路
咱们需要统一一种自己熟悉的图的数据结构，方便套用算法时好写！！

下面是咱们得关于图的重要基础知识和重点应用：
（1）图数据结构，图的统一数据结构和非标准图的转化算法
（2）图的宽度优先遍历：BFS遍历
（3）图的深度优先遍历：DFS遍历

有了这些基础知识，咱就可以破解图的题目了
（4）图的拓扑排序：图的BFS的应用题
（5）图的最小生成树：Kruskal算法–并查集的经典应用，解决连通性问题

---

文章目录

• 图的最小生成树：Prim算法--解锁一批边，解锁一批节点
• • @[TOC](文章目录)
• 生成树的定义
• 本题的图结构：Graph
• 什么是最小生成树？
• Prim算法：根据最小边解锁to节点，并解锁to的邻居边
• 总结

生成树的定义

一个连通图的生成树是一个极小的连通子图，它包含图中全部的n个顶点，但只有构成一棵树的n-1条边。

本题的图结构：Graph

就是统一的丰富图结构表示法：
这个文章必须看透：
这个文章必须看透：
这个文章必须看透：
（1）图数据结构，图的统一数据结构和非标准图的转化算法

//这里就不得不复习一下图的结构，左神标准的结构
    //边结构
    public static class Edge{
        public Node from;
        public Node to;//源节点和目的节点
        public int weight;//边的权

        public Edge(int w, Node f, Node t){
            weight = w;
            from = f;
            to = t;
        }
    }
    //点结构
    public static class Node{
        public int value;//值，这种图已经有了的，并查集就不不要包装了
        public int in;
        public int out;
        public ArrayList<Node> nexts;//直接邻居一堆动态数组节点
        public ArrayList<Edge> edges;//直接邻居的边，动态数组，一堆，个图一样

        public Node(int v){
            value = v;
            in = 0;
            out = 0;
            nexts = new ArrayList<>();
            edges = new ArrayList<>();
        }
    }

    //图结构
    public static class Graph{
        public HashMap<Integer, Node> nodes;//图的一堆节点，包出来了，并查集就不用包了
        public HashSet<Edge> edges;//图的一堆边

        public Graph(){
            nodes = new HashMap<>();
            edges = new HashSet<>();
        }
    }

    //建图的标准函数
    //这个主要是标准的左神图结构，这个玩意用来规整最明了简洁的图结构，方便实现很多图的算法
    public static Graph generateGraph(int[][] matrix){
        if (matrix == null || matrix.length == 0) return null;

        //无非就是构造一堆图节点，将节点们的参数初始化，边，边的参数初始化
        //一般图结构是二维数组：matrix,第一列是权，第二列：from节点，第三列：to节点
        //int[][] matrix = {
        //                {1,1,2},
        //                {2,2,3},
        //                {3,1,3}
        //        };
        Graph graph = new Graph();
        for (int i = 0; i < matrix.length; i++) {
            //每一行，读出来，构造节点
            int weight = matrix[i][0];
            int from = matrix[i][1];
            int to = matrix[i][2];

            //造节点,图中没有才造，否则不必---不然就要出问题，多造一些节点，导致混乱
            //****************这里出过大错！！！
            if (!graph.nodes.containsKey(from)) graph.nodes.put(from, new Node(from));
            if (!graph.nodes.containsKey(to)) graph.nodes.put(to, new Node(to));

            //获取节点
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);

            //造边
            Edge edge = new Edge(weight, fromNode, toNode);
            graph.edges.add(edge);

            toNode.in++;
            fromNode.out++;
            fromNode.nexts.add(toNode);
            fromNode.edges.add(edge);
        }
        //每一行都建好，返回图即可
        return graph;
    }

    //这些结构需要多写几遍，才能熟悉，记住，跟奥运健儿一样，多练习，才能稳定发挥

---

什么是最小生成树？

所谓一个 带权图 的最小生成树，就是原图中边的权值最小的生成树 ，
所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。

---

Prim算法：根据最小边解锁to节点，并解锁to的邻居边

与Kruskal算法不同，Kruskal算法需要并查集，把最小边from和to节点所有集合合并。
（5）图的最小生成树：Kruskal算法–并查集的经典应用，解决连通性问题

Prim算法并不需要并查集

咱们Prim算法怎么做呢？
（1）从任意出发点head开始，解锁head的一批边放入edgeSet，也放入小根堆！
（2）从head已经解锁的边（heap）中，选择最小边解锁to节点（heapd出最小边），
如果to没有进入解锁点集合nodeSet，把边加入结果ans，然后直接解锁to的所有邻居边
（3）不断循环（2） *** 作，遍历完所有的

实现的逻辑如下图所示：v0开始解锁
边3最小，选3这条边，解锁v1节点，边3做咱们的最小生成树ans，自然也就解锁了v1的5 6 8三条边

但是显然，4更小，所以解锁v5节点,边4加入最小生成树ans
然后解锁v5的邻居7 18 两条边

下一次选最小边，自然是5，解锁v8节点，然后把边5放入最小生成树ans，将v8的邻居解锁，边2 和 11解锁

自然选边2最小，将其放入最小生成树ans，解锁v2，和v2的邻居边，12，（其他的解锁过了）

再选最小边，6，解锁v6，边6加入最小生成树ans。

选目前剩下的最小边9，解锁v7,9边进入最小生成树ans，解锁v7邻居边6和1边

自然选1边最小了此时，解锁v4，把边1放入最小生成树ans，解锁边10

最后还有v3没进去，自然选择最小边6，解锁v3，成交！！

不复杂吧，思想很明确，每次找最小边，连同它这个邻居没进来的点。

既然需要小根堆，那就需要比较器：

//升序按权排序
    public static class heapComparator implements Comparator<Edge>{
        @Override
        public int compare(Edge o1, Edge o2){
            return o1.weight - o2.weight;
        }
    }

懂了思想，就可以手撕代码：

public static HashSet<Edge> primMST(Graph graph){
        if (graph == null) return null;

        //用的基础数据结构
        PriorityQueue<Edge> heap = new PriorityQueue<>(new heapComparator());
        HashSet<Edge> edgeSet = new HashSet<>();
        HashSet<Node> nodeSet = new HashSet<>();//装解锁边和点
        HashSet<Edge> res = new HashSet<>();//装结果

        //先找一个点，解锁它所有的边
        Node start = null;
        for (Node node:graph.nodes.values()){
            start = node;
            break;//据说用这个的意思就是防止森林的出现，很可能不连通
        }
        //保证这起点都没有被解锁过
        if (!nodeSet.contains(start)){
            for(Edge edge:start.edges){
                if (!edgeSet.contains(edge)){
                    heap.add(edge);
                    edgeSet.add(edge);//解锁他们这些边
                }
            }

            //然后开始解锁最小边的邻居点，及邻居点的所有边，然后继续循环本 *** 作
            while (!heap.isEmpty()){
                Edge minEdge = heap.poll();//找到最小边
                Node toNode = minEdge.to;//找到to节点
                //to节点没有解锁过，就将这个最小边加入结果
                if (!nodeSet.contains(toNode)){
                    res.add(minEdge);
                    nodeSet.add(toNode);//解锁它
                    //然后就要解锁这个节点的所有边
                    for (Edge edge:toNode.edges){
                        if (!edgeSet.contains(edge)){
                            heap.add(edge);
                            edgeSet.add(edge);
                        }
                    }
                }
            }
        }
        return res;
    }

验证一波：

public static void test(){
        //造一个图

        int[][] matrix = {
                {1,1,2},
                {2,2,3},
                {3,3,4},
                {100,4,5},
                {5,2,5},
                {100,2,6},
                {7,5,6}
        };
        Graph graph = generateGraph(matrix);
        HashSet<Edge> minEdge = primMST(graph);
        for (Edge edge:minEdge){
            System.out.println(edge.weight);
        }
    }

    public static void main(String[] args) {
        test();
    }

结果OK

3
5
2
1
7

---

总结

提示：重要经验：

1）图的算法是真的不困难，核心思想很简单，但是图的数据结构很难，在互联网大厂笔试面试中，没有任何人可以在笔试或者面试中写出来，时间太久了，这也不是考你撸代码的实力的好办法，更不是考你优化算法能力的最佳方案
2）Prim算法的关键就是每次拉所有解锁边中最小权重的那个边，进来，做最小生成树。
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。