Java图论进阶之最小生成树算法详解

目录
  • 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为止.

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

步骤分析:

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();
    }
}

 测试结果:

1.2 Prime(普里姆) 算法

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

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

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

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

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

代码示例:

/**
     * 普里姆算法实现
     * @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();
    }

总结

到此这篇关于Java图论进阶之最小生成树算法的文章就介绍到这了,更多相关Java最小生成树算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java图论普利姆及克鲁斯卡算法解决最小生成树问题详解

    目录 什么是最小生成树? 普利姆算法  算法介绍 应用 --> 修路问题  图解分析  克鲁斯卡尔算法 算法介绍 应用场景 -- 公交站问题  算法图解   算法分析  如何判断是否构成回路 什么是最小生成树? 最小生成树(Minimum Cost Spanning Tree),简称MST. 最小生成树要求图是连通图.连通图指图中任意两个顶点都有路径相通,通常指无向图.理论上如果图是有向.多重边的,也能求最小生成树,只是不太常见. 普利姆算法  算法介绍 应用 --> 修路问题  图解分析 

  • Java求最小生成树的两种算法详解

    目录 1 最小生成树的概述 2 普里姆算法(Prim) 2.1 原理 2.2 案例分析 3 克鲁斯卡尔算法(Kruskal) 3.1 原理 3.2 案例分析 4 邻接矩阵加权图实现 5 邻接表加权图实现 6 总结 介绍了图的最小生成树的概念,然后介绍了求最小生成树的两种算法:Prim算法和Kruskal算法的原理,最后提供了基于邻接矩阵和邻接链表的图对两种算法的Java实现. 阅读本文需要一定的图的基础,如果对于图不是太明白的可以看看这篇文章:Java数据结构之图的原理与实现. 1 最小生成树的

  • Java实现最小生成树算法详解

    目录 定义 带权图的实现 Kruskal 算法 二叉堆 并查集 实现算法 Prim 算法 定义 在一幅无向图G=(V,E) 中,(u,v) 为连接顶点u和顶点v的边,w(u,v)为边的权重,若存在边的子集T⊆E且(V,T) 为树,使得 最小,这称 T 为图 G 的最小生成树. 说的通俗点,最小生成树就是带权无向图中权值和最小的树.下图中黑色边所标识的就是一棵最小生成树(图片来自<算法第四版>),对于权值各不相同的连通图来说最小生成树只会有一棵: 带权图的实现 在 <如何在 Java 中实

  • Java实现最小生成树MST的两种解法

    目录 一.prim算法 二.kruskal算法 一.prim算法 时间复杂度较之kruskal较高 通俗的解释就是: (1)从哪个点开始生成最小生成树都一样,最后的权值都是相同的 (2)从哪个点开始,先标记这个点是访问过的,用visited数组表示所有节点的访问情况 (3)访问节点开始都每个没访问结点的距离选取形成的边的权值最小值 综合以上三点就是我们prim算法写代码实现的重要思路 代码实现: package Prim; import java.util.Arrays; public clas

  • Java图论进阶之最小生成树算法详解

    目录 1. 最小生成树 1.1 Kruskal(克鲁斯卡尔) 算法 1.2 Prime(普里姆) 算法 总结 1. 最小生成树 连通图中的每一棵生成树 , 都是原图的极大无环子图 , 即: 从中删去任何一条边 , 生成树就不再连通;反之 , 在其中引入任何一条新边 , 都会形成一条回路. 若连通图由n个顶点组成 , 则其生成树必含n个顶点和n-1条边 , 因此构造最小生成树有三个准则: 1.只能使用图中的边来构造最小生成树 2.只能使用恰好n-1条边来连接图中的n个顶点 3.选用的n-1条边不能

  • Java实现深度搜索DFS算法详解

    目录 DFS概述 解释 思路 案例题-单身的蒙蒙 题目描述 题解 整体代码 DFS概述 深度优先搜索是一种在开发爬虫早期使用较多的方法.它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) .在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链.深度优先搜索沿着HTML文件上的超链走到不能再深入为止,然后返回到某一个HTML文件,再继续选择该HTML文件中的其他超链.当不再有其他超链可选择时,

  • Java垃圾回收之复制算法详解

    之前的Java垃圾回收之标记清除算法详解 会导致内存碎片.下文的介绍的coping算法可以解决内存碎片问题. 概述 如果jvm使用了coping算法,一开始就会将可用内存分为两块,from域和to域, 每次只是使用from域,to域则空闲着.当from域内存不够了,开始执行GC操作,这个时候,会把from域存活的对象拷贝到to域,然后直接把from域进行内存清理. 应用场景 coping算法一般是使用在新生代中,因为新生代中的对象一般都是朝生夕死的,存活对象的数量并不多,这样使用coping算法

  • Java实现的最大匹配分词算法详解

    本文实例讲述了Java实现的最大匹配分词算法.分享给大家供大家参考,具体如下: 全文检索有两个重要的过程: 1分词 2倒排索引 我们先看分词算法 目前对中文分词有两个方向,其中一个是利用概率的思想对文章分词. 也就是如果两个字,一起出现的频率很高的话,我们可以假设这两个字是一个词.这里可以用一个公式衡量:M(A,B)=P(AB)/P(A)P(B),其中 A表示一个字,B表示一个字,P(AB)表示AB相邻出现的概率,P(A)表示A在这篇文章中的频度,P(B)表示B在这篇文章中的频度.用概率分词的好

  • Java垃圾回收之分代收集算法详解

    概述 这种算法,根据对象的存活周期的不同将内存划分成几块,新生代和老年代,这样就可以根据各个年代的特点采用最适当的收集算法.可以用抓重点的思路来理解这个算法. 新生代对象朝生夕死,对象数量多,只要重点扫描这个区域,那么就可以大大提高垃圾收集的效率.另外老年代对象存储久,无需经常扫描老年代,避免扫描导致的开销. 新生代 在新生代,每次垃圾收集器都发现有大批对象死去,只有少量存活,采用复制算法,只需要付出少量存活对象的复制成本就可以完成收集:可以参看我之前写的Java垃圾回收之复制算法详解 老年代

  • Java搜索与图论之DFS和BFS算法详解

    目录 DFS和BFS简介 DFS数字排序 DFS皇后排序 DFS树的重心 BFS走迷宫 BFS八数码 BFS图层次 本次我们介绍搜索与图论篇中DFS和BFS,我们会从下面几个角度来介绍: DFS和BFS简介 DFS数字排序 DFS皇后排序 DFS树的重心 BFS走迷宫 BFS八数码 BFS图层次 DFS和BFS简介 首先我们先来介绍一下DFS和BFS: DFS:深度优先遍历算法,我们在进行算法运算时,优先将该路径的当前路径执行完毕,执行完毕或失败后向上回溯尝试其他途径 BFS:广度优先遍历算法,

  • java 中归并排序算法详解

    java 中归并排序算法详解 归并排序算法,顾名思义,是一种先分再合的算法,其算法思想是将要排序的数组分解为单个的元素,每个元素就是一个单个的个体,然后将相邻的两个元素进行从小到大或从大到小的顺序排序组成一个整体,每个整体包含一到两个元素,然后对相邻的整体继续"合"并,因为每个整体都是排过序的,因而可以采用一定的算法对其进行合并,合并之后每个整体包含三到四个元素,继续对相邻的整体进行合并,直到所有的整体都合并为一个整体,最终得到的整体就是将原数组进行排序之后的结果. 对于相邻的整体,其

  • Java语言实现快速幂取模算法详解

    快速幂取模算法的引入是从大数的小数取模的朴素算法的局限性所提出的,在朴素的方法中我们计算一个数比如5^1003%31是非常消耗我们的计算资源的,在整个计算过程中最麻烦的就是我们的5^1003这个过程 缺点1:在我们在之后计算指数的过程中,计算的数字不都拿得增大,非常的占用我们的计算资源(主要是时间,还有空间) 缺点2:我们计算的中间过程数字大的恐怖,我们现有的计算机是没有办法记录这么长的数据的,所以说我们必须要想一个更加高效的方法来解决这个问题 当我们计算AB%C的时候,最便捷的方法就是调用Ma

随机推荐