【笔记】数据结构与算法之最小生成树（Kruskal算法）

QingYi.

[Java] 纯文本查看 复制代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static class Edge{
        int a,b,w;
        public Edge(int a,int b, int w){
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }
    static int n,m;
    //总的边
    static int cnt = 0;
    static Edge[] edges;
    static int [] p;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] s = bf.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        edges = new Edge[m];
        p = new int[n+1];
        for(int i =1 ;i<=n;i++){
            p[i] = i;
        }
        for(int i = 0; i < m; i++){
            String[] res = bf.readLine().split(" ");
            int x = Integer.parseInt(res[0]);
            int y = Integer.parseInt(res[1]);
            int w = Integer.parseInt(res[2]);
            edges[i] = new Edge(x,y,w);
        }
        //权重从小到大排序
        Arrays.sort(edges,(a,b) -> a.w - b.w);
        //最小生成树权重之和
        int res =0;
        for (int i = 0; i < m; i++) {
            Edge e = edges[i];
            int x = find(e.a);
            int y = find(e.b);
            if (x!=y){
                res+=e.w;
                p[x] =y;
                cnt++;
            }
        }
        if(cnt<n-1){
            System.out.println("failed");
        }else {
            System.out.println(res);
        }
    }
    public static int find(int x){
        if (p[x] !=x){
            p[x] = find(p[x]);
        }
        return p[x];
    }
}

在新标签打开所有链接复制所有链接URL复制所有链接URL（反向）复制所有链接标题 + URL复制所有链接标题 + URL (MD)复制所有链接标题 + URL (BBS)复制所有链接标题 + URL (筛选)复制所有链接标题 + URL (设置复制格式)在新标签页打开所有图片链接在一个标签页显示所有图片链接
复选框 - 选中
复选框 - 取消
复选框 - 反选
单选框 - 选中
单选框 - 取消
特殊单选框 - 选中