数据结构与算法(35): 图- 最小生成树Kruskal

发表于   |   分类于

最小生成树：在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通图的最小生成树。

  Kruskal算法基本思想：首先按照边的权值进行从小到大排序，每次从剩余的边中选择权值较小的且边的两个顶点不在同一个集合内的边（就是不会产生回路），加入到生成树中，直到加入了n-1条边为止。
  判断两个顶点是否已连通可以利用深度优先或广度优先搜索，但是效率低，可以采用并查集来解决。
  Kruskal算法中，对边进行快速排序的复杂度是$O(E\log{E})$，在E条边中找出V-1条边的复杂度是$O(E\log{V})$，所以Kruskal算法的复杂度是$O(E\log{(E+V)})$。通常边数E大于顶点数V，最终时间复杂度为$O(E\log{E})$。

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
public class Kruskal {
    private static void quicksort(List<Edge> a, int low, int high) {
        if (low >= high) return;
        int i = low;
        int j = high;
        Edge tmp = a.get(low);
        while (i != j) {
            // 顺序很重要, 先从右往左找
            while (a.get(j).compareTo(tmp) >= 0 && i < j) {
                j--;
            }
            // 再从左往右找
            while (a.get(i).compareTo(tmp) <= 0 && i < j) {
                i++;
            }
            // 交换两个数在数组中的位置
            if (i < j) {
                Edge t = a.get(i);
                a.set(i, a.get(j));
                a.set(j, t);
            }
        }
        // 基准数归位
        a.set(low, a.get(i));
        a.set(i, tmp);
        quicksort(a, low, i - 1);
        quicksort(a, i + 1, high);
    }
    private static class Edge implements Comparable<Edge> {
        private int v1;
        private int v2;
        private int weight;
        public Edge(int v1, int v2, int weight) {
            this.v1 = v1;
            this.v2 = v2;
            this.weight = weight;
        }
        @Override
        public int compareTo(Edge o) {
            return weight - o.weight;
        }
    }
    public static void main(String[] args) {
        int vlen = 6;
        int elen = 9;
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(1, 3, 11));
        edges.add(new Edge(2, 4, 13));
        edges.add(new Edge(3, 5, 3));
        edges.add(new Edge(4, 5, 4));
        edges.add(new Edge(1, 2, 6));
        edges.add(new Edge(3, 4, 7));
        edges.add(new Edge(0, 1, 1));
        edges.add(new Edge(2, 3, 9));
        edges.add(new Edge(0, 2, 2));
        // 对边进行快排
        quicksort(edges, 0, edges.size() - 1);
        for (Edge edge: edges){
            System.out.println(edge.weight);
        }
        // 最小生成树的边数
        int count = 0;
        // 最小生成树的权重和
        int sum = 0;
        DisjointSet disjointSet = new DisjointSet(vlen);
        // Kruskal算法核心
        for (int i = 0; i < elen; i++){
            // 判断顶点v1, v2是否尚未连通
            if (disjointSet.union(edges.get(i).v1, edges.get(i).v2)){
                count++;
                sum += edges.get(i).weight;
            }
            if (count == vlen - 1){
                break;
            }
        }
        System.out.println("sum= " + sum);
    }
}