[Java]图论进阶--最小生成树算法

系统管理员 2024-03-31 13:51 64阅读 0赞

![941a288ae22847979345f473556a3941.gif][]

--------------------

> ![c4304daa3a1846adadc000eea43efbf4.png][]专栏简介 :java语法及数据结构
> 
> ![1254c5b119a44cf0ae350489fb7736ad.png][]题目来源:leetcode,牛客,剑指offer.
> 
> ![4366a93aaa3142b5a0f16c7a2200339b.png][]创作目标:记录学习MySql学习历程
> 
> ![52a3437a932f4621b25533c330f7c6cb.png][]希望在提升自己的同时,帮助他人,,与大家一起共同进步,互相成长.
> 
> ![14aa2f0648ae44a299b8f9832af57d2c.png][]学历代表过去,能力代表现在,学习能力代表未来!

--------------------

## 目录 ##

1. 最小生成树

1.1 Kruskal(克鲁斯卡尔) 算法

1.2 Prime(普里姆) 算法

--------------------

## 1. 最小生成树 ##

连通图中的每一棵生成树 , 都是原图的极大无环子图 , 即: **从中删去任何一条边 , 生成树就不再连通;反之 , 在其中引入任何一条新边 , 都会形成一条回路**.

若连通图由n个顶点组成 , 则其生成树必含n个顶点和n-1条边 , 因此构造最小生成树有三个准则:

>  *  **1.只能使用图中的边来构造最小生成树**
>  *  **2.只能使用恰好n-1条边来连接图中的n个顶点**
>  *  **3.选用的n-1条边不能构成回路**

常见求解最小生成树的算法有: Kruskal算法和Prime算法.两种算法都采用逐步求解的贪心策略.

贪心算法: 通过局部最优解来推出全局最优解.

--------------------

### 1.1 Kruskal(克鲁斯卡尔) 算法 ###

给定一个有n个顶点的连通网络N=\{V,E\}

首先构造一个由这n个顶点组成 , 不含任何边的图G=\{V,NULL\}.

其次不断从E中取出权值最小的一条边(若有多条任选其一) , 若该边的两个顶点来自不同的连通分量 , 则将此边加入到G中.

如此反复 , 直到G中边数达到顶点数-1为止.

**核心: 每次迭代时 , 选出权值最小且两端点不在同一连通分量上的边 , 加入生成树.**

![c392cbdf002a4251804ab991fd4e5d5a.png][]

**步骤分析:**

>  *  1.由于该算法的思想是全局贪心 , 因此将所有图中所有边全部放入优先级队列中.
>  *  2.构造一个最小生成树 , 将优先级队列中的边依次加入.
>  *  3.为了防止出现环 , 使用并查集判断每次取出的边的顶点是否来自同一个集合 .
>  *  4.如果不是同一集合 , 将该边加入最小生成树并用并查集将该边的领接顶点放入同一个 集合.

**代码示例:**

