Cây khung nhỏ nhất: Kruskal, Prim

Đỗ Thị Hồng Ngát 30/04/2025
Cây khung nhỏ nhất: Kruskal, Prim
30
Th4

Các bạn thân mến

Cây khung nhỏ nhất và thuật toán Kruskal, Prim là những nội dung rất quan trọng trong lí thuyết đồ thì khi học lập trình thi đấu, vậy nên bài viết này, hãy cùng mình làm rõ chúng nhé

 

1. Định nghĩa cây khung và cây khung nhỏ nhất

Cho đồ thị vô hướng có trọng số G = (V, E), trong đó V là tập các đỉnh và E là tập các cạnh (mỗi cạnh là cặp đỉnh u-v có trọng số w). Một cây khung là tập hợp các cạnh E sao cho có thể kết nối các đỉnh V và không chứa chu trình. Một chu trình là một đường đi mà bắt đầu và kết thúc tại cùng một đỉnh, và tất cả các cạnh trên đường đi đó đều khác nhau (không lặp lại). Cây khung nhỏ nhất là cây khung có các cạnh có trọng số nhỏ

Đồ thị và cây khung nhỏ nhất được tô màu đỏ

2. Thuật toán Prim tìm cây khung nhỏ nhất

Để tìm một cây khung nhỏ nhất, một trong những thuật toán chúng ta có thể áp dụng được là thuật toán Prim.

Ý tưởng của thuật toán Prim là việc các bạn từ một cạnh , bạn sẽ mở rộng ra theo thứ từ của DFS và nạp thêm các cạnh khác vào trong một hàng đợi ưu tiên, sau đó kết nạp cạnh chưa được kết nối

Dưới đây là mô phỏng cách thuật toán Prim hoạt động

Prim

 

  1. Khởi tạo

    • Chọn đỉnh xuất phát là 1, đánh dấu màu xanh nhạt.

    • Các cạnh nối từ 1 (vào đỉnh 2 với trọng số w = 2, vào đỉnh 3 với trọng số w = 3) được đưa vào hàng đợi ưu tiên.

    Bước 1

    • Lấy cạnh nhỏ nhất trong hàng đợi: (1 – 2) với trọng số w = 2.

    • Tô đỏ cạnh này, đánh dấu đỉnh 2 thành “đã thăm”.

    • Thêm vào hàng đợi tất cả các cạnh mới từ 2 đến các đỉnh chưa thăm: (2 – 3, w = 1), (2 – 4, w = 4).

    Bước 2

    • Chọn cạnh nhỏ nhất hiện có: (2 – 3) với trọng số w = 1.

    • Tô đỏ cạnh, đánh dấu đỉnh 3 thành “đã thăm”.

    • Từ 3, thêm các cạnh đến đỉnh 5 (w = 6) và cạnh tới 4 (w = 5) vào hàng đợi.

    Bước 3

    • Cạnh nhỏ tiếp theo là (1 – 3) w = 3, nhưng vì đỉnh 3 đã nằm trong cây nên bỏ qua.

    • So sánh hai cạnh còn lại nối thành phần: (2 – 4, w = 4) và (3 – 4, w = 5); chọn (2 – 4) vì trọng số nhỏ hơn.

    • Tô đỏ cạnh (2 – 4), đánh dấu đỉnh 4.

    Bước 4

    • Cạnh nhỏ nhất hiện tại nối một đỉnh đã thăm với đỉnh chưa thăm là (3 – 5) w = 6.

    • Tô đỏ cạnh này và đánh dấu đỉnh 5.

    Kết quả
    Cây khung nhỏ nhất hoàn chỉnh gồm các cạnh đỏ:

    • (1 – 2, w = 2)

    • (2 – 3, w = 1)

    • (2 – 4, w = 4)

    • (3 – 5, w = 6)

    Tổng trọng số = 2 + 1 + 4 + 6 = 13.

