一、最小生成树算法

对于无向图来书：最小生成树算法主要有Prim 算法（P 算法）和 Kruskal 算法 （K算法）。两种算法都是采用贪心的思想进行树建立。

K 算法以边为建立依据，利用连通性与边的权值进行筛选。

P 算法以点为建立依据，不断通过增加点到树集合中。

二、Kruskal 算法

使用并查集结构快速判断是否连通、连通不同子树。

1584. 连接所有点的最小费用

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        UF uf = new UF(n);
        LinkedList<int[]> edges = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                int xi = points[i][0], yi = points[i][1];
                int xj = points[j][0], yj = points[j][1];
                edges.add(new int[]{i, j, Math.abs(xi-xj) + Math.abs(yi-yj)});
            }
        }
        Collections.sort(edges, (int[] a, int[] b) -> a[2] - b[2]);
        int res = 0;
        for (int[] edge : edges) {
            if (!uf.connected(edge[0], edge[1])) {
                uf.union(edge[0], edge[1]);
                res += edge[2];
            }
        }
        return res;
    }

    class UF {
        private int[] parents;
        private int[] size;
        private int count;

        public UF(int n) {
            parents = new int[n];
            size = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                parents[i] = i;
                size[i] = 1;
            }
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ)
                return;
            if (size[rootP] < size[rootQ]) {
                parents[rootP] = parents[rootQ];
                size[rootQ] += size[rootP];
            } else {
                parents[rootQ] = parents[rootP];
                size[rootP] += size[rootQ];
            }
            count--;
        }

        public int find(int x) {
            while (parents[x] != x) {
                parents[x] = parents[parents[x]];
                x = parents[x];
            }
            return x;
        }

        public boolean connected(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            return rootP == rootQ;
        }

        public int count() {
            return count;
        }
    }
}

三、Prim 算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public static class EdgeComparator implements Comparator<Edge> {
    
    @Override
    public int compare(Edge o1, Edge o2) {
        return o1.weight - o2.weight;
    }
}

public static Set<Edge> primMST (Graph graph) {
    PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
    HashSet<Node> set = new HashSet<>();
    Set<Edge> result = new HashSet<>();
    for (Node node : graph.nodes.values()) {
        if (!set.contains(node)) {
            set.add(node);
            for (Edge edge : node.edges) {
                priorityQueue.add(edge);
            }
            while (!priorityQueue.isEmpty()) {
                Edge edge = priorityQueue.poll();
                Node toNode = edge.to;
                if (!set.contains(toNode)) {
                    set.add(toNode);
                    result.add(edge);
                    for (Edge nextEdge : toNode.edges) {
                        priorityQueue.add(nextEdge);
                    }
                }
            }
        }
        return result;
    }
}