开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> Java知识库 -> 蓝桥杯JAVA-23.最小生成树模板（JAVA实现） -> 正文阅读

[Java知识库]蓝桥杯JAVA-23.最小生成树模板（JAVA实现）

个人博客
www.tothefor.com
蓝桥杯复习知识点汇总

纸上得来终觉浅，绝知此事要躬行。路漫漫其修远兮，吾将上下而求索！知识是经过历史的巨人沉淀下来的，别总想着自己能够快速学会，多花点时间去看看，也许会发现些不同的东西。你能快速学会的、觉得简单的东西，对于别人来说也是一样的。人外有人，天外有天。当努力到达了一定的程度，幸运自会与你不期而遇。

import java.io.*;
import java.math.BigInteger;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 200000+7;
    public static int INF = 0x3f3f3f3f;
    public static int mod = (int) 1e9+7;
    public static int[] dis = new int[maxd];
    public static int[] head = new int[maxd];
    public static int[] edgePre = new int[maxd<<1]; //无向图，边需要开2倍
    public static int[] edgeW = new int[maxd<<1];
    public static int[] edgeTo = new int[maxd<<1];
    public static boolean[] vis = new boolean[maxd];
    public static int n;
    public static int node=0;

    public static void add_edge(int a,int b,int c){
        edgeTo[node] = b;
        edgeW[node] = c;
        edgePre[node] = head[a];
        head[a]=node++;
    }

    public static void init(int n){
        for(int i=0;i<=n;++i){
            dis[i]=INF;
            vis[i]=false;
            head[i] = -1;
        }
    }
    public static int Prim(){//默认找到的第一个为集合的首元素
        int res = 0;
        for(int i=1;i<=n;++i){
            int t = -1;
            for(int j=1;j<=n;++j){
                if(!vis[j] && (t==-1 || dis[t]>dis[j]))
                    t = j;
            }
            vis[t]=true;
            if(i!=1 && dis[t]==INF) return INF; //当前点与集合中的所有点都不连通，不存在最小生成树
            if(i!=1) res+=dis[t]; //首元素不需要加
            for(int j=head[t];j!=-1;j=edgePre[j]){
                int to = edgeTo[j];
                dis[to] = Math.min(dis[to],edgeW[j]);
            }
        }
        return res;
    }


    public static void main(String[] args) throws Exception {

        n = nextInt();
        int m = nextInt();
        init(n);
        while(m-->0){
            int a = nextInt();
            int b = nextInt();
            int c = nextInt();
            add_edge(a,b,c); //无向图
            add_edge(b,a,c);
        }
        int ans = Prim();
        cout.println(ans==INF? "orz":ans);
        cout.flush();
        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers(); //可单独使用来还原数字
    }

    public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }

}

堆优化Prim

时间复杂度 O(m*logⁿ)。

import java.io.*;
import java.math.BigInteger;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 200000+7;
    public static int INF = 0x3f3f3f3f;
    public static int mod = (int) 1e9+7;
    public static int[] dis = new int[maxd];
    public static int[] head = new int[maxd];
    public static int[] edgePre = new int[maxd<<1]; //无向图，边需要开2倍
    public static int[] edgeW = new int[maxd<<1];
    public static int[] edgeTo = new int[maxd<<1];
    public static boolean[] vis = new boolean[maxd];
    public static int n;
    public static int node=0;

    public static class Edge implements Comparable<Edge> {
        private int to; //点
        private int w; //此点到集合的最短距离
        Edge(int to, int w) {
            this.to = to;
            this.w = w;
        }
        public int compareTo(Edge obj) {
            return this.w - obj.w;
        }
    }

    public static void add_edge(int a,int b,int c){
        edgeTo[node] = b;
        edgeW[node] = c;
        edgePre[node] = head[a];
        head[a]=node++;
    }

    public static void init(int n){
        for(int i=0;i<=n;++i){
            dis[i]=INF;
            vis[i]=false;
            head[i] = -1;
        }
    }
    public static int Prim(){
        PriorityQueue<Edge> q = new PriorityQueue<Edge>();
        int res = 0;
        int cnt = 0; //记录集合中的点数,只有等于给定点数n时才存在最小生成树，小于n则表示图不连通
        q.add(new Edge(1,0));
        while(!q.isEmpty()){
            Edge u = q.poll();
            if(vis[u.to]) continue;
            vis[u.to] = true;
            res+=u.w;
            cnt++;
            for(int i=head[u.to];i!=-1;i=edgePre[i]){
                if(dis[u.to]>edgeW[i]){
                    q.add(new Edge(edgeTo[i],edgeW[i]));
                }
            }
        }
        if(cnt<n) return INF; //集合中的点数小于给定点数，表示图不连通
        return res;
    }

    public static void main(String[] args) throws Exception {

        n = nextInt();
        int m = nextInt();
        init(n);
        while(m-->0){
            int a = nextInt();
            int b = nextInt();
            int c = nextInt();
            add_edge(a,b,c); //无向图
            add_edge(b,a,c);
        }
        int ans = Prim();
        cout.println(ans==INF? "orz":ans);
        cout.flush();
        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers(); //可单独使用来还原数字
    }

    public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }

}

Kruskal

适用于稀疏图，时间复杂度 O(m*log^m)。

import java.io.*;
import java.math.BigInteger;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 200000+7;
    public static int INF = 0x3f3f3f3f;
    public static int mod = (int) 1e9+7;
    public static int[] par = new int[maxd]; //存储父节点
    public static int n;

    public static class Edge implements Comparable<Edge> {
        private int u; //起点
        private int v; //终点
        private int w; //边的权重
        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
        public int compareTo(Edge obj) {
            return this.w - obj.w;
        }
    }
    public static Edge[] edges = new Edge[maxd<<1]; //无向图，开两倍

    public static void init(int n,int m){
        for(int i=1;i<=n;++i){
            par[i] = i;
        }
    }
    public static int find(int x){
        if(x!=par[x]) par[x]=find(par[x]);
        return par[x];
    }
    public static void unite(int a,int b){
        int aa = find(a);
        int bb = find(b);
        if(aa!=bb) {
            par[aa]=bb;
        }
    }
    public static int Kruskal(int m){
        int res = 0; //结果
        int cnt = 0; //记录边
        Arrays.sort(edges,0,m);
        for(int i=0;i<m;++i){
            int u = edges[i].u;
            int v = edges[i].v;
            int w = edges[i].w;
            if(find(u)!=find(v)){
                unite(u,v); //合并
                res+=w;
                cnt++;
            }
        }
        if(cnt<n-1) return INF; //若少于n-1条边，则说明图不连通
        else return res;
    }

    public static void main(String[] args) throws Exception {

        n = nextInt();
        int m = nextInt();
        init(n,m);
        for(int i=0;i<m;++i){
            int a = nextInt();
            int b = nextInt();
            int c = nextInt();
            edges[i] = new Edge(a,b,c);
        }

        int ans = Kruskal(m);
        cout.println(ans==INF? "orz":ans);
        cout.flush();
        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers(); //可单独使用来还原数字
    }

    public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }

}