Chuyên đề đồ thị nâng cao

🌉 Cây bao trùm nhỏ nhất MST: Kruskal & Prim

Bài học này nâng cấp nội dung MST theo hướng trực quan: hiểu cây bao trùm, quan sát đồ thị có trọng số, chạy từng bước Kruskal bằng DSU và Prim bằng hàng đợi ưu tiên.

MSTn − 1 cạnh, không chu trình

KruskalSắp xếp cạnh + DSU

PrimMở rộng từ một đỉnh

Ứng dụngNetwork, road, clustering

Mục tiêu Lý thuyết Kruskal Prim Code So sánh Thực hành Lỗi Quiz

Mục tiêu bài học

Học xong cần làm được

Hiểu cây bao trùm nhỏ nhất MST.
Biết MST chỉ tồn tại đầy đủ khi đồ thị vô hướng có trọng số và liên thông.
Phân biệt Kruskal: chọn cạnh nhỏ nhất; Prim: mở rộng từ tập đỉnh đã chọn.
Viết được code Kruskal và Prim, biết kiểm tra đồ thị không liên thông.

Ví dụ đời sống

Nối các máy tính bằng dây mạng với chi phí nhỏ nhất.
Thiết kế đường đi nối các điểm dân cư nhưng tổng chi phí thấp nhất.
Chọn các kết nối rẻ nhất để toàn bộ hệ thống vẫn liên thông.

1. Lý thuyết MST cần nắm

Một cây bao trùm của đồ thị là tập cạnh nối tất cả các đỉnh, không tạo chu trình. Trong đồ thị có n đỉnh, một cây bao trùm luôn có đúng n - 1 cạnh. MST là cây bao trùm có tổng trọng số nhỏ nhất.

Đủ đỉnh

Phải nối được tất cả n đỉnh.

n − 1 cạnh

Cây bao trùm không thừa cạnh.

Không chu trình

Thêm cạnh tạo cycle thì bỏ.

Nhỏ nhất

Tổng trọng số là nhỏ nhất.

Lưu ý hiện đại: Nếu đồ thị không liên thông, không có MST đầy đủ. Khi đó có thể nói tới minimum spanning forest, tức cây bao trùm nhỏ nhất cho từng component.

2. Mô phỏng Kruskal: sắp xếp cạnh + DSU

Kruskal xét các cạnh từ nhỏ đến lớn. Mỗi cạnh chỉ được chọn nếu nối hai component khác nhau. Nếu hai đầu cạnh đã cùng component, chọn cạnh đó sẽ tạo chu trình nên phải bỏ.

Tổng = 0Cạnh chọn = 0

Danh sách cạnh đã sắp xếp

Nhấn “Bước tiếp” để chạy Kruskal.

3. Mô phỏng Prim: mở rộng từ một đỉnh

Prim bắt đầu từ một đỉnh, sau đó liên tục chọn cạnh nhỏ nhất nối từ tập đỉnh đã thăm ra một đỉnh chưa thăm. Cấu trúc thường dùng là priority_queue hoặc heap.

Tổng = 0Đỉnh đã thăm = 0

Cạnh ứng viên trong heap

Nhấn “Bước tiếp” để chạy Prim.

4. Code mẫu và giải thích

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v;
    long long w;
};

struct DSU {
    vector<int> parent, sz;

    DSU(int n) {
        parent.resize(n + 1);
        sz.assign(n + 1, 1);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]); // path compression
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;           // thêm cạnh sẽ tạo chu trình

        if (sz[a] < sz[b]) swap(a, b);      // cây nhỏ treo vào cây lớn
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<Edge> edges(m);
    for (auto &e : edges) cin >> e.u >> e.v >> e.w;

    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
        return a.w < b.w;
    });

    DSU dsu(n);
    long long total = 0;
    vector<Edge> mst;

    for (const Edge &e : edges) {
        if (dsu.unite(e.u, e.v)) {
            total += e.w;
            mst.push_back(e);
        }
    }

    if ((int)mst.size() != n - 1) {
        cout << "Do thi khong lien thong\n";
        return 0;
    }

    cout << "MST = " << total << '\n';
    for (auto e : mst) cout << e.u << ' ' << e.v << ' ' << e.w << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<pair<int,int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<bool> visited(n + 1, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

    pq.push({0, 1}); // {trọng số cạnh, đỉnh}
    long long total = 0;
    int cnt = 0;

    while (!pq.empty()) {
        auto [w, u] = pq.top();
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;
        total += w;
        cnt++;

        for (auto [v, ww] : adj[u]) {
            if (!visited[v]) pq.push({ww, v});
        }
    }

    if (cnt != n) {
        cout << "Do thi khong lien thong\n";
    } else {
        cout << "MST = " << total;
    }
    return 0;
}

import heapq

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]

for _ in range(m):
    u, v, w = map(int, input().split())
    adj[u].append((w, v))
    adj[v].append((w, u))

visited = [False] * (n + 1)
pq = [(0, 1)]
total = 0
cnt = 0

while pq:
    w, u = heapq.heappop(pq)

    if visited[u]:
        continue

    visited[u] = True
    total += w
    cnt += 1

    for ww, v in adj[u]:
        if not visited[v]:
            heapq.heappush(pq, (ww, v))

if cnt != n:
    print("Do thi khong lien thong")
else:
    print("MST =", total)

Vì sao Kruskal cần DSU?

Kruskal xét cạnh theo trọng số tăng dần. Khi gặp cạnh (u, v), cần biết u và v đã nằm cùng component chưa. DSU trả lời việc này rất nhanh bằng find(u) == find(v).

Vì sao Prim cần heap?

Ở mỗi bước Prim cần cạnh nhỏ nhất nối từ tập đã thăm ra ngoài. Heap giúp lấy cạnh nhỏ nhất nhanh, thay vì quét toàn bộ danh sách cạnh nhiều lần.

Vì sao phải kiểm tra liên thông?

MST đầy đủ phải có đúng n - 1 cạnh hoặc Prim phải thăm đủ n đỉnh. Nếu không, đồ thị không liên thông và không có MST đầy đủ.

5. So sánh Kruskal và Prim

Tiêu chí	Kruskal	Prim	Gợi ý chọn
Ý tưởng	Sắp xếp tất cả cạnh, chọn cạnh nhỏ nhất không tạo chu trình.	Mở rộng từ một đỉnh bằng cạnh nhỏ nhất ra ngoài.	Kruskal dễ hiểu nếu đã học DSU; Prim gần với Dijkstra.
Cấu trúc dữ liệu	DSU / Union-Find.	Priority queue / heap.	Chọn theo cấu trúc đã quen và dạng input.
Độ phức tạp	`O(m log m)` do sắp xếp cạnh.	`O(m log n)` với heap.	Cả hai đều dùng tốt cho bài thi phổ thông/HSG.
Đồ thị thưa	Rất phù hợp.	Cũng phù hợp.	Với danh sách cạnh, Kruskal thường tiện.
Cần in cạnh MST	Rất dễ: cạnh nào `unite` thành công thì lưu lại.	Cần lưu thêm cha/cạnh khi đưa vào heap.	Kruskal thường ngắn hơn.

6. Thực hành nhanh: tự nhập đồ thị và kiểm tra MST

Nhập mỗi dòng một cạnh dạng u v w. Dòng đầu ghi n m.

Kết quả sẽ hiện ở đây.

7. Lỗi học sinh hay nhầm

Quên kiểm tra đồ thị liên thông.
Nếu Kruskal chọn được ít hơn n - 1 cạnh thì không có MST đầy đủ.

DSU không tối ưu.
Nên dùng path compression và union by size/rank để tránh chậm ở test lớn.

Prim cộng nhầm cạnh vào đỉnh đã thăm.
Khi lấy từ heap, nếu đỉnh đã visited thì phải bỏ qua.

Nhầm MST với đường đi ngắn nhất.
MST tối ưu tổng chi phí nối toàn bộ đỉnh, không đảm bảo đường giữa hai đỉnh là ngắn nhất.

8. Bài tập luyện tập phân loại

📘 Cơ bản

Tìm tổng trọng số MST bằng Kruskal.
Tìm tổng trọng số MST bằng Prim.
Kiểm tra đồ thị có liên thông hay không trước khi in MST.

📗 Trung bình

In ra các cạnh thuộc MST.
Nếu có nhiều MST, in một MST bất kỳ.
So sánh kết quả Kruskal và Prim trên cùng input.

📙 Nâng cao

Tìm MST trong đồ thị có trọng số âm.
Tính tổng trọng số cây khung lớn nhất.
Tìm cạnh không thể thuộc bất kỳ MST nào.

🐉 HSG định hướng

Kruskal với rollback DSU cho bài offline.
Second-best MST.
Dynamic MST ở mức nâng cao.

9. Quiz kiểm tra nhanh

Câu 1. MST của đồ thị có n đỉnh liên thông có bao nhiêu cạnh?

Câu 2. Kruskal dùng DSU để làm gì?

Câu 3. Prim thường dùng cấu trúc dữ liệu nào để chọn cạnh nhỏ nhất nhanh?

Tổng kết

Kruskal và Prim đều tìm MST. Kruskal nhìn theo cạnh và cần DSU để tránh chu trình. Prim nhìn theo đỉnh đã mở rộng và cần heap để lấy cạnh nhỏ nhất ra ngoài. Khi đồ thị không liên thông, không có MST đầy đủ.