Bài 20.3. Thuật toán Prim tìm cây khung nhỏ nhất

Chào mừng trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ lặn sâu vào thế giới của đồ thị và một trong những bài toán kinh điển trên đồ thị: tìm Cây Khung Nhỏ Nhất (Minimum Spanning Tree - MST). Để giải quyết bài toán này, chúng ta có một "ngôi sao" mang tên Thuật toán Prim.

Hãy cùng tìm hiểu xem thuật toán này hoạt động như thế nào, tại sao nó lại hiệu quả và cách triển khai nó bằng C++ nhé!

Cây Khung Nhỏ Nhất (Minimum Spanning Tree - MST) là gì?

Trước khi nói về Prim, chúng ta cần hiểu rõ bài toán.

Hãy tưởng tượng bạn có một mạng lưới các thành phố (đỉnh) và các con đường nối giữa chúng (cạnh). Mỗi con đường có một chi phí xây dựng hoặc khoảng cách (trọng số). Bạn muốn xây dựng một hệ thống đường sá mới sao cho tất cả các thành phố đều được kết nối với nhau, nhưng bạn muốn tổng chi phí xây dựng là nhỏ nhất có thể. Đây chính là bài toán tìm MST!

Một cách hình thức hơn:

Đồ thị (Graph): Là tập hợp các đỉnh (vertices) và các cạnh (edges) nối các đỉnh đó.
Đồ thị vô hướng (Undirected Graph): Các cạnh không có hướng, tức là nếu có cạnh nối đỉnh A và B, bạn có thể đi từ A đến B và từ B đến A.
Đồ thị có trọng số (Weighted Graph): Mỗi cạnh có một giá trị số đi kèm, gọi là trọng số (weight), thường biểu thị chi phí, khoảng cách, thời gian, v.v.
Đồ thị liên thông (Connected Graph): Có đường đi giữa bất kỳ hai đỉnh nào trong đồ thị.
Cây (Tree): Là một đồ thị liên thông không chứa chu trình.
Cây khung (Spanning Tree): Là một cây con của đồ thị gốc, chứa tất cả các đỉnh của đồ thị gốc.
Cây khung nhỏ nhất (Minimum Spanning Tree - MST): Đối với một đồ thị vô hướng, liên thông, có trọng số, MST là một cây khung có tổng trọng số của tất cả các cạnh là nhỏ nhất trong số tất cả các cây khung có thể có.

Bài toán MST có rất nhiều ứng dụng thực tế: thiết kế mạng lưới điện, mạng lưới viễn thông, định tuyến trong mạng máy tính, thiết kế đường ống dẫn dầu/khí, v.v.

Thuật toán Prim: "Phát triển" cây khung từ một đỉnh

Thuật toán Prim là một trong hai thuật toán tham lam (greedy algorithms) nổi tiếng để tìm MST (thuật toán còn lại là Kruskal). Điểm cốt lõi của thuật toán tham lam là ở mỗi bước, nó đưa ra lựa chọn tốt nhất tại thời điểm đó mà không cần xem xét hậu quả lâu dài, và điều đáng ngạc nhiên là đối với bài toán MST, chiến lược tham lam này lại hoạt động đúng!

Ý tưởng của Prim là:

Bắt đầu với một cây con chỉ gồm một đỉnh bất kỳ.
repeatedly Mở rộng cây con này bằng cách thêm vào cạnh nhỏ nhất nối một đỉnh đã có trong cây con với một đỉnh chưa có trong cây con.
Lặp lại quá trình này cho đến khi cây con bao gồm tất cả các đỉnh của đồ thị gốc.

Lúc này, cây con mà chúng ta xây dựng được chính là một Cây Khung Nhỏ Nhất!

Các bước thực hiện của Thuật toán Prim:

Giả sử đồ thị của chúng ta có $V$ đỉnh.

Chọn một đỉnh bất kỳ làm đỉnh bắt đầu. Đưa đỉnh này vào tập các đỉnh đã xây dựng cây khung. Khởi tạo cây khung ban đầu chỉ gồm đỉnh này.
Duy trì một danh sách (hoặc cách hiệu quả hơn là cấu trúc dữ liệu ưu tiên) các cạnh tiềm năng có thể thêm vào cây khung. Các cạnh này là những cạnh nối một đỉnh đã có trong cây khung với một đỉnh chưa có trong cây khung.
Lặp lại $V-1$ lần (vì cây khung có $V-1$ cạnh):
- Chọn cạnh có trọng số nhỏ nhất trong số các cạnh tiềm năng.
- Nếu cạnh được chọn nối một đỉnh đã có trong cây khung với một đỉnh chưa có, thì thêm cạnh này vào cây khung và đưa đỉnh chưa có đó vào tập các đỉnh đã xây dựng cây khung.
- (Nếu cạnh được chọn nối hai đỉnh đã có trong cây khung, cạnh đó sẽ tạo chu trình, ta bỏ qua cạnh này. Tuy nhiên, với cách quản lý cạnh hiệu quả, trường hợp này thường được xử lý ngầm).
- Cập nhật danh sách các cạnh tiềm năng: thêm vào các cạnh mới nối đỉnh vừa thêm vào cây khung với các đỉnh chưa có.
Sau $V-1$ bước lặp, ta sẽ có một cây khung chứa tất cả $V$ đỉnh và có tổng trọng số nhỏ nhất.

Ví dụ minh họa "thủ công"

Hãy xem xét một đồ thị đơn giản để hiểu rõ hơn các bước.

Giả sử chúng ta có đồ thị 5 đỉnh và các cạnh với trọng số như sau:

(A, B): 2
(A, C): 3
(B, C): 4
(B, D): 3
(C, D): 5
(C, E): 6
(D, E): 7

Chúng ta sẽ bắt đầu từ đỉnh A.

Bước 1:
- Tập đỉnh đã xây dựng: {A}
- Các cạnh tiềm năng nối {A} với bên ngoài: (A, B) trọng số 2, (A, C) trọng số 3.
Bước 2:
- Cạnh nhỏ nhất trong các cạnh tiềm năng là (A, B) với trọng số 2. Đỉnh B chưa có trong tập đỉnh đã xây dựng.
- Thêm cạnh (A, B) vào cây khung. Thêm đỉnh B vào tập đỉnh đã xây dựng.
- Cây khung hiện tại: {(A, B)}
- Tổng trọng số: 2
- Tập đỉnh đã xây dựng: {A, B}
- Các cạnh tiềm năng:
  - Từ {A}: (A, C) trọng số 3.
  - Từ {B}: (B, C) trọng số 4, (B, D) trọng số 3.
  - Tổng các cạnh tiềm năng nối {A, B} với bên ngoài: (A, C) 3, (B, C) 4, (B, D) 3.
Bước 3:
- Cạnh nhỏ nhất trong các cạnh tiềm năng là (A, C) trọng số 3 và (B, D) trọng số 3. Chọn một trong hai, ví dụ (A, C). Đỉnh C chưa có.
- Thêm cạnh (A, C) vào cây khung. Thêm đỉnh C vào tập đỉnh đã xây dựng.
- Cây khung hiện tại: {(A, B), (A, C)}
- Tổng trọng số: 2 + 3 = 5
- Tập đỉnh đã xây dựng: {A, B, C}
- Các cạnh tiềm năng:
  - Từ {A, B, C} nối ra ngoài:
    - (B, D) 3 (nối B đã có với D chưa có)
    - (C, D) 5 (nối C đã có với D chưa có)
    - (C, E) 6 (nối C đã có với E chưa có)
  - (C, B) 4 (nối C đã có với B đã có - bỏ qua)
  - Các cạnh tiềm năng hiện tại: (B, D) 3, (C, D) 5, (C, E) 6.
Bước 4:
- Cạnh nhỏ nhất trong các cạnh tiềm năng là (B, D) trọng số 3. Đỉnh D chưa có.
- Thêm cạnh (B, D) vào cây khung. Thêm đỉnh D vào tập đỉnh đã xây dựng.
- Cây khung hiện tại: {(A, B), (A, C), (B, D)}
- Tổng trọng số: 5 + 3 = 8
- Tập đỉnh đã xây dựng: {A, B, C, D}
- Các cạnh tiềm năng:
  - Từ {A, B, C, D} nối ra ngoài:
    - (C, E) 6 (nối C đã có với E chưa có)
    - (D, E) 7 (nối D đã có với E chưa có)
  - Các cạnh tiềm năng hiện tại: (C, E) 6, (D, E) 7.
Bước 5:
- Cạnh nhỏ nhất trong các cạnh tiềm năng là (C, E) trọng số 6. Đỉnh E chưa có.
- Thêm cạnh (C, E) vào cây khung. Thêm đỉnh E vào tập đỉnh đã xây dựng.
- Cây khung hiện tại: {(A, B), (A, C), (B, D), (C, E)}
- Tổng trọng số: 8 + 6 = 14
- Tập đỉnh đã xây dựng: {A, B, C, D, E}
Kết thúc: Tất cả 5 đỉnh đã được đưa vào cây khung. Chúng ta đã xây dựng được một MST với tổng trọng số là 14. Các cạnh của MST là (A, B), (A, C), (B, D), (C, E).

Triển khai Thuật toán Prim bằng C++ (Sử dụng Priority Queue)

Việc tìm kiếm cạnh có trọng số nhỏ nhất ở mỗi bước có thể tốn kém nếu duyệt qua tất cả các cạnh tiềm năng. Để làm cho Prim hiệu quả, chúng ta thường sử dụng cấu trúc dữ liệu Priority Queue (hàng đợi ưu tiên). Priority Queue sẽ giúp chúng ta lấy ra cạnh có trọng số nhỏ nhất một cách nhanh chóng.

