java kruskal怎么实现最小生成树

这篇文章主要讲解了"java kruskal怎么实现最小生成树"，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习"java kruskal怎么实现最小生成树"吧！

话不多说了，看代码：

import java.util.ArrayList;import java.util.Collections;import java.util.Scanner;/**P1861 Network D题 - 最小生成树： kruskal4 61 2 11 3 11 4 22 3 13 4 12 4 1141 21 32 33 4 * @author 姚林涛 * */public class Main {                static int N,M;         static int[] SET; //并查集数组        static ArrayList lines; //图存储，边集存储        static boolean[] visited; //访问标记        static int maxLine ;//最大距离                public static void main(String[] args) {                Scanner sc = new Scanner(System.in);                //接收参数                N = sc.nextInt();                M = sc.nextInt();                maxLine = 0;                SET = new int[N+1];                visited = new boolean[M];                lines = new ArrayList();                for (int i = 0; i < M; i++) {                        int s = sc.nextInt();                        int e = sc.nextInt();                        int v = sc.nextInt();                        new Line(s,e,v);                        lines.add(new Line(s,e,v));                }                //排序                Collections.sort(lines);                //查并集                init();                for (int i = 0; i < lines.size(); i++) {                        if(!isConntect(lines.get(i).s,lines.get(i).e)) {                                union(lines.get(i).s,lines.get(i).e);                                maxLine = lines.get(i).v; // 最后一次肯定是最大长度                                visited[i] = true;                        }                }                //计算个数                int count = N-1;                System.out.println(maxLine);                System.out.println(count);                for (int i = 0; i < lines.size(); i++) {                        if(visited[i]) {                                System.out.println(lines.get(i).s+" "+lines.get(i).e);                           }                }                sc.close();        }        /**         *   将  b的根节点，指向a的根节点         * @param a         * @param b         */        private static void union(int a, int b) {                int tempA = SET[a];                int tempB = SET[b];                if(tempA!=tempB) {                        SET[tempB] = tempA;                }        }        /**         * a,b 是否连接         * @param a         * @param b         * @return         */        private static boolean isConntect(int a, int b) {                return find(a)==find(b);        }        /**         *   返回 a 的根节点         * @param b         * @return         */        private static int find(int a) {                if(SET[a] == a) {                        return a;                }else {                        SET[a] = find(SET[a]);                        return SET[a];                 }        }        /**         *  并查集 初始化         */        private static void init() {                for (int i = 1; i < SET.length; i++) {                        SET[i] = i;                }        }                static class Line implements Comparable{                public int s;                public int e;                public int v;                                                public Line(int s, int e, int v) {                        this.s = s;                        this.e = e;                        this.v = v;                }                @Override                public int compareTo(Line o) {                        if(this.v != o.v) {                                return this.v - o.v;                         }else {                                return this.s - o.s;                        }                }                        }}

感谢各位的阅读，以上就是"java kruskal怎么实现最小生成树"的内容了，经过本文的学习后，相信大家对java kruskal怎么实现最小生成树这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是，小编将为大家推送更多相关知识点的文章，欢迎关注！