最小生成树问题与Prim、Kruskal算法

痛定思痛。 2023-07-12 03:49 31阅读 0赞

### 文章目录 ###

*   *   *  一.带权图基础
         *   *  1.什么是带权图
             *  2.如何实现
             *  3.Java代码实现
         *  二.最小生成树与切分定理
         *   *  1.最小生成树（Min Span Tree，MST）
             *  2.切分定理
         *  三.Prim算法
         *   *  1.Lazy Prim算法
             *   *  1.算法思路
                 *  2.代码实现
                 *  3.时空复杂度
             *  2.Direct Prim算法
         *  四.Kruskal算法
         *   *  1.算法思路
             *  2.代码实现
             *  3.时空复杂度

### 一.带权图基础 ###

#### 1.什么是带权图 ####

带权图指的是顶点之间的不仅有连接关系，并且连接关系上带有权重。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh_size_16_color_FFFFFF_t_70]

#### 2.如何实现 ####

对于带权图来说，由于比无权图多了一项权重，所以需要多使用一个数据结构来描述“边的权重”，所以需要多出一个Edge类。

#### 3.Java代码实现 ####

依然使用邻接表来表示带权图：

*  WeightGraph

/** * @Auther: ARong * @Date: 2020/3/4 5:37 下午 * @Description: 带权图的邻接表实现 */
    public class WeightGraph { 
        /* * 边数据结构 */
        private static class Edge { 
            private int a; // 第一个顶点编号
            private int b; // 第二个顶点编号
            private int weight; // 权重
    
            public Edge(int a, int b, int weight) { 
                this.a = a;
                this.b = b;
                this.weight = weight;
            }
    
            public Edge(Edge edge) { 
                this.a = edge.a;
                this.b = edge.b;
                this.weight = edge.weight;
            }
    
            public int getV() { 
                return a;
            }
    
            public int getW() { 
                return b;
            }
    
            public int getWeight() { 
                return weight;
            }
    
            public int getOther(int x) { 
                assert x == a || x == b;
                return x == a ? b : a;
            }
    
            @Override
            public String toString() { 
                return String.format("%d-%d: %d", a, b, weight);
            }
    
        }
    
    
        // 顶点数
        private int vertexNum;
        // 边数
        private int edgeNum;
        // 带权图,每个顶点都含有一个含有边的链表
        private List<Edge>[] graph;
        // 是否为有向图
        private boolean directed;
    
        public WeightGraph(int vertexNum, boolean directed) { 
            this.vertexNum = vertexNum;
            this.directed = directed;
            // 初始化邻接表
            graph = (LinkedList<Edge>[]) new LinkedList[vertexNum];
            for (int i = 0; i < vertexNum; i++) { 
                graph[i] = new LinkedList<Edge>();
            }
        }
    
        public int getVertexNum() { 
            return vertexNum;
        }
    
        public int getEdgeNum() { 
            return edgeNum;
        }
        
        public List<Edge>[] getGraph() { 
            return graph;
        }
        
        /* * @Author ARong * @Description 在图中添加一条边 * @Date 2020/3/4 5:58 下午 * @Param [w, v, weight] * @return void **/
        public void addEdge(int w, int v, int weight) { 
            assert w >= 0 && w < vertexNum && v >= 0 && v < vertexNum;
            // 获取w的边链表，添加w->v的关系
            List<Edge> edges1 = graph[w];
            Edge newEdge1 = new Edge(w, v, weight);
            edges1.add(newEdge1);
            if (!directed) { 
                // 无向图，在增加另一边的关系
                // 获取v的边链表，添加v->w的关系
                List<Edge> edges2 = graph[v];
                Edge newEdge2 = new Edge(v, w, weight);
                edges2.add(newEdge2);
            }
    
            // 边数增加
            edgeNum++;
        }
        public void print() { 
            System.out.println(String.format("顶点数:%d, 边数:%d", vertexNum, edgeNum));
            for (int i = 0; i < graph.length; i++) { 
                // 取出每个边链表进行遍历
                List<Edge> edges = graph[i];
                Iterator<Edge> iterator = edges.iterator();
                StringBuilder str = new StringBuilder(i + "-\t");
                while (iterator.hasNext()) { 
                    Edge edge = iterator.next();
                    System.out.println(String.format("%d - %d : %d", edge.a, edge.b, edge.weight));
                }
            }
        }
    
    
        public static void main(String[] args) { 
            WeightGraph graph = new WeightGraph(4, false);
            graph.addEdge(0, 1, 8);
            graph.addEdge(0, 2, 9);
            graph.addEdge(0, 3, 5);
            graph.addEdge(1, 2, 7);
            graph.addEdge(2, 3, 6);
    
            graph.print();
    
        }
    }

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AXm2EwqA-1583500038524)(http://note.youdao.com/yws/res/14173/C42812DC7BD544BD827ECB23C745952E)\]][img-AXm2EwqA-1583500038524_http_note.youdao.com_yws_res_14173_C42812DC7BD544BD827ECB23C745952E]

顶点数:4, 边数:5
    0 - 1 : 8
    0 - 2 : 9
    0 - 3 : 5
    1 - 0 : 8
    1 - 2 : 7
    2 - 0 : 9
    2 - 1 : 7
    2 - 3 : 6
    3 - 0 : 5
    3 - 2 : 6

### 二.最小生成树与切分定理 ###

#### 1.最小生成树（Min Span Tree，MST） ####

**最小生成树其实是最小权重生成树的简称。**

**一个含有v个顶点的连通图，可以使用v - 1条边将其全部连接起来，而当这v - 1条边的权重累加值最小时，该v个顶点与v - 1条边组成的树被称为最小生成树。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh_size_16_color_FFFFFF_t_70 1]  
最小生成树在布线方面有十分重要的应用，如果将图中的顶点视为城市，那么如何布置电话线路使得所有城市可以被连通起来，且线路费用最小就是一个经典的最小生成树问题。

#### 2.切分定理 ####

*  定义一：把图中的结点分为两部分，称为一个切分(Cut)
 *  定义二：如果一个边的两个端点，属于切分不同的两边，这个边称为横切边(Crossing Edge)
 *  切分定理：给定任意切分，横切边中权值最小的边必然属于最小生成树  
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh_size_16_color_FFFFFF_t_70 2][]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh_size_16_color_FFFFFF_t_70 3]

### 三.Prim算法 ###

Prim即普里姆算法，是一种简单求解最小生成树的算法，此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。

算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。

#### 1.Lazy Prim算法 ####

##### 1.算法思路 #####

Prim算法的懒惰实现过程是：

1.  从第0个顶点开始，将访问到的顶点记录起来
2.  获取到顶点的所有邻边（注意该边的另一端的顶点必须没有被访问过，不然该边不属于横切边），并且将边的权值加入到最小堆中
3.  从最小堆中取出当前最小边，根据切分定理，这条边肯定为MST的一条边
4.  将当前顶点设置为该最小边的另一头顶点，开始重复1、2、3过程
5.  当最小堆为空时，MST构造完成  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh_size_16_color_FFFFFF_t_70 4]

##### 2.代码实现 #####

/** * @Auther: ARong * @Date: 2020/3/6 4:17 下午 * @Description: 最小生成树问题-Lazy Prim算法 */
    public class LazyPrimMST { 
        private WeightGraph graph;// 图的引用
        private PriorityQueue<WeightGraph.Edge> minHeap;// 最小堆
        private boolean[] marked; // 标记数组，在算法运行过程中标记结点 i 是否被访问
        private List<WeightGraph.Edge> mst; // 最小生成树所包含的所有边
        private Integer mstWeight;//最小生成树的权值
    
        /* * @Author ARong * @Description 实现Lazy Prim算法 * @Date 2020/3/6 4:38 下午 * @Param [graph] * @return **/
        public LazyPrimMST(WeightGraph graph) { 
            this.graph = graph;
            // 构造Edge的最小堆
            minHeap = new PriorityQueue<>((e1 ,e2)->{ 
                return e1.getWeight() - e2.getWeight();
            });
            marked = new boolean[graph.getVertexNum()];
            mst = new ArrayList<>();
    
            // Lazy Prim
            // 1. 首先访问第0个顶点
            visit(0);
            // 2. minHeap不为空时进行MST的收集
            while (!minHeap.isEmpty()) { 
                WeightGraph.Edge minEdge = minHeap.poll();
                // 这条边两端都被访问过，则抛弃
                if (marked[minEdge.getV()] && marked[minEdge.getW()]) { 
                    continue;
                }
                mst.add(minEdge);
                // 继续在未访问过的顶点进行访问
                if (!marked[minEdge.getV()]) { 
                    visit(minEdge.getV());
                } else { 
                    visit(minEdge.getW());
                }
            }
        }
    
        public List<WeightGraph.Edge> getMst() { 
            return mst;
        }
    
        public int getWeight() { 
            // 将mst中的权值累加返回
            int total = 0;
            for (WeightGraph.Edge edge : mst) { 
                total += edge.getWeight();
            }
            return total;
        }
    
        /* * @Author ARong * @Description 访问第v个顶点，设置访问标示，并且将其尚未访问过的邻边加入到最小堆中（横切边） * @Date 2020/3/6 4:45 下午 * @Param [index] * @return void **/
        private void visit(int v) { 
            if (marked[v] || v >= graph.getVertexNum()) { 
                return;
            }
            // 访问标示
            marked[v] = true;
            // 将v尚未访问过的邻边加入到最小堆中（横切边）
            for (WeightGraph.Edge edge : graph.getGraph()[v]) { 
                // 改变的另一个节点一定不可被访问过，否则不是横切边
                if (!marked[edge.getOther(v)]) { 
                    minHeap.offer(edge);
                }
            }
        }
    
    
        public static void main(String[] args) { 
            WeightGraph graph = new WeightGraph(4, false);
            graph.addEdge(0, 1, 8);
            graph.addEdge(0, 2, 9);
            graph.addEdge(0, 3, 5);
            graph.addEdge(1, 2, 7);
            graph.addEdge(2, 3, 6);
    
            graph.print();
    
            // 获取mst
            LazyPrimMST lazyPrimMST = new LazyPrimMST(graph);
            System.out.println(lazyPrimMST.getMst());
            System.out.println(lazyPrimMST.getWeight());
        }
    }

顶点数:4, 边数:5
    0 - 1 : 8
    0 - 2 : 9
    0 - 3 : 5
    1 - 0 : 8
    1 - 2 : 7
    2 - 0 : 9
    2 - 1 : 7
    2 - 3 : 6
    3 - 0 : 5
    3 - 2 : 6
    [0-3: 5, 3-2: 6, 2-1: 7]
    18

##### 3.时空复杂度 #####

Lazy Prim算法懒惰的地方在于，minHeap中其实存储了很多不可能再构成横切边的边，但是在Lazy Prim算法中并不给予清除，而是使用了marked数组来判断其是否为横切边。

设图中有E个条边，V个节点，那么有：

*  空间复杂度：O（E），堆中需要放置全部边
 *  时间复杂度：O（ElogE），每次visit为O（logE），一共进行了E次

#### 2.Direct Prim算法 ####

Prim算法的即时实现优化了最小堆的空间，一般是借助最小索引堆来实现。

具体的实现思路与Lazy Prim差不多，具体可以参考：

[https://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html][https_www.cnblogs.com_biyeymyhjob_archive_2012_07_30_2615542.html]

### 四.Kruskal算法 ###

Kruskal算法即克鲁斯卡尔算法，是相较于Prim算法的另一个被用于求最小生成树问题的算法，它采取的是贪心策略。首先将边通过升序排列起来，然后不断地挑选出最小的边，并判断取出该边作为最小生成树的边是否会产生环，若不会则该边就是最小生成树的一条边。Krsukal算法又被称为“加边法”。

#### 1.算法思路 ####

1.  先将边存储进最小堆中
2.  每次取出最小的边，通过并查集判断该边的两个顶点是否连通分量，不连通则不会成环，取出该边作为最小生成树的一条边
3.  将该边的两个顶点连通起来
4.  重复1，2，3过程，直到最小生成树的边数 = 顶点数 - 1  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh_size_16_color_FFFFFF_t_70 5]

#### 2.代码实现 ####

*  KruskalMST

/** * @Auther: ARong * @Date: 2020/3/6 7:00 下午 * @Description: Kruskal算法求解最小生成树 */
    public class KruskalMST { 
        private WeightGraph graph;// 图的引用
        private PriorityQueue<WeightGraph.Edge> minHeap;// 最小堆
        private List<WeightGraph.Edge> mst; // 最小生成树所包含的所有边
        private Integer mstWeight;//最小生成树的权值
    
    
        /* * @Author ARong * @Description kruskal算法实现最小生成树 * @Date 2020/3/6 8:50 下午 * @Param [graph] * @return **/
        public KruskalMST(WeightGraph graph) { 
            this.graph = graph;
            // 构造Edge的最小堆
            minHeap = new PriorityQueue<>((e1 ,e2)->{ 
                return e1.getWeight() - e2.getWeight();
            });
            mst = new ArrayList<>();
    
            // Kruskal
            // 1. 将所有的边添加到最小堆中
            for (int i = 0; i < graph.getGraph().length; i++) { 
                List<WeightGraph.Edge> edges = graph.getGraph()[i];
                for (WeightGraph.Edge edge : edges) { 
                    // 防止重复加入边
                    if (edge.getV() < edge.getW()) { 
                        minHeap.add(edge);
                    }
                }
            }
            // 2. 创建并查集，保存顶点间的连通关系
            UnionFind unionFind = new UnionFind(graph.getVertexNum());
            // 3. 收集到mst的边数 = 顶点数 - 1时即完成最小生成树的边数收集
            while (!minHeap.isEmpty() && mst.size() < graph.getVertexNum() - 1) { 
                WeightGraph.Edge minEdge = minHeap.poll();
                // 判断顶点是否连通成环，不成环则加入mst
                if (unionFind.find(minEdge.getV(), minEdge.getW())) { 
                    continue;
                }
                // 加入mst和并查集
                mst.add(minEdge);
                unionFind.union(minEdge.getV(), minEdge.getW());
            }
        }
    
        public List<WeightGraph.Edge> getMst() { 
            return mst;
        }
    
        public int getWeight() { 
            // 将mst中的权值累加返回
            int total = 0;
            for (WeightGraph.Edge edge : mst) { 
                total += edge.getWeight();
            }
            return total;
        }
    
        public static void main(String[] args) { 
            WeightGraph graph = new WeightGraph(4, false);
            graph.addEdge(0, 1, 8);
            graph.addEdge(0, 2, 9);
            graph.addEdge(0, 3, 5);
            graph.addEdge(1, 2, 7);
            graph.addEdge(2, 3, 6);
    
            graph.print();
    
            // 获取mst
            KruskalMST kruskalMST = new KruskalMST(graph);
            System.out.println(kruskalMST.getMst());
            System.out.println(kruskalMST.getWeight());
        }
    }

*  UnionFind

/** * @Auther: ARong * @Date: 2020/3/6 7:05 下午 * @Description: 并查集实现 */
    public class UnionFind { 
        // 存储元素的父节点索引
        private int[] parent;
    
    
        public UnionFind(int capacity) { 
            parent = new int[capacity];
            // 初始化parent数组，让各个元素的父节点指向自身,表面其自身已经是根节点
            for (int i = 0; i < parent.length; i++) { 
                parent[i] = i;
            }
        }
    
        /* * @Author ARong * @Description 判断x与y是否连通 * @Date 2020/3/6 7:08 下午 * @Param [x, y] * @return boolean **/
        public boolean find(int x, int y) { 
            // 根节点相同
            if (find(x) == find(y)) { 
                return true;
            }
            return false;
        }
    
        /* * @Author ARong * @Description 查询x的根节点 * @Date 2020/3/6 7:09 下午 * @Param [x] * @return int **/
        private int find(int x) { 
            if (x == parent[x]) { 
                return x;
            }
    // while (x != parent[x]) { 
    // x = parent[x];
    // }
            // 路径压缩，在寻找根节点的过程中不断地将节点的父节点往上挪，最后形成两层
            if (x != parent[x]) { 
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
    
        /* * @Author ARong * @Description 将x与y相连通 * @Date 2020/3/6 7:13 下午 * @Param [x, y] * @return void **/
        public void union(int x, int y) { 
            if (find(x) == find(y)) { 
                return;
            }
            parent[find(x)] = find(y);
        }
    }

顶点数:4, 边数:5
    0 - 1 : 8
    0 - 2 : 9
    0 - 3 : 5
    1 - 0 : 8
    1 - 2 : 7
    2 - 0 : 9
    2 - 1 : 7
    2 - 3 : 6
    3 - 0 : 5
    3 - 2 : 6
    [0-3: 5, 2-3: 6, 1-2: 7]
    18

#### 3.时空复杂度 ####

1.  空间复杂度：O（E），E为边数
2.  时间复杂度：O（ElogE）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200306210822938.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh,size_16,color_FFFFFF,t_70
[img-AXm2EwqA-1583500038524_http_note.youdao.com_yws_res_14173_C42812DC7BD544BD827ECB23C745952E]: https://img-blog.csdnimg.cn/20200306210843628.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200306210905986.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200306210926827.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200306210944463.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200306211046178.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh,size_16,color_FFFFFF,t_70
[https_www.cnblogs.com_biyeymyhjob_archive_2012_07_30_2615542.html]: https://www.liwei.party/2019/01/16/algorithms-and-data-structures/minimum-span-trees/#toc-heading-3
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200306211202520.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh,size_16,color_FFFFFF,t_70