Chúng ta sẽ lưu trữ trong Priority Queue các cặp {trọng số, đỉnh đích} của các cạnh nối từ cây khung hiện tại tới các đỉnh chưa được thêm vào.

Chi tiết triển khai với Priority Queue:

Biểu diễn đồ thị: Sử dụng danh sách kề (adjacency list). Mỗi phần tử trong danh sách kề của đỉnh u sẽ là một cặp {trọng số, đỉnh_v} biểu thị có cạnh nối từ u đến v với trọng số đó.
Theo dõi đỉnh đã thăm: Một mảng boolean visited để đánh dấu các đỉnh đã được đưa vào cây khung.
Lưu trọng số nhỏ nhất để nối một đỉnh chưa thăm vào cây: Một mảng dist (hoặc min_cost) lưu trữ trọng số cạnh nhỏ nhất hiện tại để nối đỉnh i (chưa thăm) vào tập các đỉnh đã thăm. Ban đầu, dist[i] được đặt là vô cực cho tất cả các đỉnh trừ đỉnh bắt đầu (đỉnh bắt đầu có dist = 0).
Priority Queue: Lưu trữ các cặp {trọng số, đỉnh}. Priority Queue sẽ tự động sắp xếp sao cho phần tử có trọng số nhỏ nhất luôn nằm ở đỉnh.

Code C++:

#include <iostream>
#include <vector>
#include <queue>
#include <limits> // For numeric_limits

using namespace std;

// Cấu trúc để biểu diễn cạnh: {trọng số, đỉnh đích}
typedef pair<int, int> Edge;

// Hàm thực hiện thuật toán Prim
// num_vertices: số đỉnh
// adj: danh sách kề, adj[u] chứa vector các cặp {trọng số, v} cho các cạnh (u, v)
void primMST(int num_vertices, const vector<vector<Edge>>& adj) {
    // Mảng đánh dấu các đỉnh đã được đưa vào MST
    vector<bool> visited(num_vertices, false);

    // Mảng lưu trữ trọng số nhỏ nhất để nối mỗi đỉnh chưa thăm vào MST
    // Ban đầu tất cả là vô cực, đỉnh bắt đầu là 0
    vector<int> min_cost(num_vertices, numeric_limits<int>::max());

    // Mảng lưu trữ đỉnh "cha" trong MST (dùng để in cây khung)
    vector<int> parent(num_vertices, -1);

    // Priority Queue: lưu trữ các cặp {trọng số, đỉnh}
    // pair<int, int> lưu {cost, vertex}
    // greater<pair<int, int>> để tạo min-priority queue (phần tử nhỏ nhất ở top)
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;

    // Chọn đỉnh 0 làm đỉnh bắt đầu (có thể chọn đỉnh bất kỳ)
    int start_vertex = 0;
    min_cost[start_vertex] = 0;
    pq.push({0, start_vertex}); // Đẩy đỉnh bắt đầu vào PQ với cost 0

    int total_mst_cost = 0;
    int edges_in_mst = 0; // Đếm số cạnh đã thêm vào MST

    cout << "Cac canh cua MST:" << endl;

    // Vòng lặp chính: tiếp tục cho đến khi PQ rỗng hoặc đã có V-1 cạnh (đã thăm V đỉnh)
    while (!pq.empty() && edges_in_mst < num_vertices) {
        // Lấy ra đỉnh có chi phí nhỏ nhất từ PQ
        Edge current_edge = pq.top();
        pq.pop();

        int cost = current_edge.first;
        int u = current_edge.second;

        // Nếu đỉnh u đã được thăm, bỏ qua (vì đã tìm được đường đi tốt hơn)
        if (visited[u]) {
            continue;
        }

        // Đánh dấu đỉnh u đã được thăm và thêm vào MST
        visited[u] = true;
        total_mst_cost += cost;
        edges_in_mst++;

        // Nếu đây không phải đỉnh bắt đầu (parent[u] != -1), in cạnh vừa thêm
        if (parent[u] != -1) {
             // Cạnh vừa thêm là (parent[u], u)
             cout << "  (" << parent[u] << ", " << u << ") - Trong so: " << cost << endl;
        } else {
             // Đây là đỉnh bắt đầu, không có cạnh đi vào từ MST
             cout << "  Bat dau voi dinh " << u << endl;
        }


        // Duyệt qua tất cả các đỉnh kề v của u
        for (const auto& neighbor_edge : adj[u]) {
            int neighbor_weight = neighbor_edge.first;
            int v = neighbor_edge.second;

            // Nếu đỉnh v chưa được thăm VÀ chi phí từ u đến v nhỏ hơn chi phí nhỏ nhất hiện tại để nối v vào MST
            if (!visited[v] && neighbor_weight < min_cost[v]) {
                // Cập nhật chi phí nhỏ nhất để nối v vào MST
                min_cost[v] = neighbor_weight;
                // Lưu đỉnh cha của v trong MST là u
                parent[v] = u;
                // Đẩy đỉnh v vào PQ với chi phí mới
                pq.push({min_cost[v], v});
            }
        }
    }

     // Kiểm tra xem đồ thị có liên thông không
    if (edges_in_mst < num_vertices) {
        cout << "Do thi khong lien thong, khong tim duoc cay khung." << endl;
    } else {
        cout << "Tong trong so cua MST: " << total_mst_cost << endl;
    }
}

int main() {
    // Ví dụ 1: Đồ thị trong minh họa thủ công (đỉnh 0 đến 4)
    int V1 = 5;
    vector<vector<Edge>> adj1(V1);

    // Lưu ý: Đồ thị vô hướng nên thêm cạnh cả 2 chiều
    adj1[0].push_back({2, 1}); adj1[1].push_back({2, 0}); // (0, 1) - 2
    adj1[0].push_back({3, 2}); adj1[2].push_back({3, 0}); // (0, 2) - 3
    adj1[1].push_back({4, 2}); adj1[2].push_back({4, 1}); // (1, 2) - 4
    adj1[1].push_back({3, 3}); adj1[3].push_back({3, 1}); // (1, 3) - 3
    adj1[2].push_back({5, 3}); adj1[3].push_back({5, 2}); // (2, 3) - 5
    adj1[2].push_back({6, 4}); adj1[4].push_back({6, 2}); // (2, 4) - 6
    adj1[3].push_back({7, 4}); adj1[4].push_back({7, 3}); // (3, 4) - 7

    cout << "--- MST cho vi du 1 ---" << endl;
    primMST(V1, adj1);
    cout << "-----------------------" << endl << endl;

    // Ví dụ 2: Đồ thị khác
    int V2 = 7;
    vector<vector<Edge>> adj2(V2);

    adj2[0].push_back({2, 1}); adj2[1].push_back({2, 0});
    adj2[0].push_back({7, 3}); adj2[3].push_back({7, 0});
    adj2[1].push_back({3, 2}); adj2[2].push_back({3, 1});
    adj2[1].push_back({4, 3}); adj2[3].push_back({4, 1});
    adj2[1].push_back({3, 4}); adj2[4].push_back({3, 1});
    adj2[2].push_back({5, 4}); adj2[4].push_back({5, 2});
    adj2[3].push_back({1, 4}); adj2[4].push_back({1, 3}); // Canh nhe nhat giua 3 va 4
    adj2[3].push_back({6, 5}); adj2[5].push_back({6, 3});
    adj2[4].push_back({5, 5}); adj2[5].push_back({5, 4});
    adj2[4].push_back({8, 6}); adj2[6].push_back({8, 4});
    adj2[5].push_back({9, 6}); adj2[6].push_back({9, 5});

    cout << "--- MST cho vi du 2 ---" << endl;
    primMST(V2, adj2);
    cout << "-----------------------" << endl;


    return 0;
}

Giải thích Code C++

#include <iostream>, <vector>, <queue>, <limits>: Các thư viện cần thiết cho nhập xuất, vector (danh sách kề và các mảng), priority queue, và giá trị vô cực số nguyên.
typedef pair<int, int> Edge;: Định nghĩa một kiểu dữ liệu Edge tiện lợi, là một cặp số nguyên. Trong ngữ cảnh này, chúng ta dùng để lưu {trọng số, đỉnh đích}.
primMST(int num_vertices, const vector<vector<Edge>>& adj): Hàm chính thực hiện thuật toán Prim.
- num_vertices: Tổng số đỉnh trong đồ thị.
- adj: Danh sách kề biểu diễn đồ thị. adj[u] là một vector chứa các Edge kề với đỉnh u. Vì là đồ thị vô hướng, mỗi cạnh (u, v) trọng số w được lưu ở cả adj[u] (là {w, v}) và adj[v] (là {w, u}).
vector<bool> visited(num_vertices, false);: Mảng boolean để theo dõi đỉnh nào đã được thêm vào MST. Ban đầu, không có đỉnh nào được thăm.
vector<int> min_cost(num_vertices, numeric_limits<int>::max());: Mảng này là trái tim của việc sử dụng Priority Queue trong Prim. min_cost[v] lưu trữ trọng số nhỏ nhất của một cạnh hiện tại nối một đỉnh đã thăm (visited[u] == true) với đỉnh v (chưa thăm, visited[v] == false). Ban đầu, tất cả các chi phí này là vô cực.
vector<int> parent(num_vertices, -1);: Mảng này lưu trữ đỉnh "cha" của mỗi đỉnh trong MST. parent[v] = u nghĩa là cạnh (u, v) là cạnh được chọn để đưa đỉnh v vào MST. Dùng để in ra các cạnh của MST. Đỉnh bắt đầu không có cha (-1).
priority_queue<Edge, vector<Edge>, greater<Edge>> pq;: Khai báo một priority queue.
- Edge: Kiểu dữ liệu của các phần tử ({trọng số, đỉnh}).
- vector<Edge>: Container cơ bản cho PQ.
- greater<Edge>: Comparator để biến nó thành min-priority queue. Mặc định priority_queue là max-PQ. Với greater, cặp có phần tử đầu tiên (trọng số) nhỏ nhất sẽ được ưu tiên lên đỉnh.
int start_vertex = 0; min_cost[start_vertex] = 0; pq.push({0, start_vertex});: Chọn đỉnh 0 làm đỉnh bắt đầu (có thể chọn bất kỳ). Đặt chi phí để đến đỉnh này là 0 và đưa nó vào PQ.
Vòng lặp while (!pq.empty() && edges_in_mst < num_vertices): Vòng lặp chính tiếp tục cho đến khi PQ rỗng (không còn cạnh tiềm năng) hoặc đã thu thập đủ $V-1$ cạnh cho một MST (đã thăm $V$ đỉnh).
Edge current_edge = pq.top(); pq.pop();: Lấy cạnh có trọng số nhỏ nhất từ PQ. Đây là cạnh tiềm năng tốt nhất hiện tại.
int cost = current_edge.first; int u = current_edge.second;: Tách trọng số và đỉnh đích từ cạnh lấy ra.
if (visited[u]) { continue; }: Kiểm tra xem đỉnh u đã được thăm chưa. Nếu rồi, điều này có nghĩa là chúng ta đã tìm thấy một đường đi ngắn hơn đến u trước đó và đã xử lý nó. Cặp {cost, u} này trong PQ là "dư thừa" hoặc "lỗi thời", nên ta bỏ qua.
visited[u] = true; total_mst_cost += cost; edges_in_mst++;: Nếu đỉnh u chưa thăm, đánh dấu nó là đã thăm. Thêm cost (đây chính là trọng số của cạnh nối đỉnh u vào MST) vào tổng chi phí MST. Tăng số cạnh trong MST.
if (parent[u] != -1) { ... }: In ra cạnh vừa thêm vào MST. Đỉnh u được nối vào MST thông qua cạnh từ đỉnh parent[u].
for (const auto& neighbor_edge : adj[u]) { ... }: Duyệt qua tất cả các đỉnh kề v của đỉnh u vừa thêm vào MST.
int neighbor_weight = neighbor_edge.first; int v = neighbor_edge.second;: Lấy trọng số và đỉnh đích của cạnh kề.
if (!visited[v] && neighbor_weight < min_cost[v]) { ... }: Đây là bước relaxation quan trọng. Nếu đỉnh kề v chưa được thăm VÀ trọng số của cạnh hiện tại (u, v) (neighbor_weight) nhỏ hơn chi phí nhỏ nhất đã biết để nối v vào MST (min_cost[v]), thì chúng ta tìm thấy một đường đi tốt hơn để nối v vào MST thông qua đỉnh u.
min_cost[v] = neighbor_weight; parent[v] = u; pq.push({min_cost[v], v});: Cập nhật min_cost[v] với trọng số mới nhỏ hơn, lưu u làm đỉnh cha của v, và đẩy cặp {min_cost[v], v} mới vào PQ. Lưu ý: có thể có nhiều cặp {cost, v} khác nhau trong PQ cho cùng một đỉnh v. Điều này là bình thường; khi xử lý, chúng ta chỉ lấy cặp có cost nhỏ nhất và bỏ qua nếu v đã được thăm (như ở bước 12).
Kiểm tra liên thông: Sau vòng lặp, nếu edges_in_mst < num_vertices, điều đó có nghĩa là không phải tất cả các đỉnh đều được thăm, suy ra đồ thị không liên thông và không có cây khung (hay MST) chứa tất cả các đỉnh.

Ví dụ 2: Trace theo code

Hãy thử trace lại Ví dụ 2 với code để hiểu cách Priority Queue hoạt động. Đỉnh bắt đầu là 0.

Đồ thị 7 đỉnh: (0,1,2), (0,3,7), (1,2,3), (1,3,4), (1,4,3), (2,4,5), (3,4,1), (3,5,6), (4,5,5), (4,6,8), (5,6,9) (u, v, weight)

Khởi tạo: visited = {F, F, F, F, F, F, F} min_cost = {0, inf, inf, inf, inf, inf, inf} parent = {-1, -1, -1, -1, -1, -1, -1} pq = {{0, 0}} total_mst_cost = 0 edges_in_mst = 0

Vòng lặp 1:

pq.top() = {0, 0}. Pop.
u = 0, cost = 0. visited[0] = F.
visited[0] = T. total_mst_cost = 0. edges_in_mst = 1. In "Bat dau voi dinh 0".
Duyệt kề của 0:
- (0, 1) cost 2: !visited[1] (T) && 2 < min_cost[1] (inf). Cập nhật min_cost[1] = 2, parent[1] = 0, push {2, 1} to PQ.
- (0, 3) cost 7: !visited[3] (T) && 7 < min_cost[3] (inf). Cập nhật min_cost[3] = 7, parent[3] = 0, push {7, 3} to PQ.
pq = {{2, 1}, {7, 3}} (min-heap)

Vòng lặp 2:

pq.top() = {2, 1}. Pop.
u = 1, cost = 2. visited[1] = F.
visited[1] = T. total_mst_cost = 0 + 2 = 2. edges_in_mst = 2. In "(0, 1) - Trong so: 2".
Duyệt kề của 1:
- (1, 0) cost 2: visited[0] = T. Bỏ qua.
- (1, 2) cost 3: !visited[2] (T) && 3 < min_cost[2] (inf). Cập nhật min_cost[2] = 3, parent[2] = 1, push {3, 2} to PQ.
- (1, 3) cost 4: !visited[3] (T) && 4 < min_cost[3] (7). Cập nhật min_cost[3] = 4, parent[3] = 1, push {4, 3} to PQ. (Lưu ý: Đỉnh 3 đã có {7,3} trong PQ, giờ thêm {4,3})
- (1, 4) cost 3: !visited[4] (T) && 3 < min_cost[4] (inf). Cập nhật min_cost[4] = 3, parent[4] = 1, push {3, 4} to PQ.
pq = {{3, 2}, {3, 4}, {4, 3}, {7, 3}} (min-heap, thứ tự giữa 3,4 và 4,3 có thể thay đổi tùy cài đặt, nhưng 3 luôn lên đầu)

Vòng lặp 3:

pq.top() = {3, 2}. Pop. (Hoặc {3, 4}, giả sử là {3, 2})
u = 2, cost = 3. visited[2] = F.
visited[2] = T. total_mst_cost = 2 + 3 = 5. edges_in_mst = 3. In "(1, 2) - Trong so: 3".
Duyệt kề của 2:
- (2, 1) cost 3: visited[1] = T. Bỏ qua.
- (2, 4) cost 5: !visited[4] (T) && 5 < min_cost[4] (3). False, 5 không nhỏ hơn 3. Bỏ qua.
pq = {{3, 4}, {4, 3}, {7, 3}}

Vòng lặp 4:

pq.top() = {3, 4}. Pop.
u = 4, cost = 3. visited[4] = F.
visited[4] = T. total_mst_cost = 5 + 3 = 8. edges_in_mst = 4. In "(1, 4) - Trong so: 3".
Duyệt kề của 4:
- (4, 1) cost 3: visited[1] = T. Bỏ qua.
- (4, 2) cost 5: visited[2] = T. Bỏ qua.
- (4, 3) cost 1: !visited[3] (T) && 1 < min_cost[3] (4). True. Cập nhật min_cost[3] = 1, parent[3] = 4, push {1, 3} to PQ.
- (4, 5) cost 5: !visited[5] (T) && 5 < min_cost[5] (inf). Cập nhật min_cost[5] = 5, parent[5] = 4, push {5, 5} to PQ.
- (4, 6) cost 8: !visited[6] (T) && 8 < min_cost[6] (inf). Cập nhật min_cost[6] = 8, parent[6] = 4, push {8, 6} to PQ.
pq = {{1, 3}, {4, 3}, {5, 5}, {7, 3}, {8, 6}}

Vòng lặp 5:

pq.top() = {1, 3}. Pop.
u = 3, cost = 1. visited[3] = F.
visited[3] = T. total_mst_cost = 8 + 1 = 9. edges_in_mst = 5. In "(4, 3) - Trong so: 1".
Duyệt kề của 3:
- (3, 0) cost 7: visited[0] = T. Bỏ qua.
- (3, 1) cost 4: visited[1] = T. Bỏ qua.
- (3, 4) cost 1: visited[4] = T. Bỏ qua.
- (3, 5) cost 6: !visited[5] (T) && 6 < min_cost[5] (5). False, 6 không nhỏ hơn 5. Bỏ qua.
pq = {{4, 3}, {5, 5}, {7, 3}, {8, 6}}

Vòng lặp 6:

pq.top() = {4, 3}. Pop.
u = 3, cost = 4. visited[3] = T. Bỏ qua (đã xử lý ở vòng trước với cost = 1).
pq = {{5, 5}, {7, 3}, {8, 6}}

Vòng lặp 7:

pq.top() = {5, 5}. Pop.
u = 5, cost = 5. visited[5] = F.
visited[5] = T. total_mst_cost = 9 + 5 = 14. edges_in_mst = 6. In "(4, 5) - Trong so: 5".
Duyệt kề của 5:
- (5, 3) cost 6: visited[3] = T. Bỏ qua.
- (5, 4) cost 5: visited[4] = T. Bỏ qua.
- (5, 6) cost 9: !visited[6] (T) && 9 < min_cost[6] (8). False, 9 không nhỏ hơn 8. Bỏ qua.
pq = {{7, 3}, {8, 6}}

Vòng lặp 8:

pq.top() = {7, 3}. Pop.
u = 3, cost = 7. visited[3] = T. Bỏ qua.
pq = {{8, 6}}

Vòng lặp 9:

pq.top() = {8, 6}. Pop.
u = 6, cost = 8. visited[6] = F.
visited[6] = T. total_mst_cost = 14 + 8 = 22. edges_in_mst = 7. In "(4, 6) - Trong so: 8".
Duyệt kề của 6:
- (6, 4) cost 8: visited[4] = T. Bỏ qua.
- (6, 5) cost 9: visited[5] = T. Bỏ qua.
pq = {}

Kết thúc: edges_in_mst = 7, bằng số đỉnh. Vòng lặp kết thúc. In tổng trọng số MST là 22.

Các cạnh của MST (theo thứ tự được in ra): (0, 1), (1, 2), (1, 4), (4, 3), (4, 5), (4, 6).

Lưu ý thứ tự in có thể hơi khác so với thứ tự cạnh được thêm vào trong ví dụ thủ công nếu bạn chọn đỉnh khác, nhưng tập cạnh cuối cùng và tổng trọng số sẽ giống nhau.

Độ phức tạp của Thuật toán Prim

Với cài đặt Priority Queue:
- Mỗi đỉnh được đưa vào PQ tối đa một lần khi chi phí đến nó được cập nhật lần đầu hoặc tìm được đường đi tốt hơn. Khi một đỉnh được lấy ra từ PQ (và chưa thăm), nó được xử lý một lần. Có $V$ đỉnh.
- Mỗi cạnh $(u, v)$ được xem xét khi đỉnh $u$ hoặc đỉnh $v$ được thêm vào MST. Khi xem xét cạnh $(u, v)$, nếu $v$ chưa thăm, chúng ta có thể push nó vào PQ. Một cạnh có thể khiến đỉnh đích được push vào PQ nhiều lần nếu tìm thấy đường đi rẻ hơn. Tuy nhiên, mỗi cạnh chỉ gây ra tối đa hai lần cập nhật (push) trong suốt quá trình (một lần từ $u$ sang $v$, một lần từ $v$ sang $u$). Có $E$ cạnh.
- Thao tác trên Priority Queue (push, pop) mất thời gian $O(\log K)$, với $K$ là số phần tử trong PQ. Trong trường hợp xấu nhất, PQ có thể chứa tới $O(E)$ phần tử.
- Tổng cộng, mỗi đỉnh được xử lý $O(\log E)$ khi lấy ra từ PQ. Mỗi cạnh được xem xét $O(1)$, và có thể gây ra một vài thao tác push/update trong PQ, mỗi thao tác $O(\log E)$.
- Vì $E \le V^2$ và trong đồ thị liên thông $E \ge V-1$, $\log E$ thường xấp xỉ $\log V^2 = 2 \log V$, nên có thể nói là $O(\log V)$.
- Độ phức tạp thời gian: $O(V \log V + E \log V) = O(E \log V)$ (vì $E \ge V-1$ trong đồ thị liên thông cần tìm cây khung). Nếu PQ được triển khai tối ưu hơn một chút (như với Fibonacci Heap), có thể đạt $O(E + V \log V)$, nhưng với Priority Queue tiêu chuẩn C++, nó là $O(E \log V)$.
- Độ phức tạp không gian: $O(V + E)$ để lưu đồ thị và các mảng/PQ.
Với cài đặt đơn giản (không dùng PQ):
- Ở mỗi bước, chúng ta duyệt qua tất cả các đỉnh chưa thăm ($O(V)$) và tìm cạnh nhỏ nhất nối với tập đỉnh đã thăm. Việc này có thể yêu cầu duyệt qua $O(E)$ cạnh hoặc $O(V^2)$ cặp đỉnh.
- Nếu duy trì mảng min_cost và tìm kiếm tuyến tính min trong mảng này, mỗi bước mất $O(V)$. Lặp $V-1$ lần.
- Độ phức tạp thời gian: $O(V^2)$.
- Cài đặt Priority Queue rõ ràng hiệu quả hơn cho các đồ thị thưa (ít cạnh so với số đỉnh, E gần V), trong khi $O(V^2)$ có thể chấp nhận được hoặc thậm chí tốt hơn cho các đồ thị đầy đủ (nhiều cạnh, E gần $V^2$).

Bài tập ví dụ:

Thành phố và lũ lụt

Trong một dự án nghiên cứu về thiên tai, FullHouse Dev được giao nhiệm vụ phân tích dữ liệu về sự thay đổi lãnh thổ sau các đợt lũ lụt. Họ nhận được báo cáo về $N$ vùng đất riêng biệt và cách chúng hợp nhất theo thời gian.

Bài toán

Ban đầu có $N$ vùng đất riêng biệt, được đánh số từ $1$ đến $N$. Qua thời gian, một số vùng đất đã sáp nhập vào nhau. Mỗi lần sáp nhập, vùng đất $i$ sẽ thôn tính vùng đất $j$, khiến vùng đất $j$ trở thành một phần của vùng đất $i$ và được đổi tên thành vùng đất $i$. Nhiệm vụ của FullHouse Dev là xác định số lượng vùng đất còn tồn tại sau tất cả các đợt sáp nhập.

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên $N$ - số lượng vùng đất ban đầu.
Dòng thứ hai chứa số nguyên $K$ - số lượng lần sáp nhập.
$K$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $i$ và $j$, thể hiện vùng đất $i$ thôn tính vùng đất $j$.

OUTPUT FORMAT:

In ra một số nguyên duy nhất là số lượng vùng đất còn tồn tại.

Ràng buộc:

$1 \leq N \leq 10^5$
$1 \leq K \leq 10^5$

Ví dụ

INPUT

OUTPUT

Giải thích

Ban đầu có 4 vùng đất được đánh số 1, 2, 3, 4. Đầu tiên, vùng đất 1 thôn tính vùng đất 2, khiến vùng đất 2 được đổi tên thành vùng đất 1. Sau đó, vùng đất 4 thôn tính vùng đất 1, khiến các vùng đất trước đây là 1 và 2 đều trở thành vùng đất 4. Cuối cùng chỉ còn lại vùng đất 3 và vùng đất 4, vì vậy đáp án là 2. Đây là hướng dẫn giải bài "Thành phố và lũ lụt" bằng C++ một cách ngắn gọn, tập trung vào ý tưởng và cấu trúc dữ liệu cần dùng:

Hiểu bài toán: Chúng ta cần đếm số lượng vùng đất còn tồn tại sau tất cả các lần sáp nhập. Một vùng đất tồn tại nếu nó không bị vùng đất khác thôn tính. Khi i thôn tính j, vùng đất j không còn tồn tại độc lập nữa.
Ý tưởng chính: Ban đầu có N vùng đất độc lập. Mỗi lần sáp nhập i j, vùng đất j bị thôn tính và mất đi tính độc lập của nó. Vùng đất i vẫn giữ nguyên tính độc lập (trừ khi sau này nó bị vùng khác thôn tính). Điều quan trọng là chỉ cần biết vùng đất j đã từng bị thôn tính, thì nó không thể là một vùng đất độc lập cuối cùng.
Cấu trúc dữ liệu:
- Sử dụng một mảng boolean hoặc một set để đánh dấu các vùng đất đã bị thôn tính. Kích thước của mảng boolean sẽ là N+1 (để dễ dàng dùng chỉ số từ 1 đến N).
Các bước thực hiện:
- Khởi tạo mảng boolean is_absorbed (hoặc set) có kích thước N+1, tất cả các giá trị ban đầu là false (hoặc set rỗng), biểu thị chưa vùng đất nào bị thôn tính.
- Đọc số lượng lần sáp nhập K.
- Lặp K lần:
  - Đọc cặp số i và j.
  - Đánh dấu vùng đất j là đã bị thôn tính. Trong mảng boolean, set is_absorbed[j] = true.
- Sau khi xử lý tất cả K lần sáp nhập, đếm số lượng vùng đất từ 1 đến N mà không bị đánh dấu là đã bị thôn tính (tức là is_absorbed[x] vẫn là false với 1 <= x <= N).
- Kết quả đếm được chính là số lượng vùng đất còn tồn tại.
Tại sao cách này hoạt động? Vùng đất j chỉ không còn tồn tại độc lập nếu nó bị vùng đất khác thôn tính. Việc nó thôn tính ai khác không ảnh hưởng đến trạng thái độc lập của chính nó. Nếu j bị thôn tính, nó sẽ vĩnh viễn không phải là một "gốc" của lãnh thổ cuối cùng. Bằng cách đánh dấu tất cả các vùng đất bị thôn tính, chúng ta dễ dàng đếm được những vùng đất không bị thôn tính bởi bất kỳ ai trong suốt quá trình, đó chính là các vùng đất độc lập còn lại.
Độ phức tạp:
- Thời gian: O(N) để khởi tạo mảng + O(K) để xử lý K lần sáp nhập (mỗi lần O(1) với mảng boolean) + O(N) để đếm kết quả. Tổng cộng O(N + K).
- Không gian: O(N) cho mảng boolean.
- Với ràng buộc N, K <= 10^5, độ phức tạp này là hoàn toàn phù hợp.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.