/**
         * 克鲁斯卡尔算法实现
         * @param minTree
         * @return
         */
        /**
         * 模拟实现一条边
         */
        static class Edge{
            public int srcIndex;
            public int destIndex;
            public int weight;
    
            public Edge(int srcIndex, int destIndex, int weight) {
                this.srcIndex = srcIndex;
                this.destIndex = destIndex;
                this.weight = weight;
            }
        }
    
        public int kruskal(GraphOfMatrix minTree) {
            //1.定义一个优先级队列
            PriorityQueue<Edge> minQ = new PriorityQueue<Edge>(new Comparator<Edge>() {
                @Override
                public int compare(Edge o1, Edge o2) {
                    return o1.weight - o2.weight;
                }
            });
            int n = arrayV.length;
            //2.遍历领接矩阵,将所有的边都放入优先级队列中
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i < j && Matrix[i][j] != Integer.MIN_VALUE) {
                        minQ.offer(new Edge(i, j, Matrix[i][j]));
                    }
                }
            }
            //3.构造并查集将符合要求的边加入到最小生成树中
            UnionFindSet ufs = new UnionFindSet(n);
    
            int size = 0;//记录最小生成树中边的数量
            int totalWeight = 0;//记录权值
            while (size < n - 1 && !minQ.isEmpty()) {
                Edge edge = minQ.poll();
                int srcIndex = edge.srcIndex;
                int destIndex = edge.destIndex;
                //同一边的相邻顶点不能来自同一集合
                if (!ufs.isSameUnionFindSet(srcIndex, destIndex)) {
                    //将符合条件的边加入到最小生成树中
                    minTree.addEdgeUseIndex(srcIndex, destIndex, Matrix[srcIndex][destIndex]);
                    System.out.println("选择的边"+arrayV[srcIndex]+" -> "+arrayV[destIndex]+Matrix[srcIndex][destIndex]);
                    size++;
                    totalWeight += Matrix[srcIndex][destIndex];
                    //将添加过的边的相邻顶点放入同一集合,防止出现环.
                    ufs.union(srcIndex, destIndex);
                }
            }
            if (size == n - 1) {
                return totalWeight;
            } else {
                throw new RuntimeException("没有最小生成树");
            }
        }
    
       //按照下标将边加入到最小生成树中
        public void addEdgeUseIndex(int srcIndex,int destIndex,int weight){
            Matrix[srcIndex][destIndex] = weight;
            //如果是无向图邻接矩阵对称位置也要添加
            if (!isDirect){
                Matrix[destIndex][srcIndex] = weight;
            }
        }
        //测试克鲁斯卡尔算法
        public static void main(String[] args) {
            String str = "abcdefghi";
            char[] array =str.toCharArray();
            graph.GraphOfMatrix g = new graph.GraphOfMatrix(str.length(),false);
            g.initArray(array);
            g.addEdge('a', 'b', 4);
            g.addEdge('a', 'h', 8);
    //g.addEdge('a', 'h', 9);
            g.addEdge('b', 'c', 8);
            g.addEdge('b', 'h', 11);
            g.addEdge('c', 'i', 2);
            g.addEdge('c', 'f', 4);
            g.addEdge('c', 'd', 7);
            g.addEdge('d', 'f', 14);
            g.addEdge('d', 'e', 9);
            g.addEdge('e', 'f', 10);
            g.addEdge('f', 'g', 2);
            g.addEdge('g', 'h', 1);
            g.addEdge('g', 'i', 6);
            g.addEdge('h', 'i', 7);
            graph.GraphOfMatrix kminTree = new graph.GraphOfMatrix(str.length(),false);
            System.out.println(g.kruskal(kminTree));
            kminTree.printGraph();
        }

**构造并查集:**

public class UnionFindSet {
        public int[] elem;
    
        public UnionFindSet(int n){
            this.elem = new int[n];
            Arrays.fill(elem,-1);
        }
    
        /**
         * 查找数据x的根节点
         * @param x
         * @return
         */
        public int findRoot(int x){
            if (x < 0){
                throw new RuntimeException("下表不合法");
            }
            while (elem[x] >= 0){
                x = elem[x];
            }
            return x;
        }
        /**
         * 查询x1和x2是不是同一个集合
         * @param x1
         * @param x2
         * @return
         */
        public boolean isSameUnionFindSet(int x1 , int x2){
            int index1 = findRoot(x1);
            int index2 = findRoot(x2);
            if (index1 == index2){
                return true;
            }
            return false;
        }
    
        /**
         * 这是合并操作
         * @param x1
         * @param x2
         */
        public void union(int x1 , int x2){
            int index1 = findRoot(x1);
            int index2 = findRoot(x2);
            if (index1 == index2) return;
            elem[index1] = elem[index1] + elem[index2];
            elem[index2] = index1;
        }
    
        /**
         * 有几对关系
         * @return
         */
        public int getCount(){
            int count = 0;
            for (int x:elem) {
                if (x < 0){
                    count++;
                }
            }
            return count;
        }
        public void Print(){
            for (int x:elem){
                System.out.print(x+" ");
            }
            System.out.println();
        }
    }

**测试结果:**

![70502885a0a94b19a289fd8b7dad4732.png][]

--------------------

### 1.2 Prime(普里姆) 算法 ###

普里姆算法与克鲁斯卡尔算法类似 , 核心区别是普里姆算法采用局部贪心的思想.

首先 , 设定两个集合 , X\{\}已确定顶点的集合 , Y\{\}未确定顶点的集合.

其次 , 假设图中的顶点为 a,b,c,d,e,f,g,h,i.放入Y\{\}中.

然后 , 任取一个顶点放入X\{\}中 . 在Y\{\}中选择一个与该顶点相连权值最小的边 , 加入最小生成树中.

如此重复 , 直到最小生成树的边数达到顶点数-1为止.

