Minimum Spanning Tree
Minimum Spanning Tree
(Cây khung nhỏ nhất)
05/08/2019
I. Definition
- Tree: (Cây) là đồ thị vô hướng (undirected), liên thông (connected) và không có chu trình (acyclic).
Các tính chất của cây:- Cây n nodes luôn có n-1 cạnh
- Mỗi cạnh đều là cầu
- Thêm 1 cạnh bất kì sẽ tạo nên chu trình.
- Spanning Tree: (Cây khung) là Cây chứa tất cả các nodes, so nó luôn có n-1 cạnh.
Có thể tìm cây khung sử dụng bfs, dfs.
- Minimum Spanning Tree: Là cây khung có chi phí nhỏ nhất (tổng weight min), dĩ nhiên nó cũng phải có n-1 cạnh thôi.
- Maximum Spanning Tree có thể hoàn toàn sử dụng thuật toán minimum spanning tree bằng cách đổi dấu các cạnh.
II. Kruscal’s Algorithm
1. Ý tưởng:
Sắp xếp tất cả các cạnh theo thứ tự tăng của weight.
Lần lượt lấy các cạnh để cấu thành cây khung, nếu cạnh nào làm xuất hiện cycle thì bỏ qua đi tiếp đến khi đủ $n-1$ cạnh là được. (đủ $n-1$ cạnh có nghĩa là đã cover hết các nodes).
2. Why does this work?
Trực quan:
Cho đồ thị có $n$ nodes và có cây khung nhỏ nhất là $e_1, e_2, …, e_{n-1}$.
Giả sử có 1 cây khung $T$ khác mà không chứa 1 cạnh $e_i$ nào đó $(1\leq i \leq n-1)$ ở trên thì rõ ràng $T + e_i$ tạo ra cycle, từ cycle đó ta luôn có thể bỏ đi 1 cạnh $>$ $e_i$ và được cây khung nhỏ hơn. Nếu được loại 1 cạnh thì đương nhiên ta loại cạnh lớn nhất.
More Provement in cp-algorithms
3. Implementation
Ý tưởng cài đặt:
Ban đầu tất cả các đỉnh rời nhau. Lấy các cạnh theo thứ tự đã sort để giảm số CC (ban đầu có n CCs). Đến khi còn 1 CC thì dừng lại.
Cài đặt tầm thường:
$$\Rightarrow O(M\ log\ N + N^2)$$ ($M\ log\ N \approx M\ log\ M$)
1struct Edge {
2 int u, v, weight;
3 bool operator<(Edge const& other) {
4 return weight < other.weight;
5 }
6};
7
8int n;
9vector<Edge> edges;
10
11int cost = 0;
12vector<int> tree_id(n);
13vector<Edge> result;
14for (int i = 0; i < n; i++)
15 tree_id[i] = i;
16
17sort(edges.begin(), edges.end());
18
19for (Edge e : edges) {
20 if (tree_id[e.u] != tree_id[e.v]) {
21 cost += e.weight;
22 result.push_back(e);
23
24 int old_id = tree_id[e.u], new_id = tree_id[e.v];
25 for (int i = 0; i < n; i++) {
26 if (tree_id[i] == old_id)
27 tree_id[i] = new_id;
28 }
29 }
30}
Cài đặt dùng DSU (Disjoint Set Union)
$$\Rightarrow O(M\ log\ N + N + M) = O(M\ log\ N)$$
1vector<int> parent, rank;
2//parent: leader (representative)
3//rank: height of tree
4void make_set(int v) {
5 parent[v] = v;
6 rank[v] = 0;
7}
8
9int find_set(int v) {
10 if (v == parent[v])
11 return v;
12 return parent[v] = find_set(parent[v]);
13}
14
15void union_sets(int a, int b) {
16 a = find_set(a);
17 b = find_set(b);
18 if (a != b) {
19 if (rank[a] < rank[b])
20 swap(a, b);
21 parent[b] = a;
22 if (rank[a] == rank[b])
23 rank[a]++;
24 }
25}
26
27struct Edge {
28 int u, v, weight;
29 bool operator<(Edge const& other) {
30 return weight < other.weight;
31 }
32};
33
34int n;
35vector<Edge> edges;
36
37int cost = 0;
38vector<Edge> result;
39parent.resize(n);
40rank.resize(n);
41for (int i = 0; i < n; i++)
42 make_set(i);
43
44sort(edges.begin(), edges.end());
45
46for (Edge e : edges) {
47 if (find_set(e.u) != find_set(e.v)) {
48 cost += e.weight;
49 result.push_back(e);
50 union_sets(e.u, e.v);
51 }
52}
Có thể dùng $size[]$ thay cho $rank[]$, more information: cp-algorithms