Tác giả:
Reviewer:
Vương Hoàng Long - Đại học Quốc Gia Singapore
Vì bài viết nói về cây khung nhỏ nhất, các bạn nên đọc một số kiến thức liên quan đến cây trước mà mình liệt kê dưới đây vì đây là những kiến thức rất thường gặp trong những bài tập về cây khung, trong khuôn khổ bài viết mình sẽ không giải thích lại về những kiến thức này nữa:
Lưu ý: Toàn bộ phần code phía dưới sử dụng cho C++11
trở lên, các bạn lưu ý kiểm tra trình biên dịch của mình.
Theo lý thuyết đồ thị, chúng ta đều biết rằng 1 đồ thị được biểu diễn bằng công thức , trong đó đồ thị của chúng ta bao gồm tập các đỉnh và tập các cạnh .
Cây khung (spanning tree) của đồ thị là một tập hợp các cạnh của đồ thị thỏa mãn tập cạnh này không chứa chu trình và liên thông (từ một đỉnh bất kì có thể đi tới bất kỳ đỉnh nào khác theo mà chỉ dùng các cạnh trên cây khung)
Trong đồ thị có trọng số, cây khung nhỏ nhất (minimum spanning tree) là cây khung có tổng trọng số các cạnh trong cây nhỏ nhất.
Một ví dụ về cây khung trong đồ thị vô hướng không trọng số:
Trong khuôn khổ bài viết, chúng ta sẽ làm việc với đồ thị vô hướng có trọng số.
Một vài tính chất của cây khung nhỏ nhất trong đồ thị vô hướng có trọng số:
1. Tính chất chu trình: Trong một chu trình bất kỳ, nếu là cạnh có trọng số lớn nhất tuyệt đối (không có cạnh nào có trọng số bằng ) thì không thể nằm trên bất kỳ cây khung nhỏ nhất nào.
2. Đường đi hẹp nhất: Xét 2 đỉnh , bất kỳ trong đồ thị. Nếu là trọng số của cạnh lớn nhất trên đường đi từ đến trên cây khung nhỏ nhất của đồ thị thì ta không thể tìm được đường đi nào từ đến trên đồ thị ban đầu chỉ đi qua những cạnh có trọng số nhỏ hơn .
3. Tính duy nhất: Nếu tất cả các cạnh đều có trọng số khác nhau thì chỉ có duy một cây khung nhỏ nhất. Ngược lại, nếu một vài cạnh có trọng số giống nhau thì có thể có nhiều hơn một cây khung nhỏ nhất.
4. Tính chất cạnh nhỏ nhất: Nếu là cạnh có trọng số nhỏ nhất của đồ thị, và không có cạnh nào có trọng số bằng thì nằm trong mọi cây khung nhỏ nhất của đồ thị.
Lưu ý : các bạn mới học cây khung lần đầu cân nhắc việc đọc chứng minh, tác giả khuyên các bạn nên tạm thời bỏ qua phần này
Xuyên suốt cả bốn tính chất, ta đều sử dụng phép phản chứng để chứng minh
1. Tính chất chu trình:
Giả sử thuộc một cây khung của đồ thị, ta sẽ chứng minh luôn tồn tại một cây khung khác của đồ thị có trọng số nhỏ hơn .
2. Đường đi hẹp nhất:
3. Tính duy nhất:
4. Tính chất cạnh nhỏ nhất:
Ta sẽ chứng minh mọi cây khung không chứa của đồ thị đều không phải là cây khung nhỏ nhất.
Ý tưởng thuật toán: Ban đầu mỗi đỉnh là một cây riêng biệt, ta tìm cây khung nhỏ nhất bằng cách duyệt các cạnh theo trọng số từ nhỏ đến lớn, rồi hợp nhất các cây lại với nhau.
Cụ thể hơn, giả sử cạnh đang xét nối 2 đỉnh và , nếu 2 đỉnh này nằm ở 2 cây khác nhau thì ta thêm cạnh này vào cây khung, đồng thời hợp nhất 2 cây chứa và .
Giả sử ta cần tìm cây khung nhỏ nhất của đồ thị . Thuật toán bao gồm các bước sau:
Khi thuật toán kết thúc, rừng chỉ gồm đúng một cây và đó là một cây khung nhỏ nhất của đồ thị
Ví dụ các bước giải bài toán tìm cây khung nhỏ nhất với thuật toán Kruskal :
Để thực hiện thao tác kiểm tra cạnh và hợp nhất 2 cây một cách nhanh chóng, ta sử dụng cấu trúc Disjoint Set, dưới đây là đoạn code dùng để cài đặt thuật toán:
/*input
4 4
1 2 1
2 3 2
3 4 3
4 1 4
*/
#include <bits/stdc++.h>
using namespace std;
// Cấu trúc để lưu các cạnh đồ thị
// u, v là 2 đỉnh, c là trọng số cạnh
struct Edge {
int u, v, c;
Edge(int _u, int _v, int _c): u(_u), v(_v), c(_c) {};
};
struct Dsu {
vector<int> par;
void init(int n) {
par.resize(n + 5, 0);
for (int i = 1; i <= n; i++) par[i] = i;
}
int find(int u) {
if (par[u] == u) return u;
return par[u] = find(par[u]);
}
bool join(int u, int v) {
u = find(u); v = find(v);
if (u == v) return false;
par[v] = u;
return true;
}
} dsu;
// n và m là số đỉnh và số cạnh
// totalWeight là tổng trọng số các cạnh trong cây khung nhỏ nhất
int n, m, totalWeight = 0;
vector < Edge > edges;
int main() {
// Fast IO
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, c;
cin >> u >> v >> c;
edges.push_back({u, v, c});
}
dsu.init(n);
// Sắp xếp lại các cạnh theo trọng số tăng dần
sort(edges.begin(), edges.end(), [](Edge & x, Edge & y) {
return x.c < y.c;
});
// Duyệt qua các cạnh theo thứ tự đã sắp xếp
for (auto e : edges) {
// Nếu không hợp nhất được 2 đỉnh u và v thì bỏ qua
if (!dsu.join(e.u, e.v)) continue;
// Nếu hợp nhất được u, v ta thêm trọng số cạnh vào kết quả
totalWeight += e.c;
}
// Xuất ra kết quả
cout << totalWeight << '\n';
}
Ta phải chứng minh hai điều:
Chứng minh (1)
Chứng minh (2)
Lưu ý : Nếu bạn mới học cây khung lần đầu tiên chưa nên đọc ngay chứng minh này, vì chúng có thể khiến bạn hoang mang. Chứng minh có sử dụng một số khái niệm như lát cắt, lát cắt hẹp nhất
Trong chứng minh này, mình có quy ước sử dụng một số kí hiệu:
Giờ cùng đi vào chi tiết chứng minh nhé (づ◔ ͜ʖ◔)づ
Gọi là cây khung đầu ra của thuật toán Kruskal và là một cây khung nhỏ nhất, ta sẽ chứng minh tổng trọng số trên và bằng nhau : =
Nếu = ⇒ hiển nhiên đúng
Nếu ≠ gọi là cạnh mà hay thuộc . Gọi là thành phần liên thông chứa u tại thời điểm được thêm vào .
Nhận xét:
Dễ thấy nếu xóa cạnh trên thì sẽ tách thành 2 thành phần liên thông và .
Đây là một lát cắt, ta có thể thêm bất cứ cạnh nào nối giữa 2 thành phần liên thông này để tạo thành một cây mới ⇒ lát cắt .
Định nghĩa : Một lát cắt - là một tập con của 𝐸 mà khi loại bỏ những cạnh này thì không còn đường đi từ tới . (Bài toán lát cắt hẹp nhất)
Ta sẽ chứng minh thuộc lát cắt nhỏ nhất
Đánh giá độ phức tạp thuật toán:
Gọi là số đỉnh, là số cạnh của đồ thị
Thuật toán gồm 2 phần:
độ phức tạp của thuật toán Kruskal là
Ý tưởng thuật toán: Ý tưởng của thuật toán Prim rất giống với ý tưởng của thuật toán Dijkstra (tìm đường đi ngắn nhất trên đồ thị).
Nếu như thuật toán Kruskal xây dựng cây khung nhỏ nhất bằng cách kết nạp từng cạnh vào đồ thị thì thuật toán Prim lại kết nạp từng đỉnh vào đồ thị theo tiêu chí: đỉnh được nạp vào tiếp theo phải chưa được nạp và gần nhất với các đỉnh đã được nạp vào đồ thị.
Thuật toán bao gồm các bước sau:
Mặc dù không bắt buộc, các bạn có thể đọc chứng minh tính đúng đắn thuật toán của Wikipedia tại đây.
Khi hoàn thành xong bước trên, ta thu được cây khung nhỏ nhất của đồ thị gồm đỉnh và cạnh.
Ví dụ các bước giải bài toán tìm cây khung nhỏ nhất với thuật toán Prim:
Đoạn code sử dụng để cài đặt thuật toán Prim:
/*input
4 4
1 2 1
2 3 2
3 4 3
4 1 4
*/
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
const int N = 1e5 + 5;
const int INF = 1e9;
// khai báo đồ thị. g[u] chứa các cạnh nối với đỉnh u. Các cạnh sẽ được lưu dưới dạng pair<v,c>
int n, m;
vector <pair<int, int>> g[N];
int dis[N]; // mảng d lưu khoảng cách của toàn bộ đỉnh
int prim(int s) { // thuật toán Prim bắt đầu chạy từ đỉnh nguồn s
int ret = 0;
// Sử dụng priority_queue lưu khoảng cách của các đỉnh tăng dần đối với cây khung
// Vì priority_queue.top luôn là phần tử lớn nhất, ta sẽ phải sử dụng greater<pair<int,int>>
// để priority_queue.top là phần tử nhỏ nhất
// các phần tử lưu trong priority queue sẽ có dạng pair<dis[u],u>
priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
// khởi tạo khoảng cách của các đỉnh là vô cùng lớn
for (int i = 1; i <= n; i++) dis[i] = INF;
// khởi tạo đỉnh nguồn có khoảng cách là 0 và push đỉnh này vào
dis[s] = 0;
q.push({0, s});
while (!q.empty()) {
// lấy đỉnh có khoảng cách nhỏ nhất chưa được kết nạp
auto top = q.top(); q.pop();
int curDis = top.fi; int u = top.se;
if (curDis != dis[u]) continue;
// kết nạp đỉnh u vào cây khung
ret += dis[u]; dis[u] = -INF;
// cập nhất khoảng cách cho các đỉnh kề u
for (auto &e : g[u]) {
int v = e.fi; int c = e.se;
if (dis[v] > c) {
dis[v] = c;
q.push({ dis[v], v});
}
}
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, c;
cin >> u >> v >> c;
g[u].push_back({v, c});
g[v].push_back({u, c});
}
cout << prim(1) << '\n';
}
Đánh giá độ phức tạp thuật toán:
Fact: Trong các bài toán tìm cây khung, phần lớn mọi người sẽ sử dụng thuật toán Kruskal do tính dễ cài đặt cũng như dễ hiểu của nó.
Bonus : Các bạn có thể sử dụng Visualgo để mô phỏng thuật toán Kruskal và Prim thông qua hoạt ảnh, qua đó hiểu thêm về các thuật toán trên
1 thành phố gồm trọng điểm, tuyến đường có thể được xây dựng với chi phí xây dựng khác nhau. Yêu cầu chọn ra một số tuyến đường sao cho trọng điểm phải được liên thông với nhau và chi phí xây dựng tuyến đường lớn nhất là nhỏ nhất có thể.
Dựa vào tính chất đường đi hẹp nhất của cây khung mà ta đã trình bày ở trên, đường đi giữa 2 đỉnh , bất kỳ trên cây khung nhỏ nhất là đường đi có cạnh lớn nhất là nhỏ nhất của đồ thị.
Như vậy việc chọn ra các tuyến đường để xây dựng chỉ đơn giản là chọn các cạnh trên cây khung nhỏ nhất của đồ thị.
Chính là độ phức tạp của thuật toán tìm cây khung nhỏ nhất mà các bạn sẽ cài đặt.
Ở đây ta sẽ dùng Kruskal để tìm cây khung nhỏ nhất
/*input
4 4
1 2 1
2 3 2
3 4 3
4 1 4
*/
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u, v, c;
Edge(int _u, int _v, int _c): u(_u), v(_v), c(_c) {};
};
struct Dsu {
vector<int> par;
void init(int n) {
par.resize(n + 5, 0);
for (int i = 1; i <= n; i++) par[i] = i;
}
int find(int u) {
if (par[u] == u) return u;
return par[u] = find(par[u]);
}
bool join(int u, int v) {
u = find(u); v = find(v);
if (u == v) return false;
par[v] = u;
return true;
}
} dsu;
int n, m, maxWeight = 0;
vector < Edge > edges;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, c;
cin >> u >> v >> c;
edges.push_back({u, v, c});
}
dsu.init(n);
sort(edges.begin(), edges.end(), [](Edge & x, Edge & y) {
return x.c < y.c;
});
for (auto e : edges) {
if (!dsu.join(e.u, e.v)) continue;
maxWeight = max(maxWeight, e.c);
}
cout << maxWeight << '\n';
}
Cho đồ thị vô hướng gồm đỉnh và cạnh. Yêu cầu với mỗi cạnh trong đồ thị, tìm cây khung nhỏ nhất chứa cạnh đó của đồ thị và in ra trọng số của cây khung đó.
Đây là 1 bài tập khá kinh điển về cây khung nhỏ nhất. Để giải được bài tập này, chúng ta cần giải bài LUBENICA trước. Các bạn có thể đọc thêm về bài ở đây
/*input
8 10
8 7 11
3 5 23
2 1 23
7 2 13
6 4 18
1 4 20
8 4 17
2 8 8
3 2 9
5 6 29
*/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define bit(x, k) (1ll&(x >> k))
using ll = long long;
const int N = 2e5 + 5;
const ll INF = 1e18;
struct Edge {
int u, v, c, id;
Edge(int _u, int _v, int _c, int _id): u(_u), v(_v), c(_c), id(_id) {};
};
struct Data {
int par; ll maxc = -INF;
};
struct Dsu {
vector<int> par;
void init(int n) {
par.resize(n + 5, 0);
for (int i = 1; i <= n; i++) par[i] = i;
}
int find(int u) {
if (par[u] == u) return u;
return par[u] = find(par[u]);
}
bool join(int u, int v) {
u = find(u); v = find(v);
if (u == v) return false;
par[v] = u;
return true;
}
} dsu;
int n, m; ll mstWeight = 0;
int h[N]; ll res[N];
vector <Edge> edges;
vector <pair <int, int>> g[N];
Data up[N][21];
void dfs(int u, int p) {
up[u][0].par = p;
for (auto &e : g[u]) {
int v = e.fi; int c = e.se;
if (v == p) continue;
h[v] = h[u] + 1;
up[v][0].maxc = c;
dfs(v, u);
}
}
// tìm cạnh có trọng số lớn nhất trên đường đi u, v như bài LUBENICA
ll lca(int u, int v) {
ll ret = -INF;
if (h[u] < h[v]) swap(u, v);
int depth = h[u] - h[v];
for (int i = 0; i <= 20; i++) {
if (bit(depth, i)) {
ret = max(ret, up[u][i].maxc);
u = up[u][i].par;
}
}
if (u == v) return ret;
for (int i = 20; i >= 0; i--) {
if (up[u][i].par != up[v][i].par) {
ret = max({ret, up[u][i].maxc, up[v][i].maxc});
u = up[u][i].par; v = up[v][i].par;
}
}
ret = max({ret, up[u][0].maxc, up[v][0].maxc});
return ret;
}
void buildMST() {
dsu.init(n);
sort(edges.begin(), edges.end(), [](Edge & x, Edge & y) {
return x.c < y.c;
});
for (auto &e : edges) {
if (!dsu.join(e.u, e.v)) continue;
g[e.u].push_back({e.v, e.c});
g[e.v].push_back({e.u, e.c});
res[e.id] = -1; // đánh dấu là cạnh này thuộc cây khung nhỏ nhất
mstWeight += e.c;
}
}
void buildLCA() {
dfs(1, 1);
for (int i = 1; i <= 20; i++) {
for (int u = 1; u <= n; u++) {
up[u][i].par = up[up[u][i - 1].par][i - 1].par;
up[u][i].maxc = max(up[u][i - 1].maxc, up[up[u][i - 1].par][i - 1].maxc);
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, c;
cin >> u >> v >> c;
edges.push_back({u, v, c, i});
}
// dựng cây khung nhỏ nhất
buildMST();
// dựng LCA
buildLCA();
// tìm cây khung nhỏ nhất cho từng cạnh
for (auto &e : edges) {
if (res[e.id] == -1) res[e.id] = mstWeight;
else res[e.id] = mstWeight - lca(e.u, e.v) + e.c;
}
// in ra kết quả
for (int i = 1; i <= m; i++) cout << res[i] << "\n";
return 0;
}
Cho đồ thị vô hướng có trọng số gồm đỉnh và cạnh. Yêu cầu với mỗi cạnh trong đồ thị, kiểm tra xem cạnh đó không thuộc bất kỳ cây khung nhỏ nhất nào, thuộc một số cây khung nhỏ nhất hay nằm trong mọi cây khung nhỏ nhất của đồ thị.
/*input
4 5
1 2 101
1 3 100
2 3 2
2 4 2
3 4 1
*/
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
const int N = 1e5 + 5;
enum EdgeType {
NONE, // không cây nào chứa
ANY, // tất cả các cây đều chứa
ATL // ít nhất 1 cây chứa
};
struct Edge {
int u, v, c, id;
Edge(int _u, int _v, int _c, int _id): u(_u), v(_v), c(_c), id(_id) {};
};
struct Dsu {
vector<int> par;
void init(int n) {
par.resize(n + 5, 0);
for (int i = 1; i <= n; i++) par[i] = i;
}
int find(int u) {
if (par[u] == u) return u;
return par[u] = find(par[u]);
}
bool join(int u, int v) {
u = find(u); v = find(v);
if (u == v) return false;
par[v] = u;
return true;
}
} dsu;
vector <pair<int, int>> g[N];
int low[N], num[N], Time = 0;
int n, m;
EdgeType res[N];
vector <Edge> edges;
void dfs(int u, int idx) {
num[u] = low[u] = ++Time;
for (auto &e : g[u]) {
int v = e.fi; int id = e.se;
if (id == idx) continue;
if (num[v] == 0) {
dfs(v, id);
low[u] = min(low[u], low[v]);
if (low[v] == num[v]) {
// nếu cạnh là cầu thì mọi cây đều phải chứa
res[id] = EdgeType::ANY;
}
}
else {
low[u] = min(low[u], num[v]);
}
}
}
void solve(vector<Edge> &pen) { // xử lý các nhóm cạnh có cùng trọng số
if (pen.empty()) return;
// khởi tạo đồ thị nối các thành phần liên thông
for (int i = 0; i < pen.size(); i++) {
// sử dụng đỉnh cha trong dsu làm đỉnh đại diện cho thành phần liên thông
pen[i].u = dsu.find(pen[i].u); pen[i].v = dsu.find(pen[i].v);
g[pen[i].u].clear(); g[pen[i].v].clear();
num[pen[i].u] = num[pen[i].v] = 0;
}
for (auto e : pen) {
if (e.u == e.v) {
// nếu 2 đỉnh cùng thuộc 1 thành phần liên thông
res[e.id] = EdgeType::NONE;
}
else {
// nếu 2 đỉnh nối 2 thành phần liên thông khác nhau lại với nhau
res[e.id] = EdgeType::ATL;
// thêm cạnh vào đồ thị
g[e.v].push_back({e.u, e.id});
g[e.u].push_back({e.v, e.id});
}
}
// tìm cạnh cầu
for (auto &e : pen) if (num[e.u] == 0) dfs(e.u, -1);
// sau khi hoàn thành, ta thực hiện hợp các cạnh vào cây khung
for (auto &e : pen) dsu.join(e.u, e.v);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, c;
cin >> u >> v >> c;
edges.push_back({u, v, c, i});
}
dsu.init(n);
sort(edges.begin(), edges.end(), [](Edge x, Edge y) {
return x.c < y.c;
});
vector<Edge> pen;
for (auto &e : edges) {
if (!pen.empty() && pen.back().c == e.c) {
pen.push_back(e);
}
else {
solve(pen);
pen = {e};
}
}
solve(pen);
// in ra kết quả
for (int i = 1; i <= m; i++) {
if (res[i] == EdgeType::NONE) cout << "none\n";
else if (res[i] == EdgeType::ANY) cout << "any\n";
else cout << "at least one\n";
}
}
Các bạn có thể thử sức với một số bài tập sau: