最小生成树

最小生成树
prim 算法
kruskal 算法

最小生成树

题目

题目描述
在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。
不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将所有岛屿联通起来（注意：这是一个无向图）。
给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。
输入描述
第一行包含两个整数V 和 E，V代表顶点数，E代表边数。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。
接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和终点，val代表边的权值。
输出描述
输出联通所有岛屿的最小路径总距离
输入示例
1
2
3
4
5
6
7
8
9
10
11
12
7 11
1 2 1
1 3 1
1 5 2
2 6 1
2 4 2
2 3 2
3 4 1
4 5 1
5 6 2
5 7 1
6 7 1
输出示例
1
6
提示信息
数据范围：
2 <= V <= 10000;
1 <= E <= 100000;
0 <= val <= 10000;
如下图，可见将所有的顶点都访问一遍，总距离最低是6.

思路

prim算法(适用于稠密图)

prim 算法的核心思想是让一棵小树长成大树。

prim 算法核心就是三步，称为 prim三部曲，大家一定要熟悉这三步，代码相对会好些很多：
1. 选距离生成树的最近节点
2. 将最近节点加入生成树
3. 更新非生成树节点到生成树的距离（即更新 minDist 数组）
  - minDist 数组用来记录每一个未加入生成树的节点距离最小生成树的最近距离。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int V = in.nextInt();
        int E = in.nextInt();
        int[][] dist = new int[V + 1][V + 1];
        // minDist存储的是其他未连接点和当前图之间的最小距离
        int[] minDist = new int[V + 1];
        // 用Integer.MAX_VALUE表明两个岛屿之间不连通
        for (int i = 1; i <= V; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        Arrays.fill(minDist, Integer.MAX_VALUE);
        for (int i = 0; i < E; i++) {
            int v1 = in.nextInt();
            int v2 = in.nextInt();
            int val = in.nextInt();
            dist[v1][v2] = dist[v2][v1] = val;
        }
        int res = 0;
        // 表示已经有多少岛屿加入图中了
        int count = 0;
        // 先把第一个结点加入图中
        minDist[1] = 0;
        count++;
        for (int i = 2; i <= V; i++) {
            minDist[i] = dist[1][i];
        }
        while (count < V) {
            int k = 0; // 标记当前要把哪个岛屿加入图中
            int min = Integer.MAX_VALUE;
            for (int i = 1; i <= V; i++) {
                if (minDist[i] != 0 && minDist[i] < min) {
                    k = i;
                    min = minDist[i];
                }
            }
            if (k == 0) {
                // 表明岛屿之间并不都是连通的
                System.out.println(-1);
                return;
            }
            res += min;
            count++;
            minDist[k] = 0;
            // 更新minDist数组
            for (int i = 1; i <= V; i++) {
                if (dist[k][i] < minDist[i]) {
                    minDist[i] = dist[k][i];
                }
            }
        }
        System.out.println(res);
    }
}

kruskal算法(适用于稀疏图)

kruskal 算法的核心思想是将森林合并成树。

kruscal 的思路：
1. 先将边按权值排序，因为要优先选最小的边加入到生成树里。
2. 遍历排序后的边：
  - 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环，就舍弃这条边
  - 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合
  使用并查集来判断两个结点是否在同一个集合中。

import java.util.*;

class Edge {
    int start;
    int end;
    int val;
    public Edge() {}
    public Edge(int start, int end, int val) {
        this.start = start;
        this.end = end;
        this.val = val;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int V = in.nextInt();
        int E = in.nextInt();
        // 并查集数组
        int[] root = new int[V + 1];
        for (int i = 1; i <= V; i++) {
            root[i] = i; // 初始时根都是自己
        }
        int res = 0;
        // 将边从小到大排序
        Queue<Edge> queue = new PriorityQueue<>((e1, e2) -> e1.val - e2.val);
        for (int i = 0; i < E; i++) {
            int v1 = in.nextInt();
            int v2 = in.nextInt();
            int val = in.nextInt();
            queue.offer(new Edge(v1, v2, val));
        }
        while (!queue.isEmpty()) {
            Edge e = queue.poll();
            int root1 = find(root, e.start);
            int root2 = find(root, e.end);
            // 说明在同一个集合中
            if (root1 == root2) {
                continue;
            } else {
                root[root2] = root1; // 将两个集合合并
                res += e.val;
            }
        }
        System.out.println(res);
    }
    
