一、Java实现Prim算法求最小生成树(邻接表)

解题思路：

• 1、首先通过链式前向星建立图，因为是无向图，所以需要建立2遍
• 2、通过邻接表建立图的时候，默认已经选择最短路建立，因为不用特殊处理重边/以及自环，只有使用邻接矩阵建图才会特殊处理权重
• 3、prim算法的模板和dijkstra和类似，区别如下:
  • dijkstra在遍历t的所有出边，进行松弛操作的时候是dist[j] = Math.min(dist[j], dist[t] + w[i]);需要累加下dist[t]
  • prim算法，只需要当前dist[j] = Math.min(dist[j], w[i]);也就是遍历t的所有出边，只需要和t出边的权重对比取最小的就行。
• 5、在进行t的所有出边遍历，进行松弛操作之前，需要先判断下dist[t]的距离是否为不可达INF，则表示没有最小生成树

import java.util.*;

public class Main {
    private static int N = 510;
    private static int M = 100010;
    private static int[] e = new int[2 * M]; // 因为是无向图
    private static int[] w = new int[2 * M];
    private static int[] ne = new int[2 * M];
    private static int[] h = new int[N];
    private static int idx = 0;

    private static void add(int a, int b, int c) { // a->b的边，权重为c
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    private static int[] dist = new int[N]; // dist[x] = y，表示起点到x的最短距离是y
    private static boolean[] st = new boolean[N];
    private static int INF = 0x3f3f3f3f;
    private static int prim(int start, int n) {
        int ans = 0; // 存储最小生成树的所有权重之和
        Arrays.fill(st, false);
        Arrays.fill(dist, INF);
        dist[start] = 0; // 起点到自己的距离是0
        for (int p = 0; p < n; p++) {
            int t = -1;
            for (int i = 1; i <= n; i++) { // 从1-n节点找出未被访问过，距离短的点
                if (!st[i] && (t == -1 || dist[t] > dist[i])) {
                    t = i;
                }
            }
            st[t] = true;
            if (dist[t] > INF / 2) { // 先判断，如果发现1-t的最短距离已经大于INF/2，则说明不存在最小生成树，直接返回INF就行
                return INF;
            }
            ans += dist[t]; // 累加最小生成树过程中保存的距离
            for (int i = h[t]; i != -1; i = ne[i]) { // 遍历访问t的所有出边
                int j = e[i];
                dist[j] = Math.min(dist[j], w[i]); // 此处和dijkstra的区别是，直接和t的出边权重比较获取最小的，而不是进行松弛操作，并没有累加dist[t]
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Arrays.fill(h, -1);
        while (m-- > 0) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            add(u, v, w); // 无向图所以建立2次边
            add(v, u, w);
        }
        int ans = prim(1, n); // 我们假设从起点1开始
        String res = ans > INF / 2 ? "impossible" : ans + "";
        System.out.println(res);
        sc.close();
    }
}

二、Java实现prim算法求最小生成树(邻接矩阵)

解题思路：

• 1、因为是使用邻接矩阵来建立图，因此需要处理重边/自环，读取输入每次取最小的权重值就行，无向图需要建立2次
• 2、松弛操作同上，确定选取好t点后，需要先判断下dist[t]，如果不可达，则返回INF，然后在进行松弛操作，访问1-n号点，然后更新dist距离
• 3、更新距离使用dist[i] = Math.min(dist[i], g[t][i])，不用进行dist[t]累加

import java.util.*;

public class Main {
    private static int N = 510; // 邻接矩阵建图，只跟图点数有关，和边数无关
    private static int[][] g = new int[N][N];
    private static int INF = 0x3f3f3f3f;

    private static int[] dist = new int[N];
    private static boolean[] st = new boolean[N];
    private static int prim(int start, int n) {
        int ans = 0; // 存储最小生成树的边权之和
        Arrays.fill(dist, INF);
        Arrays.fill(st, false);
        dist[start] = 0; // 初始化起点到自己的距离是0
        for (int p = 0; p < n; p++) { 
            int t = -1;
            for (int i = 1; i <= n; i++) {
                if (!st[i] && (t == -1 || dist[t] > dist[i])) {
                    t = i;
                }
            }
            st[t] = true;
            if (dist[t] > INF / 2) return INF;
            ans += dist[t];
            for (int i = 1; i <= n; i++) {
                dist[i] = Math.min(dist[i], g[t][i]); // dist[i]，与t到i的权重比较
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) { // 初始化
                if (i == j) g[i][j] = 0;
                else g[i][j] = INF;
            }
        }
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            g[u][v] = Math.min(g[u][v], w); // 处理自环/重边
            g[v][u] = Math.min(g[v][u], w);
        }
        int ans = prim(1, n); // 假设起点从1开始，起点随便都行，只要不超过n
        String res = ans > INF / 2 ? "impossible" : ans + "";
        System.out.println(res);
        sc.close();
    }
}

三、Java实现prim算法求最小生成树(堆优化)

解题思路

• 1、核心的关键是利用小根堆，然后还需要统计生成最小生成树的时候统计节点
• 2、特判如果最小生成树的节点数不是图的节点数n，则说明没有最小生成树
• 3、松弛操作类似

import java.util.*;

public class Main {
    private static int N = 510;
    private static int M = 100010;
    private static int[] e = new int[2 * M];
    private static int[] w = new int[2 * M];
    private static int[] ne = new int[2 * M];
    private static int[] h = new int[N];
    private static int idx = 0;

    private static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    private static int[] dist = new int[N];
    private static boolean[] st = new boolean[N];
    private static int INF = 0x3f3f3f3f;

    public static class Pair {
        int x; // 点
        int y; // 当点的最短距离
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    private static int prim(int start, int n) {
        int ans = 0; // 保存最小生成树的权重之和
        int cnt = 0; // 统计最小生成树经过的点数
        Arrays.fill(dist, INF);
        Arrays.fill(st, false);
        dist[start] = 0;
        PriorityQueue<Pair> heap = new PriorityQueue<>((a, b) -> a.y - b.y);
        heap.offer(new Pair(start, 0));
        while (!heap.isEmpty()) {
            var q = heap.poll();
            int t = q.x;
            int d = q.y; // 最短距离也就是dist[t]
            if (st[t]) continue;
            st[t] = true;
            ans += d; // 累加最小生成树权重之和
            cnt++; // 累加最小生成树的点数
            for (int i = h[t]; i != -1; i = ne[i]) { // 遍历访问t的所有出边
                int j = e[i];
                if (dist[j] > w[i]) { // 松弛操作，当前dist[j]与t的出边的权重比较大小
                    dist[j] = w[i];
                    heap.offer(new Pair(j, dist[j]));
                }
            }
        }
        if (cnt != n) return INF; // 最小生成树的点数一定等于图中的点数
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Arrays.fill(h, -1);
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            add(u, v, w); // 无向图，需要建立2条边
            add(v, u, w);
        }
        int ans = prim(1, n); // 假设起点从1开始
        String res = ans > INF / 2 ? "impossible" : ans + "";
        System.out.println(res);
        sc.close();
    }
}