最小生成树-Kruskal算法(Java实现)

概念
  • 图的生成树是图的子图,并且不形成环路
  • 最小生成树是带权图中所有生成树里边权值总和最小的一个解,可能不唯一
算法思路
  1. 将图的所有边按权重排序
  2. 按顺序取出每条边
  3. 按原位置拼接,如果形成环就跳过这一条边的拼接

算法实现

图的实现
  • 此实现方法没有节点类
  • 采用邻接矩阵和顶点索引
  • 边类有两个成员变量,用于记录两个端点的索引int Aint B
  • 邻接矩阵int[][] matrix(邻接矩阵无需设置为沿对角线对称)
    • matrix[i][j]表示从索引i的节点指向索引j的节点的权值
    • 权值为0表示两点不连接或者自身与自身不连接
public class Graph<T> {
    private int N; // N个节点
    public int[][] matrix;  // 邻接矩阵
    private T[] datas;  // 保存每个节点的数据
    public List<Edge> edges = new ArrayList<>();
    class Edge {
        int A;  // 顶点索引
        int B;  // 顶点索引

        public Edge(int a, int b) {
            A = a;
            B = b;
        }

        @Override
        public String toString() {
            return "<" +
                    datas[A] +
                    "-" + matrix[A][B] + "-" + datas[B] +
                    '>';
        }
    }
}
两个重点
  • 每条边按权重排序
    • edges是图所有边的集合
    • 需要重写compare()方法,默认是升序排序
    • o1o2是两个对象也即两条边,return matrix[o1.A][o1.B] - matrix[o2.A][o2.B]的作用是,集合调用sort()方法进行排序时,按前一条边的权重减去后一条边的权重,小于0(前一条边的权重小)则两条边的位置不变,大于0则交换位置(大概意思是这样)
        edges.sort(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return matrix[o1.A][o1.B] - matrix[o2.A][o2.B];
            }
        });
  • 判断是否有环(回路)
    • 基本思路:判断一条边加入的时候两个端点的 "终点" 是否相同,相同则说明有环
    • getEnd()
      • int[] ends保存所有节点的终点索引,但不是一开始就确定,而是执行最小生成树算法的过程中才动态确定每个元素的一个数组
      • 最开始ends所有元素都是0
      • 如果传进来的索引iends[i] == 0则说明这个节点是第一次被访问到,则直接返回自身i(因为不会进入循环),表示此节点的终点是自己
      • 传进来索引iends[i] != 0则说明这个节点不是第一次被访问到,则把这个节点的终点索引赋值给i,如果ends[i]仍然不为0则说明最开始索引i的终点也有终点,则再把终点的终点索引赋值给iwhile (ends[i] != 0)的作用就是不断往下找到真正的终点
    • 在遍历边集合过程中,endOfA != endOfB如果边的两个端点的终点索引不同,ends[endOfA] = endOfB;则把第一个端点的终点的终点设置为第二个端点的终点(可能有点绕,这步骤的原因是两个端点终点不同,所以可以加入最终结果的边集合,也就是这条边已经确定加入图中,所以第一个端点必定能按这条边到达第二个端点的终点)
    /**
     * 本方法获取索引为i的顶点的终点, 用于判断两个顶点的终点是否相同
     *
     * @param ends 记录各个顶点的终点(遍历过程中才动态确定的数组)
     * @param i    传入的顶点索引
     * @return int 传入索引对应顶点的终点索引
     */
    private int getEnd(int[] ends, int i) {
        while (ends[i] != 0) {  // 循环是为了找到最终的终点
            i = ends[i];
        }
        return i;
    }

    /*****下面的代码在最小生成树算法主体方法中***********************/
            // 如果这条边取出来拼接后构成环, 则取消拼接操作
            int endOfA = getEnd(ends, edge.A);
            int endOfB = getEnd(ends, edge.B);
            // 如果边的第一个顶点的终点不等于第二个顶点的终点
            if (endOfA != endOfB) {
                // 设置第一个顶点的终点的终点为第二个顶点的终点
                ends[endOfA] = endOfB;
                result.add(edge);  // 最小生成树结果的边集合
            }