    // 找到根结点，同时压缩路径
    public static int find(int[] root, int v) {
        if (root[v] == v) {
            return v;
        }
        return root[v] = find(root, root[v]);
    }
}

进阶(输出最小生成树的边)

原题是求联通所有岛屿的最小路径总距离，那如果要把这颗最小生成树画出来呢？

对于 prim 算法，可以用一个 parent 数组记录最小生成树中结点之间的关系，parent[当前岛屿] = 前一个岛屿。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int V = in.nextInt();
        int E = in.nextInt();
        int[][] dist = new int[V + 1][V + 1];
        // minDist存储的是其他未连接点和当前图之间的最小距离
        int[] minDist = new int[V + 1];
        // 记录最小生成树的样子
        int[] parent = new int[V + 1];
        // 用Integer.MAX_VALUE表明两个岛屿之间不连通
        for (int i = 1; i <= V; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        Arrays.fill(minDist, Integer.MAX_VALUE);
        for (int i = 0; i < E; i++) {
            int v1 = in.nextInt();
            int v2 = in.nextInt();
            int val = in.nextInt();
            dist[v1][v2] = dist[v2][v1] = val;
        }
        int res = 0;
        // 表示已经有多少岛屿加入图中了
        int count = 0;
        // 先把第一个结点加入图中
        minDist[1] = 0;
        count++;
        for (int i = 2; i <= V; i++) {
            minDist[i] = dist[1][i];
            if (minDist[i] != Integer.MAX_VALUE) {
                parent[i] = 1;
            }
        }
        while (count < V) {
            int k = 0; // 标记当前要把哪个岛屿加入图中
            int min = Integer.MAX_VALUE;
            for (int i = 1; i <= V; i++) {
                if (minDist[i] != 0 && minDist[i] < min) {
                    k = i;
                    min = minDist[i];
                }
            }
            if (k == 0) {
                // 表明岛屿之间并不都是连通的
                System.out.println(-1);
                return;
            }
            res += min;
            count++;
            minDist[k] = 0;
            // 更新minDist数组
            for (int i = 1; i <= V; i++) {
                if (dist[k][i] < minDist[i]) {
                    minDist[i] = dist[k][i];
                    parent[i] = k;
                }
            }
        }
        // 打印出最小生成树
        for (int i = 1; i <= V; i++) {
            System.out.println(parent[i] + "->" + i);
        }
        System.out.println(res);
    }
}

对于 kruskal 算法，直接对边进行操作即可。

import java.util.*;

class Edge {
    int start;
    int end;
    int val;
    public Edge() {}
    public Edge(int start, int end, int val) {
        this.start = start;
        this.end = end;
        this.val = val;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int V = in.nextInt();
        int E = in.nextInt();
        // 并查集数组
        int[] root = new int[V + 1];
        for (int i = 1; i <= V; i++) {
            root[i] = i; // 初始时根都是自己
        }
        int res = 0;
        // 将边从小到大排序
        Queue<Edge> queue = new PriorityQueue<>((e1, e2) -> e1.val - e2.val);
        // 存储最小生成树的边
        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i < E; i++) {
            int v1 = in.nextInt();
            int v2 = in.nextInt();
            int val = in.nextInt();
            queue.offer(new Edge(v1, v2, val));
        }
        while (!queue.isEmpty()) {
            Edge e = queue.poll();
            int root1 = find(root, e.start);
            int root2 = find(root, e.end);
            // 说明在同一个集合中
            if (root1 == root2) {
                continue;
            } else {
                edges.add(e);
                root[root2] = root1; // 将两个集合合并
                res += e.val;
            }
        }
        // 输出最小生成树
        for (Edge e : edges) {
            System.out.println(e.start + "->" + e.end);
        }
        System.out.println(res);
    }
    
    // 找到根结点，同时压缩路径
    public static int find(int[] root, int v) {
        if (root[v] == v) {
            return v;
        }
        return root[v] = find(root, root[v]);
    }
}