![eafbaf0027424319ac519b13f98f3639.png][]

**代码示例:**

/**
         * 普里姆算法实现
         * @param minTree
         * @param chV 图中顶点的起点
         * @return
         */
        public int prime(GraphOfMatrix minTree,char chV) {
            int srcIndex = getIndexOfV(chV);
            //存储已确定的顶点
            Set<Integer> setX = new HashSet<>();
            setX.add(srcIndex);
            //初始化未确定的点
            Set<Integer> setY = new HashSet<>();
            int n = arrayV.length;
            for (int i = 0; i < n; i++) {
                if (i != srcIndex){
                    setY.add(i);
                }
            }
            //定义一个优先级队列
            PriorityQueue<Edge> minQ = new PriorityQueue<>(new Comparator<Edge>() {
                @Override
                public int compare(Edge o1, Edge o2) {
                    return o1.weight - o2.weight;
                }
            });
            //遍历srcIndex连接出去的边,并放入优先级队列中排序
            for (int i = 0; i < n; i++) {
                if (Matrix[srcIndex][i] != Integer.MIN_VALUE){
                    minQ.offer(new Edge(srcIndex,i,Matrix[srcIndex][i]));
                }
            }
            int size = 0;
            int totalWeight = 0;
            while (!minQ.isEmpty()){
                Edge min = minQ.poll();
                int srcI = min.srcIndex;
                int destI = min.destIndex;
                if (setX.contains(destI)){
                    //此时会构成环
                }else {
                    minTree.addEdgeUseIndex(srcI,destI,Matrix[srcI][destI]);
                    System.out.println("起点"+arrayV[srcI]+" -> "+"终点"+arrayV[destI]+Matrix[srcI][destI]);
                    size++;
                    totalWeight+=min.weight;
                    if (size == n-1){
                        return totalWeight;
                    }
                    //更新两个集合
                    setX.add(destI);
                    setY.remove(destI);
                    //把dest连出去的所有边也放到优先级队列中
                    for (int i = 0; i < n; i++) {
                        if (Matrix[destI][i] != Integer.MIN_VALUE && !setX.contains(i)){
                            minQ.offer(new Edge(destI,i,Matrix[destI][i]));
                        }
                    }
                }
            }
           throw new RuntimeException("没有最小生成树");
        }
        //测试普里姆算法
        public static void main3(String[] args) {
                String str = "abcdefghi";
                char[] array =str.toCharArray();
                GraphOfMatrix g = new GraphOfMatrix(str.length(),false);
                g.initArray(array);
                g.addEdge('a', 'b', 4);
                g.addEdge('a', 'h', 8);
    //g.addEdge('a', 'h', 9);
                g.addEdge('b', 'c', 8);
                g.addEdge('b', 'h', 11);
                g.addEdge('c', 'i', 2);
                g.addEdge('c', 'f', 4);
                g.addEdge('c', 'd', 7);
                g.addEdge('d', 'f', 14);
                g.addEdge('d', 'e', 9);
                g.addEdge('e', 'f', 10);
                g.addEdge('f', 'g', 2);
                g.addEdge('g', 'h', 1);
                g.addEdge('g', 'i', 6);
                g.addEdge('h', 'i', 7);
                GraphOfMatrix primTree = new GraphOfMatrix(str.length(),false);
                System.out.println(g.prime(primTree,'a'));
                primTree.printGraph();
        }

--------------------

##  ##

[941a288ae22847979345f473556a3941.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/a7fd04a85f8a4008990e3e6f8e853fc8.gif
[c4304daa3a1846adadc000eea43efbf4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6723993de8524e069f3b226f2e177837.png
[1254c5b119a44cf0ae350489fb7736ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f742e44272a344e984572f7ff5fba0ec.png
[4366a93aaa3142b5a0f16c7a2200339b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/1638b4c1da354d6489f35a2b17b31307.png
[52a3437a932f4621b25533c330f7c6cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/21bedd2b6239401d97db2091c79657e9.png
[14aa2f0648ae44a299b8f9832af57d2c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/96c795405b8842429bba10494188329c.png
[c392cbdf002a4251804ab991fd4e5d5a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/28e76f5d45e240a28fc480ff16ed287b.png
[70502885a0a94b19a289fd8b7dad4732.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/550556aa21864df883464f9d3275d50c.png
[eafbaf0027424319ac519b13f98f3639.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6acfab232ed84179901c78ab48bd2631.png