算法主体方法
  1. int[] ends保存取出各个边后依次拼接时, 各个顶点的终点索引
  2. 把边的权重排序
  3. List<Edge> result保存最终结果的所有边的集合
  4. 依次取出,不形成回路则拼接
  5. 将结果集合的所有边以邻接矩阵int[][] treeMatrix的形式表现
    /**
     * 克鲁斯卡尔算法-最小生成树
     *
     * @return void
     */
    public void KruskalTree() {
        // ends保存取出各个边后依次拼接时, 各个顶点的终点索引
        int[] ends = new int[N];
        // 把边的权重排序
        edges.sort(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return matrix[o1.A][o1.B] - matrix[o2.A][o2.B];
            }
        });
        // 保存最终结果的所有边的集合
        List<Edge> result = new ArrayList<>();
        // 依次取出并拼接
        for (Edge edge : edges) {
            // 如果这条边取出来拼接后构成环, 则取消拼接操作
            int endOfA = getEnd(ends, edge.A);
            int endOfB = getEnd(ends, edge.B);
            // 如果边的第一个顶点的终点不等于第二个顶点的终点
            if (endOfA != endOfB) {
                // 设置第一个顶点的终点的终点为第二个顶点的终点
                ends[endOfA] = endOfB;
                result.add(edge);
            }
        }
        // 查看一下结果
        System.out.println(result);
        // 返回最小生成树的邻接矩阵
        int[][] treeMatrix = new int[N][N];
        // 将结果集合的所有边以邻接矩阵的形式表现
        for (Edge edge : result) {
            treeMatrix[edge.A][edge.B] = matrix[edge.A][edge.B];
        }
        System.out.println("最小生成树的邻接矩阵: ");
        for (int[] nums : treeMatrix) {
            System.out.println(Arrays.toString(nums));
        }
    }
测试
  1. 6个节点,对应保存数据为字母ABCDEF
  2. int[][] set是为了初始化邻接矩阵graph.setMatrix(set[i][0], set[i][1], set[i][2])
  3. 设置边集合graph.setEdges()
  4. 执行算法graph.KruskalTree()
    public static void main(String[] args) {
        Graph<String> graph = new Graph<>(6);
        graph.setDatas(new String[]{"A", "B", "C", "D", "E", "F"});
        // {端点索引, 端点索引, 权值}
        int[][] set = {{0, 1, 1},
                {0, 2, 3},
                {1, 3, 2},
                {1, 5, 2},
                {2, 3, 4},
                {2, 5, 7},
                {3, 4, 1},
                {4, 5, 8}};

        for (int i = 0; i < set.length; i++) {
            // graph.setMatrix(端点索引, 端点索引, 权值)
            graph.setMatrix(set[i][0], set[i][1], set[i][2]);
        }
        graph.setEdges();
        graph.KruskalTree();
    }
测试结果
最小生成树

输出结果如下
[<A-1-B>, <D-1-E>, <B-2-D>, <B-2-F>, <A-3-C>]
最小生成树的邻接矩阵:
[0, 1, 3, 0, 0, 0]
[0, 0, 0, 2, 0, 2]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]

完整代码实现

public class Graph<T> {
    private int N; // 节点个数
    public int[][] matrix;  // 邻接矩阵
    private T[] datas;  // 保存每个节点的数据
    public List<Edge> edges = new ArrayList<>();  // 边集合

    class Edge {
        int A;  // 顶点索引
        int B;  // 顶点索引

        public Edge(int a, int b) {
            A = a;
            B = b;
        }

        // 重写toString()方法方便查看结果
        @Override
        public String toString() {
            return "<" +
                    datas[A] +
                    "-" + matrix[A][B] + "-" + datas[B] +
                    '>';
        }
    }

    public Graph(int N) {
        this.N = N;
        matrix = new int[N][N];
        statuses = new Status[N];
        datas = (T[]) new Object[N];  // 泛型数组实例化
    }

    /**
     * 邻接矩阵保存的信息是从一个节点指向另一个节点的信息
     *
     * @param from   从这个节点
     * @param to     指向这个节点
     * @param weight 路径权重
     * @return void
     */
    public void setMatrix(int from, int to, int weight) {
        matrix[from][to] = weight;
    }

    /**
     * 设置图的边(matrix初始化之后才调用)
     *
     * @return void
     */
    public void setEdges() {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] > 0) {
                    edges.add(new Edge(i, j));
                }
            }
        }
    }

    /**
     * 最小生成树中判断是否有回路的重要方法
     * 获取索引为i的顶点的终点, 用于判断两个顶点的终点是否相同
     *
     * @param ends 记录各个顶点的终点(遍历过程中才动态确定的数组)
     * @param i    传入的顶点索引
     * @return int 原顶点的终点索引
     */
    private int getEnd(int[] ends, int i) {
        System.out.print(datas[i] + "->");
        while (ends[i] != 0) {  // 艹我懂了: 循环是为了找到最终的终点
            i = ends[i];
        }
        System.out.println(datas[i]);

        return i;
    }

    /**
     * 克鲁斯卡尔算法-最小生成树
     *
     * @return void
     */
    public void KruskalTree() {
        // ends保存取出各个边后依次拼接时, 各个顶点的终点索引
        int[] ends = new int[N];
        // 把边的权重排序
        edges.sort(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return matrix[o1.A][o1.B] - matrix[o2.A][o2.B];
            }
        });
        // 保存最小生成树中包含的边集合
        List<Edge> result = new ArrayList<>();
        // 依次取出并拼接
        for (Edge edge : edges) {
            // 如果这条边取出来拼接后构成环, 则取消拼接操作
            int endOfA = getEnd(ends, edge.A);
            int endOfB = getEnd(ends, edge.B);
            // 如果边的第一个顶点的终点不等于第二个顶点的终点
            if (endOfA != endOfB) {
                // 设置第一个顶点的终点的终点为第二个顶点的终点
                ends[endOfA] = endOfB;
                result.add(edge);
            }
        }
        System.out.println(result);
        // 返回最小生成树的邻接矩阵
        int[][] treeMatrix = new int[N][N];
        for (Edge edge : result) {
            treeMatrix[edge.A][edge.B] = matrix[edge.A][edge.B];
        }
        System.out.println("最小生成树的邻接矩阵: ");
        for (int[] nums : treeMatrix) {
            System.out.println(Arrays.toString(nums));
        }
    }
    public static void main(String[] args) {
        Graph<String> graph = new Graph<>(6);
        graph.setDatas(new String[]{"A", "B", "C", "D", "E", "F"});
        // {端点索引, 端点索引, 权值}
        int[][] set = {{0, 1, 1},
                {0, 2, 3},
                {1, 3, 2},
                {1, 5, 2},
                {2, 3, 4},
                {2, 5, 7},
                {3, 4, 1},
                {4, 5, 8}};

        for (int i = 0; i < set.length; i++) {
            // graph.setMatrix(端点索引, 端点索引, 权值)
            graph.setMatrix(set[i][0], set[i][1], set[i][2]);
        }
        graph.setEdges();
        graph.KruskalTree();
    }
}

谢谢,第一次写文,不喜轻喷,狗头保命

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,591评论 6 501
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,448评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,823评论 0 353
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,204评论 1 292
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,228评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,190评论 1 299
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,078评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,923评论 0 274
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,334评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,550评论 2 333
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,727评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,428评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,022评论 3 326
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,672评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,826评论 1 269
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,734评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,619评论 2 354