最小生成树之克鲁斯卡尔算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了最小生成树之克鲁斯卡尔算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2410字，纯文字阅读大概需要4分钟。

内容图文

算法思路

1. 准备：边类，图类；
2. 根据图的邻接矩阵获得边集合，并将边按照边的权值进行排序（升序）；
3. 依次取边集合中的边，如果取出来的这条边不和已经选择的边构成回路就添加这条边，否则取边集合中的下一条边。

Q：怎么判断新取的边和已经选取的边会不会构成回路？

A：引入一个数组，记录每个顶点的终点，如果新取的这条边的两端的终点相同，说明构成回路；否则不构成。

注：终点是指在最小生成树中与它连通的最大顶点。

代码实现

package com.ex.kruskal;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Kruskal{

    static final int INF=10000;

    //边
    static class Edge implements Comparable<Edge>{
        int p1;
        int p2;
        int weight;

        public Edge(int p1, int p2, int weight) {
            this.p1 = p1;
            this.p2 = p2;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return this.weight-o.weight;
        }

    }

    //图
    static class Graph{
        char[] nodes;
        int[][] matrix;
        List<Edge> edges;

        public Graph(char[] nodes, int[][] matrix) {
            this.nodes = nodes;
            this.matrix = matrix;
            generateEdges();
        }

        //生成边，并排序
        public void generateEdges(){
            edges=new ArrayList<>();
            for (int i = 0; i < nodes.length; i++) {
                for (int j = i+1; j < nodes.length; j++) {
                    if (matrix[i][j]!=INF) {
                        edges.add(new Edge(i,j,matrix[i][j]));
                    }
                }
            }
            Collections.sort(edges);
        }
    }

    //生成最小生成树
    public static void kruskal(Graph graph){
        //准备
        char[] nodes = graph.nodes;
        List<Edge> edges = graph.edges;
        int[][] matrix = graph.matrix;
        int[] ends=new int[nodes.length];
        //每次选择一个边，如果不构成回路就加入集合，否则下一条边
        for (int i = 0; i < edges.size(); i++) {
            Edge edge = edges.get(i);
            int end1 = getEnd(ends, edge.p1);
            int end2 = getEnd(ends, edge.p2);
            if (end1!=end2) {
                System.out.println(nodes[edge.p1]+"—>"+nodes[edge.p2]+"："+matrix[edge.p1][edge.p2]);
                ends[end1]=end2;
            }
        }
    }

    //获得某个顶点的终点
    private static int getEnd(int[] ends,int index){
       while (ends[index]!=0){
           index=ends[index];
       }
        return index;
    }

    public static void main(String[] args) {
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //克鲁斯卡尔算法的邻接矩阵  
        int matrix[][] = {
                 {   0,  12, INF, INF, INF,  16,  14},
                 {  12,   0,  10, INF, INF,   7, INF},
                 { INF,  10,   0,   3,   5,   6, INF},
                 { INF, INF,   3,   0,   4, INF, INF},
                 { INF, INF,   5,   4,   0,   2,   8},
                 {  16,   7,   6, INF,   2,   0,   9},
                 {  14, INF, INF, INF,   8,   9,   0}};
        //求最小生成树
        Graph graph = new Graph(vertexs, matrix);
        kruskal(graph);

    }



}

普里姆算法 VS 克鲁斯卡尔算法

　　　　　　　　　　　　　　　　　　　　　　　　　　n：结点数　　E：边数

算法名	普里姆算法	克鲁斯卡尔算法
时间复杂度	O(n2)	O(ElogE)
适用范围	稠密图 （n、E相当）	稀疏图 （E<<n）

内容总结

以上是互联网集市为您收集整理的最小生成树之克鲁斯卡尔算法全部内容，希望文章能够帮你解决最小生成树之克鲁斯卡尔算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---