わたしの部屋

1
import java.util.*;
2

3
/** 一条带权边。Comparable 让 PriorityQueue 默认按权值排序。 */
4
class Edge implements Comparable<Edge> {
5
    int from, to, weight;
6

7
    Edge(int from, int to, int weight) {
8
        this.from = from;
9
        this.to = to;
10
        this.weight = weight;
11
    }
12

13
    @Override
14
    public int compareTo(Edge other) {
15
        return Integer.compare(this.weight, other.weight);
16
    }
17

18
    @Override
19
    public String toString() {
20
        return "(" + from + "-" + to + ", w=" + weight + ")";
21
    }
22
}

1
public class PrimMST {
2

3
    private final List<List<Edge>> adj;   // 邻接表
4
    private final int n;                  // 顶点数
5

6
    public PrimMST(int n) {
7
        this.n = n;
8
        this.adj = new ArrayList<>();
9
        for (int i = 0; i < n; i++) {
10
            adj.add(new ArrayList<>());
11
        }
12
    }
13

14
    /** 添加一条无向边。 */
15
    public void addEdge(int u, int v, int w) {
16
        adj.get(u).add(new Edge(u, v, w));
17
        adj.get(v).add(new Edge(v, u, w));
18
    }
19

20
    /**
21
     * 从顶点 start 开始跑 Prim，返回 MST 的边集合。
22
     * 如果图不连通，返回的是最小生成森林。
23
     */
24
    public List<Edge> prim(int start) {
25
        List<Edge> mst = new ArrayList<>();          // 结果：MST 的边
26
        boolean[] inTree = new boolean[n];           // 顶点是否已在树内
27
        PriorityQueue<Edge> heap = new PriorityQueue<>();  // 跨切边最小堆
28

29
        // 1. 起点入树，它的邻接边全部入堆
30
        inTree[start] = true;
31
        visit(start, heap);
32

33
        // 2. 只要 MST 还没长全，就继续
34
        while (!heap.isEmpty() && mst.size() < n - 1) {
35
            Edge e = heap.poll();                    // 当前最小跨切边
36

37
            // 懒处理：两端都在树内 = 废边，跳过
38
            if (inTree[e.from] && inTree[e.to]) {
39
                continue;
40
            }
41

42
            // 由于前面已经排除了“两端都在树内”的情况，此时这条边必定是一端在树内、一端在树外。
43
            // 找出那个尚未加入生成树的顶点 w，将其并入树中。
44
            int w = inTree[e.from] ? e.to : e.from;
45
            inTree[w] = true;
46
            mst.add(e);
47
            visit(w, heap);                                // 新顶点的邻接边入堆
48
        }
49

50
        return mst;
51
    }
52

53
    /** 把顶点 v 的所有邻接边加入堆。 */
54
    private void visit(int v, PriorityQueue<Edge> heap) {
55
        for (Edge e : adj.get(v)) {
56
            // 将邻接边入堆
57
            heap.offer(e);
58
        }
59
    }
60
}

1
public static void main(String[] args) {
2
    PrimMST g = new PrimMST(6);
3
    // 第 4 节示例的图
4
    g.addEdge(0, 1, 7);   // A-B
5
    g.addEdge(0, 2, 8);   // A-C
6
    g.addEdge(1, 2, 3);   // B-C
7
    g.addEdge(1, 3, 6);   // B-D
8
    g.addEdge(2, 3, 4);   // C-D
9
    g.addEdge(2, 4, 3);   // C-E
10
    g.addEdge(3, 4, 2);   // D-E
11
    g.addEdge(3, 5, 5);   // D-F
12
    g.addEdge(4, 5, 2);   // E-F
13

14
    List<Edge> mst = g.prim(0);   // 从 A 开始
15

16
    System.out.println("MST 的边：");
17
    int total = 0;
18
    for (Edge e : mst) {
19
        System.out.println("  " + e);
20
        total += e.weight;
21
    }
22
    System.out.println("总权值：" + total);
23
}

1
MST 的边：
2
  (0-1, w=7)
3
  (1-2, w=3)
4
  (2-4, w=3)
5
  (4-3, w=2)
6
  (4-5, w=2)
7
总权值：17

1
public class MatrixPrim {
2
    private static final int INF = Integer.MAX_VALUE;
3

4
    /**
5
     * 基于邻接矩阵的 Prim 算法实现。
6
     * @param graph 邻接矩阵，graph[i][j] 表示顶点 i 到 j 的权值，不连通为 INF
7
     * @param n 顶点个数
8
     * @param start 起点
9
     */
10
    public static void prim(int[][] graph, int n, int start) {
11
        int[] lowcost = new int[n];
12
        int[] closest = new int[n];
13
        boolean[] inTree = new boolean[n];
14

15
        // 初始化
16
        for (int i = 0; i < n; i++) {
17
            lowcost[i] = graph[start][i];
18
            closest[i] = start;
19
        }
20
        inTree[start] = true;
21

22
        int totalWeight = 0;
23
        System.out.println("教材版 Prim MST 的边：");
24

25
        // 寻找剩余的 n - 1 个顶点
26
        for (int step = 1; step < n; step++) {
27
            int minCost = INF;
28
            int u = -1;
29

30
            // 1. 寻找当前连接代价最小的树外顶点
31
            for (int i = 0; i < n; i++) {
32
                if (!inTree[i] && lowcost[i] < minCost) {
33
                    minCost = lowcost[i];
34
                    u = i;
35
                }
36
            }
37

38
            if (u == -1) {
39
                System.out.println("图不连通，无法构造完整的 MST");
40
                return;
41
            }
42

43
            // 2. 并入树内并输出边
44
            inTree[u] = true;
45
            totalWeight += minCost;
46
            System.out.println("  (" + closest[u] + "-" + u + ", w=" + minCost + ")");
47

48
            // 3. 更新剩余树外顶点的最小连接代价
49
            for (int v = 0; v < n; v++) {
50
                if (!inTree[v] && graph[u][v] < lowcost[v]) {
51
                    lowcost[v] = graph[u][v];
52
                    closest[v] = u;
53
                }
54
            }
55
        }
56
        System.out.println("总权值：" + totalWeight);
57
    }
58
}