Sau đây là các cài đặt thuật toán Prim


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pq priority_queue
#define pii pair<int, int>
#define inf 10000000
vector<pair<int, int>> graph[100000];
int D[100000];
int n, m;
int Prim(int S)
{
    int ans = 0;
    pq<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    for (int i = 0; i < n + 2; i++)
        D[i] = inf;
    D[S] = 0;
    q.push({D[S], S});
    while (q.size() != 0)
    {
        auto top = q.top();
        q.pop();
        int u = top.second;
        int w = top.first;
        if (w != D[u])
            continue;

        ans += D[u];
        D[u] = -inf;
        for (int i = 0; i < graph[u].size(); i++) { auto v = graph[u][i].second; auto w = graph[u][i].first; if (D[v] > w)
            {
                D[v] = w;
                q.push({D[v], v});
            }
        }
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("main.inp","r",stdin);
    // freopen("main.out","w",stdout);
    cin >> n >> m;
    for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w;
        pii o = {w, u};
        pii p = {w, v};
        graph[u].push_back(p);
        graph[v].push_back(o);
    }
    cout << Prim(1) << endl;
    return 0;
}

 

1. Khai báo và chuẩn bị

#define ll long long
#define ld long double
#define pq priority_queue
#define pii pair<int, int>
#define inf 10000000
vector<pair<int, int>> graph[100000];
int D[100000];
int n, m;
  • graph[100000]: mảng danh sách kề cho đồ thị.
  • D[100000]: lưu trọng số nhỏ nhất của cạnh nối đến các đỉnh chưa thăm. Kiểu như là cạnh 3 có 3 cạnh nối đến có trọng số là {1,3,2} thì D[3]=1
  • n, m: số lượng đỉnh và cạnh của đồ thị.

2. Hàm Prim (Chạy thuật toán Prim)

int Prim(int S)
{
    int ans = 0;
    pq<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    for (int i = 0; i < n + 2; i++)
        D[i] = inf;
    D[S] = 0;
    q.push({D[S], S});
    while (q.size() != 0)
    {
        auto top = q.top();
        q.pop();
        int u = top.second;
        int w = top.first;
        if (w != D[u])
            continue;

        ans += D[u];
        D[u] = -inf;
        for (int i = 0; i < graph[u].size(); i++) { 
            auto v = graph[u][i].second; 
            auto w = graph[u][i].first; 
            if (D[v] > w)
            {
                D[v] = w;
                q.push({D[v], v});
            }
        }
    }
    return ans;
}
  • ans: tổng trọng số của cây khung nhỏ nhất.
  • q: hàng đợi ưu tiên lưu dạng pair<int,int> trong đó: first là trọng số cạnh nối đến đỉnh đó, second là đỉnh được nối đến .
  • Khởi tạo D[i] với inf, đặt D[S] = 0 và đẩy đỉnh xuất phát vào hàng đợi.
  • Mỗi vòng lặp: lấy cạnh nhỏ nhất, sau đó thăm đỉnh mới được kết nối và nạp vào pair độ dài và cạnh .
  • Trả về tổng trọng số ans khi đã thăm tất cả đỉnh.
        if (w != D[u])
                      continue;

Đoạn này có thể khó hiểu với các bạn, mình sẽ giải thích nhé. Các bạn thấy là là D[u] lưu trọng số nhỏ nhất của cạnh nối đến các đỉnh chưa thăm, và priority queue sẽ giúp bạn lấy ra cạnh và đỉnh có trọng số nhỏ nhất. Vậy sau khi các bạn pop pair đó ra thì sẽ có pair khác cũng có cùng đỉnh nhưng khác cạnh được nối đến, và tất nhiên cạnh này nối rồi và trọng số không bao giờ là nhỏ nhất nên mình bỏ đi thôi, đoạn này các bạn thử suy nghĩ nhé.

3. Hàm main: Đọc đầu vào và gọi Prim

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    cout << Prim(1) << 'n';
    return 0;
}

Độ phức tạp của thuật toán này là O(N log N)

3.Thuật toán Kruskal tìm cây khung nhỏ nhất

Ý tưởng của thuật toán Kruskal cũng có thể nói là gần giống thuật toán Prim. Nhưng khác ở chỗ, trước khi sát nhập các cạnh, thì mình sẽ tạo một mảng pair với tất cả các giá trị của cạnh và đỉnh nối đến, sau đó sắp xếp các pair theo thứ tự tăng dẫn của các trọng số các đỉnh và sau đó dùng DSU để ghép nối

 

Trong GIF mô phỏng Kruskal, các cạnh của đồ thị được xét theo thứ tự trọng số tăng dần và được chọn vào cây khung nhỏ nhất (MST) nếu không tạo chu trình bởi cấu trúc DSU. Mỗi bước thực hiện như sau:

Kruskal

  1. Bước 0: Xét (2–3, w=1) – cạnh nhỏ nhất; chưa có cạnh nào chọn.
  2. Bước 1: Xét (2–3, w=1); hai đỉnh khác thành phần ⇒ thêm cạnh đỏ (2–3).
  3. Bước 2: Xét (1–2, w=2); đỉnh 1 và 2 khác thành phần ⇒ thêm (1–2).
  4. Bước 3: Xét (1–3, w=3); 1 và 3 cùng thành phần ⇒ bỏ qua.
  5. Bước 4: Xét (2–4, w=4); 2 và 4 khác thành phần ⇒ thêm (2–4).
  6. Bước 5: Xét (3–4, w=5); cùng thành phần ⇒ bỏ qua.
  7. Bước 6: Xét (3–5, w=6); khác thành phần ⇒ thêm (3–5).
  8. Bước 7: Xét (4–5, w=7); cùng thành phần ⇒ bỏ qua.

Kết quả cuối cùng: MST gồm các cạnh đỏ (2–3, w=1), (1–2, w=2), (2–4, w=4), (3–5, w=6), tổng trọng số 13.

Sau đây là cách cài đặt thuật toán Kruskal


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pq priority_queue
#define bs binary_search
#define int ll
const ll sized = 1e6;
const ll N = 1e7;
const ll inf = 1e18;
const ll MOD = 123456789;
const ll LOG = 20;
vector<pair<int, pair<int, int>>> graph;
int par[sized];
int getroot(int u)
{
    if (par[u] < 0) return u; return par[u] = getroot(par[u]); } void merge(int u, int v) { u = getroot(u); v = getroot(v); if (u == v) return; if (par[u] >= par[v])
        swap(u, v);
    par[u] += par[v];
    par[v] = u;
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("main.inp","r",stdin);
    // freopen("main.out","w",stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w;
        graph.push_back({w, {u, v}});
    }
    sort(graph.begin(), graph.end());
    for (int i = 0; i < sized; i++)
    {
        par[i] = -1;
    }
    int ans = 0;
    for (int i = 0; i < graph.size(); i++)
    {
        int u = graph[i].second.first;
        int v = graph[i].second.second;
        int w = graph[i].first;
        u = getroot(u);
        v = getroot(v);
        if (u == v)
            continue;
        else
        {
            merge(u, v);
            ans += w;
        }
    }
    cout << ans << endl;
    return 0;
}

Mình sẽ chuẩn bị 1 vector với kiểu dữ liệu pair<int,pair<int,int> > để lưu một cạnh có dạng {trọng số,{đỉnh bắt đầu, đỉnh kết thúc}}
Sau đó mình sẽ sort lại mảng và dùng DSU để nối các cạnh có trọng số nhỏ nhất, cặp cạnh nào nối rồi thì mình không nối nữa

Độ phức tạp của thuật toán là O(N log N)

Các bạn hoàn toàn có thể giải thử lại bài toán tìm cây khung nhỏ nhất bằng cả 2 thuật toán ở link này nhé

Cảm ơn các bạn đã đọc và hi vọng rằng qua bài đọc các bạn có thể làm chủ thành công một trong những nội dung rất quan trọng trong lí thuyết đồ thị. Chúc các bạn luôn thành công trên con đường học lập trình thi đấu của mình

Bài viết liên quan:

Bài viết cùng chủ đề:

Đỗ Thị Hồng Ngát

Để lại một bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *