Bài 20.4. So sánh và phân tích hiệu quả Kruskal và Prim

Chào mừng các bạn quay trở lại với series "Cấu trúc dữ liệu và Giải thuật" cùng FullhouseDev!

Trong các bài trước, chúng ta đã khám phá vẻ đẹp của cây bao trùm nhỏ nhất (Minimum Spanning Tree - MST) và làm quen với hai "ứng cử viên" sáng giá nhất để giải quyết bài toán này: Thuật toán Kruskal và Thuật toán Prim. Cả hai đều có chung mục tiêu là tìm ra tập hợp các cạnh nối tất cả các đỉnh của một đồ thị vô hướng có trọng số, sao cho tổng trọng số các cạnh là nhỏ nhất và không tạo thành chu trình. Tuy nhiên, cách tiếp cận và hiệu quả của chúng lại có những điểm khác biệt thú vị.

Hôm nay, chúng ta sẽ đặt Kruskal và Prim lên "sân đấu" để so sánh trực tiếp, phân tích hiệu quả của từng thuật toán và xem xét khi nào thì nên dùng "gã khổng lồ" này thay vì "gã khổng lồ" kia. Hãy cùng bắt đầu cuộc so tài đỉnh cao này nhé!

Nhắc lại ngắn gọn: Kruskal và Prim hoạt động như thế nào?

Trước khi đi sâu vào so sánh, hãy cùng lướt qua nguyên tắc hoạt động cơ bản của hai thuật toán này.

Kruskal: Lựa chọn cạnh rẻ nhất toàn cục

Thuật toán Kruskal đi theo một hướng tiếp cận khá trực giác: cứ chọn cạnh nào có trọng số nhỏ nhất trong toàn bộ đồ thị, miễn là việc thêm cạnh đó không tạo thành chu trình với các cạnh đã chọn trước đó. Cứ thế, thuật toán sẽ "gom" dần các cạnh rẻ nhất cho đến khi chọn đủ V-1 cạnh (với V là số đỉnh), đảm bảo tất cả các đỉnh được nối với nhau.

Để làm được điều này một cách hiệu quả, Kruskal cần hai thứ chính:

Sắp xếp cạnh: Toàn bộ các cạnh của đồ thị cần được sắp xếp theo thứ tự trọng số tăng dần.
Kiểm tra chu trình: Cần một cách nhanh chóng để xác định xem hai đỉnh đầu cuối của một cạnh có nằm trong cùng một thành phần liên thông (component) của cây bao trùm đang xây dựng hay không. Nếu có, việc thêm cạnh này sẽ tạo chu trình. Cấu trúc dữ liệu Disjoint Set Union (DSU), hay Union-Find, chính là "người hùng" giúp thực hiện việc này cực kỳ hiệu quả.

Prim: Mở rộng cây từ một điểm

Ngược lại, thuật toán Prim có cách tiếp cận tham lam cục bộ hơn. Nó bắt đầu từ một đỉnh bất kỳ (ví dụ: đỉnh 0). Từ đỉnh đó, nó sẽ tìm cạnh có trọng số nhỏ nhất nối một đỉnh đã thuộc cây bao trùm đang xây dựng với một đỉnh chưa thuộc cây. Cạnh này được thêm vào cây, và đỉnh mới được đánh dấu là đã thuộc cây. Quá trình này lặp lại cho đến khi tất cả các đỉnh đều nằm trong cây bao trùm.

Để Prim hoạt động hiệu quả, chúng ta cần:

Biểu diễn đồ thị: Thường sử dụng danh sách kề (adjacency list) để dễ dàng truy cập các cạnh nối từ một đỉnh.
Tìm cạnh rẻ nhất: Cần một cấu trúc dữ liệu giúp nhanh chóng tìm được cạnh có trọng số nhỏ nhất từ tập các cạnh nối giữa cây đang xây dựng và phần còn lại của đồ thị. Hàng đợi ưu tiên (Priority Queue) là lựa chọn lý tưởng cho tác vụ này.

Cuộc so tài chính: Kruskal vs. Prim - Ai hiệu quả hơn?

Đây là phần mà chúng ta sẽ "mổ xẻ" sâu hơn. Việc so sánh hiệu quả giữa hai thuật toán này chủ yếu dựa vào:

Độ phức tạp thời gian (Time Complexity): Đây là yếu tố quan trọng nhất.
Cấu trúc dữ liệu sử dụng: Ảnh hưởng đến độ phức tạp và cách triển khai.
Khả năng áp dụng: Đồ thị thưa hay đồ thị dày đặc.
Độ phức tạp cài đặt: Thuật toán nào dễ cài đặt hơn?

1. Độ phức tạp thời gian: Cuộc chiến của E và V

Kruskal:
- Bước tốn thời gian nhất là sắp xếp các cạnh. Với E cạnh, việc này mất O(E log E).
- Sau đó, chúng ta duyệt qua E cạnh. Với mỗi cạnh, thực hiện 2 phép find và 1 phép unite trong DSU. Với các tối ưu như nén đường (path compression) và hợp theo kích thước/hạng (union by size/rank), các phép toán DSU trung bình có độ phức tạp gần như hằng số, ký hiệu là O(α(V)), trong đó α là hàm Ackermann ngược, tăng trưởng cực kỳ chậm và thực tế có thể coi là một hằng số nhỏ.
- Tổng độ phức tạp của Kruskal là O(E log E + Eα(V)). Vì log E thường lớn hơn α(V) (và E ≤ V^2 nên log E ≤ 2 log V), độ phức tạp thường được viết gọn là O(E log E).
Prim:
- Độ phức tạp của Prim phụ thuộc vào cách cài đặt hàng đợi ưu tiên và biểu diễn đồ thị.
- Sử dụng danh sách kề và Min-Priority Queue (như Binary Heap):
  - Khởi tạo (đặt khoảng cách vô cực cho các đỉnh, 0 cho đỉnh bắt đầu) mất O(V).
  - Vòng lặp chính chạy tối đa V lần (mỗi lần chọn một đỉnh mới vào cây).
  - Trong mỗi lần lặp, ta trích xuất đỉnh có chi phí nhỏ nhất từ PQ: O(log V).
  - Sau khi trích xuất đỉnh u, ta duyệt qua tất cả các đỉnh v kề với u. Nếu v chưa nằm trong cây và cạnh (u, v) có trọng số nhỏ hơn chi phí hiện tại để nối v vào cây, ta cập nhật chi phí cho v và giảm khóa (decrease key) trong PQ, hoặc thêm/cập nhật v vào PQ.
  - Tổng số lần cập nhật/thêm vào PQ có thể lên tới E (mỗi cạnh được xem xét tối đa 2 lần). Mỗi thao tác thêm/cập nhật/giảm khóa trong Binary Heap mất O(log V).
  - Tổng độ phức tạp là O(V log V + E log V), thường viết gọn là O(E log V) (vì E có thể lớn hơn V log V).
- Sử dụng ma trận kề và mảng/vector đơn giản để theo dõi chi phí:
  - Ở mỗi bước, ta duyệt qua tất cả V đỉnh để tìm đỉnh chưa thuộc cây có chi phí kết nối nhỏ nhất: O(V).
  - Sau khi chọn được đỉnh u, ta cập nhật chi phí cho tất cả V đỉnh khác dựa trên các cạnh (u, v): O(V).
  - Quá trình này lặp lại V lần.
  - Tổng độ phức tạp là O(V * (V + V)) = O(V^2).

Phân tích:

Đối với đồ thị thưa (sparse graphs), nơi số cạnh E gần với số đỉnh V (ví dụ E ≈ O(V)), E log E ≈ V log V và E log V ≈ V log V. Trong trường hợp này, cả Kruskal O(E log E) và Prim O(E log V) với hàng đợi ưu tiên đều có hiệu quả tương đương, khoảng O(V log V) hoặc O(E log V).
Đối với đồ thị dày đặc (dense graphs), nơi số cạnh E gần với V^2 (ví dụ E ≈ O(V^2)), E log E ≈ V^2 log(V^2) = 2 V^2 log V và E log V ≈ V^2 log V.
- Kruskal vẫn là O(E log E) ≈ O(V^2 log V).
- Prim với hàng đợi ưu tiên là O(E log V) ≈ O(V^2 log V).
- Prim với ma trận kề và mảng đơn giản là O(V^2).
- Trong trường hợp đồ thị cực kỳ dày đặc, Prim với cài đặt O(V^2) có thể nhanh hơn cả Kruskal và Prim với hàng đợi ưu tiên vì O(V^2) nhỏ hơn O(V^2 log V).

Tóm lại về độ phức tạp:

Kruskal: Tốt nhất là O(E log E). Hiệu quả trên đồ thị thưa.
Prim:
- Với Binary Heap (danh sách kề): O(E log V). Hiệu quả trên đồ thị thưa và trung bình.
- Với mảng (ma trận kề): O(V^2). Hiệu quả trên đồ thị dày đặc.

2. Cấu trúc dữ liệu sử dụng: Công cụ nào mạnh hơn?

Kruskal:
- Cần một cách để lưu trữ các cạnh (thường là danh sách các bộ ba {trọng số, đỉnh_u, đỉnh_v}).
- Cần thuật toán sắp xếp hiệu quả (như Merge Sort, Quick Sort) để sắp xếp các cạnh.
- Cần cấu trúc Disjoint Set Union (DSU) để quản lý các thành phần liên thông và kiểm tra chu trình. DSU cần mảng parent và mảng rank hoặc size (để tối ưu).
- Ưu điểm: DSU là một cấu trúc dữ liệu mạnh mẽ và đa năng, có thể học riêng và áp dụng cho nhiều bài toán khác ngoài MST.
- Nhược điểm: Việc triển khai DSU hiệu quả (với path compression và union by rank/size) có thể hơi "khó nhằn" hơn so với các cấu trúc cơ bản.
Prim:
- Cần biểu diễn đồ thị (thường là danh sách kề vector<pair<int, int>> adj[]).
- Cần một mảng để theo dõi các đỉnh đã thuộc cây (ví dụ: bool visited[]).
- Cần một mảng để lưu trữ chi phí nhỏ nhất để kết nối mỗi đỉnh chưa thuộc cây với cây đang xây dựng (ví dụ: int min_cost[] hoặc dist[]).
- Quan trọng nhất, cần một Hàng đợi ưu tiên (Priority Queue) để lưu trữ các cạnh "tiềm năng" và nhanh chóng lấy ra cạnh rẻ nhất. PQ lưu trữ các cặp {chi phí, đỉnh_đích} hoặc {chi phí, {đỉnh_nguồn, đỉnh_đích}}.
- Ưu điểm: PQ là một cấu trúc dữ liệu rất phổ biến và có sẵn trong thư viện chuẩn của nhiều ngôn ngữ (như std::priority_queue trong C++), giúp việc cài đặt Prim trở nên dễ dàng hơn so với Kruskal nếu bạn đã quen dùng PQ.
- Nhược điểm: Cần quản lý đồng thời trạng thái của đỉnh (visited), chi phí (min_cost), và cập nhật PQ (mặc dù std::priority_queue trong C++ không hỗ trợ decrease_key hiệu quả, ta thường dùng cách thêm bản sao mới với chi phí nhỏ hơn).

3. Khả năng áp dụng: Thưa hay dày đặc?

Như đã phân tích ở phần độ phức tạp, sự lựa chọn giữa Kruskal và Prim thường phụ thuộc vào tính chất của đồ thị:

Kruskal: Thường là lựa chọn tốt hơn cho đồ thị thưa, nơi E << V^2. Độ phức tạp O(E log E) sẽ tốt hơn O(V^2) của Prim cài đặt đơn giản.
Prim:
- Với Binary Heap: Tốt cho cả đồ thị thưa và trung bình, hiệu quả tương đương Kruskal.
- Với cài đặt O(V^2) (dùng mảng/ma trận): Tốt hơn Kruskal và Prim với heap khi đồ thị cực kỳ dày đặc, nơi E ≈ V^2.

Một điểm khác cần lưu ý: Kruskal có thể hoạt động trên đồ thị không liên thông (disconnected graph) để tìm Cây Bao Trùm Nhỏ Nhất (Minimum Spanning Forest - MSF). Nó sẽ tự nhiên tìm MST cho từng thành phần liên thông. Prim thì thường được sử dụng cho đồ thị liên thông; nếu dùng cho đồ thị không liên thông, ta cần chạy Prim từ mỗi đỉnh chưa được thăm để tìm MSF.

4. Độ phức tạp cài đặt: Ai "nhập môn" dễ hơn?

Kruskal:
- Cần cài đặt hoặc hiểu rõ cấu trúc DSU với các tối ưu. Đây có thể là phần khó nhất đối với người mới bắt đầu.
- Sắp xếp cạnh là thao tác có sẵn trong thư viện.
- Logic chính là một vòng lặp đơn giản qua các cạnh đã sắp xếp.
- Nhận xét: Khó hơn một chút ở phần DSU, nhưng logic chính dễ hiểu.
Prim:
- Cần cài đặt biểu diễn đồ thị (danh sách kề là phổ biến).
- Cần sử dụng hàng đợi ưu tiên. Nếu dùng std::priority_queue trong C++, việc này khá dễ dàng. Tuy nhiên, cần lưu ý cách xử lý "giảm khóa" (thường là thêm phần tử mới vào PQ).
- Cần quản lý mảng visited và min_cost/dist.
- Nhận xét: Dễ tiếp cận hơn nếu bạn đã quen với biểu diễn đồ thị và hàng đợi ưu tiên, dù việc quản lý trạng thái các đỉnh cần cẩn thận.

Mã nguồn minh họa (C++)

Để mọi thứ trở nên rõ ràng hơn, chúng ta hãy cùng xem xét cách cài đặt cơ bản của hai thuật toán này bằng C++.

Cài đặt Kruskal với DSU

Chúng ta cần một cấu trúc Edge và một lớp/struct cho DSU.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> // for iota

// --- Cấu trúc Edge ---
struct Edge {
    int u, v, weight;

    // Hàm so sánh để sắp xếp cạnh theo trọng số
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

// --- Cấu trúc Disjoint Set Union (DSU) ---
struct DSU {
    std::vector<int> parent;
    // vector<int> sz; // Có thể dùng size hoặc rank để tối ưu union

    DSU(int n) {
        parent.resize(n);
        std::iota(parent.begin(), parent.end(), 0); // Khởi tạo mỗi đỉnh là gốc của chính nó
        // sz.assign(n, 1); // Khởi tạo kích thước mỗi tập là 1
    }

    // Tìm gốc (Find operation) với nén đường (path compression)
    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]); // Nén đường
    }

    // Hợp hai tập (Union operation) theo kích thước (hoặc hạng)
    // Trả về true nếu hợp thành công (không tạo chu trình), false nếu đã cùng tập
    bool unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);

        if (root_i != root_j) {
            // Hợp tập nhỏ vào tập lớn hơn (union by size) - ví dụ
            // if (sz[root_i] < sz[root_j]) std::swap(root_i, root_j);
            parent[root_j] = root_i;
            // sz[root_i] += sz[root_j];
            return true; // Đã hợp thành công, thêm cạnh này vào MST
        }
        return false; // Đã cùng tập, thêm cạnh này sẽ tạo chu trình
    }
};

// --- Thuật toán Kruskal ---
std::vector<Edge> kruskal_mst(int V, std::vector<Edge>& edges) {
    std::vector<Edge> mst;
    DSU dsu(V);

    // 1. Sắp xếp các cạnh theo trọng số tăng dần
    std::sort(edges.begin(), edges.end());

    // 2. Duyệt qua các cạnh đã sắp xếp
    for (const auto& edge : edges) {
        // 3. Kiểm tra xem hai đỉnh của cạnh có khác tập không
        if (dsu.unite(edge.u, edge.v)) {
            // Nếu khác tập, thêm cạnh vào MST
            mst.push_back(edge);
            // Điều kiện dừng: tìm đủ V-1 cạnh
            if (mst.size() == V - 1) {
                break;
            }
        }
    }

    return mst; // Trả về các cạnh của MST
}

int main() {
    int V = 4; // Số đỉnh
    std::vector<Edge> edges = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };

    std::vector<Edge> mst_edges = kruskal_mst(V, edges);

    std::cout << "**MST (Kruskal):**" << std::endl;
    int total_weight = 0;
    for (const auto& edge : mst_edges) {
        std::cout << "Cạnh: " << edge.u << " - " << edge.v << " (Trọng số: " << edge.weight << ")" << std::endl;
        total_weight += edge.weight;
    }
    std::cout << "Tổng trọng số MST: " << total_weight << std::endl;

    return 0;
}

Giải thích code Kruskal:

struct Edge: Định nghĩa cấu trúc đơn giản để lưu trữ thông tin của một cạnh: hai đỉnh u, v và trọng số weight. Hàm operator< được nạp chồng để cho phép sắp xếp vector<Edge> dựa trên trọng số.
struct DSU: Triển khai cấu trúc Disjoint Set Union.
- parent: Một vector lưu trữ đỉnh cha của mỗi đỉnh. Ban đầu, mỗi đỉnh là cha của chính nó (parent[i] = i).
- find(int i): Tìm gốc của tập chứa đỉnh i. Implementationsử dụng nén đường (path compression): khi tìm gốc, tất cả các đỉnh trên đường đi từ i đến gốc đều được gắn trực tiếp vào gốc, làm phẳng cấu trúc cây và tăng tốc các phép find sau này.
- unite(int i, int j): Hợp hai tập chứa đỉnh i và j. Đầu tiên, tìm gốc của cả hai đỉnh. Nếu gốc khác nhau, tức là hai đỉnh nằm trong hai tập khác nhau, chúng ta hợp hai tập lại bằng cách cho gốc của tập này làm cha của gốc tập kia (parent[root_j] = root_i). Việc này không tạo chu trình, nên hàm trả về true. Nếu gốc giống nhau, tức là hai đỉnh đã cùng tập, việc thêm cạnh sẽ tạo chu trình, hàm trả về false và không làm gì cả. (Phần tối ưu union by size/rank được bỏ qua trong ví dụ đơn giản này nhưng rất quan trọng cho hiệu suất thực tế).
kruskal_mst(int V, std::vector<Edge>& edges): Hàm chính thực hiện thuật toán Kruskal.
- Khởi tạo vector mst để lưu trữ các cạnh của cây bao trùm.
- Khởi tạo đối tượng DSU với V đỉnh.
- Sắp xếp: Sử dụng std::sort để sắp xếp vector edges dựa trên operator< đã định nghĩa trong struct Edge.
- Duyệt cạnh: Lặp qua từng cạnh trong danh sách đã sắp xếp.
- Kiểm tra & Hợp: Với mỗi cạnh (u, v), gọi dsu.unite(u, v). Nếu hàm này trả về true (tức là u và v ban đầu khác tập, và đã được hợp), nghĩa là thêm cạnh này không tạo chu trình và nó là cạnh rẻ nhất có thể để nối hai thành phần đó, nên thêm cạnh này vào mst.
- Điều kiện dừng: Thuật toán dừng khi mst có đủ V-1 cạnh, vì một cây với V đỉnh luôn có V-1 cạnh.
main(): Thiết lập đồ thị mẫu (số đỉnh V và danh sách cạnh edges) và gọi hàm kruskal_mst. In kết quả.

Cài đặt Prim với Priority Queue

Chúng ta cần biểu diễn đồ thị bằng danh sách kề và sử dụng std::priority_queue.

#include <iostream>
#include <vector>
#include <queue> // for priority_queue
#include <limits> // for numeric_limits

// --- Biểu diễn cạnh trong danh sách kề ---
// pair<int, int>: {đỉnh_đích, trọng số}
using Edge = std::pair<int, int>;
// pair<int, int>: {trọng số, đỉnh} - dùng cho priority queue (min-heap)
// priority_queue mặc định là max-heap, nên lưu {-trọng số, đỉnh} hoặc dùng greater<>
using WeightedNode = std::pair<int, int>;

// --- Thuật toán Prim ---
std::vector<Edge> prim_mst(int V, const std::vector<std::vector<Edge>>& adj) {
    // vector lưu trữ các cạnh của MST. Lưu {đỉnh_nguồn, đỉnh_đích}
    // Để đơn giản, ví dụ này chỉ tính tổng trọng số chứ không lưu chi tiết cạnh
    // Nếu muốn lưu cạnh, cần thêm logic theo dõi parent/edge_to

    std::priority_queue<WeightedNode, std::vector<WeightedNode>, std::greater<WeightedNode>> pq; // Min-priority queue: pair {trọng số, đỉnh}
    std::vector<int> min_cost(V, std::numeric_limits<int>::max()); // Chi phí nhỏ nhất để kết nối đỉnh i với cây đang xây dựng
    std::vector<bool> in_mst(V, false); // Mảng theo dõi đỉnh đã thuộc MST chưa

    // Chúng ta sẽ bắt đầu từ đỉnh 0
    int start_node = 0;
    min_cost[start_node] = 0;
    pq.push({0, start_node}); // Thêm đỉnh bắt đầu vào PQ với chi phí 0

    int total_weight = 0; // Tổng trọng số MST

    // Lặp cho đến khi PQ rỗng hoặc tất cả các đỉnh đã được thêm vào MST (V đỉnh)
    while (!pq.empty()) {
        // 1. Lấy ra đỉnh có chi phí nhỏ nhất từ PQ
        WeightedNode current = pq.top();
        pq.pop();

        int u = current.second; // Đỉnh hiện tại
        int weight_u = current.first; // Chi phí để thêm đỉnh u vào MST

        // Nếu đỉnh u đã thuộc MST rồi hoặc chi phí hiện tại lớn hơn chi phí min đã biết, bỏ qua
        // Việc này xử lý trường hợp "giảm khóa" trong Binary Heap bằng cách thêm bản sao mới
        if (in_mst[u]) {
            continue;
        }

        // Đỉnh u chưa thuộc MST, thêm nó vào MST
        in_mst[u] = true;
        total_weight += weight_u; // Cộng trọng số cạnh nối u vào MST

        // Nếu đã thêm đủ V đỉnh, dừng lại
        // Note: trong cài đặt này, chúng ta không lưu lại các cạnh, chỉ tính tổng trọng số.
        // Nếu cần lưu cạnh, cần thêm logic tại đây (ví dụ: lưu đỉnh cha hoặc cạnh nào nối u vào MST)

        // 2. Duyệt qua các đỉnh v kề với u
        for (const auto& edge : adj[u]) {
            int v = edge.first; // Đỉnh kề
            int weight_uv = edge.second; // Trọng số cạnh (u, v)

            // Nếu đỉnh v chưa thuộc MST và cạnh (u, v) có trọng số nhỏ hơn
            // chi phí hiện tại để kết nối v với cây đang xây dựng
            if (!in_mst[v] && weight_uv < min_cost[v]) {
                // Cập nhật chi phí cho v và thêm/cập nhật v vào PQ
                min_cost[v] = weight_uv;
                pq.push({weight_uv, v}); // Thêm vào PQ
                // Lưu ý: Nếu muốn lưu cạnh MST, tại đây có thể lưu parent[v] = u hoặc edge_to[v] = {u, v}
            }
        }
    }

    // Trả về tổng trọng số. Để trả về danh sách cạnh, cần sửa đổi code.
    // Ví dụ này chỉ minh họa logic chính của Prim dùng PQ.
    std::vector<Edge> dummy_result; // Trả về vector rỗng hoặc cần xây dựng lại logic lưu cạnh
    std::cout << "**MST (Prim) - Tổng trọng số:** " << total_weight << std::endl;
    return dummy_result; // Trả về rỗng vì code này chỉ tính tổng trọng số
}

int main() {
    int V = 4; // Số đỉnh
    // Biểu diễn đồ thị bằng danh sách kề: adj[u] = danh sách các cặp {đỉnh_kề, trọng số}
    std::vector<std::vector<Edge>> adj(V);
    adj[0].push_back({1, 10}); adj[1].push_back({0, 10});
    adj[0].push_back({2, 6});  adj[2].push_back({0, 6});
    adj[0].push_back({3, 5});  adj[3].push_back({0, 5});
    adj[1].push_back({3, 15}); adj[3].push_back({1, 15});
    adj[2].push_back({3, 4});  adj[3].push_back({2, 4});

    // Gọi hàm Prim (ví dụ này chỉ in tổng trọng số bên trong hàm)
    prim_mst(V, adj);

    // Để có kết quả như Kruskal (in danh sách cạnh), cần bổ sung mảng parent/edge_to trong Prim
    // và xây dựng vector<Edge> kết quả sau khi vòng lặp kết thúc.

    return 0;
}

Giải thích code Prim:

Biểu diễn đồ thị: Sử dụng std::vector<std::vector<Edge>> adj làm danh sách kề. adj[u] chứa danh sách các pair<int, int> {đỉnh_kề, trọng số} cho các cạnh đi từ đỉnh u. Vì đồ thị vô hướng, mỗi cạnh {u, v, w} được thêm vào cả adj[u] (dưới dạng {v, w}) và adj[v] (dưới dạng {u, w}).
WeightedNode: Định nghĩa kiểu pair<int, int> để lưu {-trọng số, đỉnh} hoặc {trọng số, đỉnh} trong priority queue. Sử dụng std::greater<WeightedNode> với {trọng số, đỉnh} tạo thành một min-priority queue, ưu tiên các cặp có trọng số nhỏ hơn.
min_cost: Vector lưu trữ chi phí nhỏ nhất hiện tại để kết nối mỗi đỉnh i (chưa thuộc MST) với cây bao trùm đang xây dựng. Ban đầu tất cả là vô cực.
in_mst: Vector boolean để đánh dấu đỉnh đã được thêm vào MST chưa.
pq: Hàng đợi ưu tiên lưu trữ các WeightedNode {chi phí, đỉnh}. PQ sẽ luôn giữ đỉnh chưa thuộc MST có chi phí kết nối thấp nhất ở trên cùng.
Khởi tạo: Chọn đỉnh 0 làm đỉnh bắt đầu, đặt min_cost[0] = 0 và thêm {0, 0} vào PQ.
Vòng lặp chính: Lặp cho đến khi PQ rỗng.
- Lấy đỉnh rẻ nhất: Lấy đỉnh u có chi phí kết nối thấp nhất từ PQ (pq.top(), rồi pq.pop()).
- Kiểm tra in_mst: Nếu đỉnh u đã được xử lý và thêm vào MST rồi (do cơ chế thêm bản sao vào PQ), bỏ qua.
- Thêm vào MST: Nếu u chưa thuộc MST, đánh dấu in_mst[u] = true và cộng weight_u (chi phí để nối u vào MST) vào tổng trọng số.
- Cập nhật láng giềng: Duyệt qua tất cả các cạnh {v, weight_uv} kề với đỉnh u.
- Kiểm tra và thêm vào PQ: Nếu đỉnh v chưa thuộc MST và weight_uv nhỏ hơn chi phí hiện tại min_cost[v], cập nhật min_cost[v] = weight_uv và thêm {weight_uv, v} vào PQ. Thao tác này hiệu quả như "giảm khóa": nếu v đã có trong PQ với chi phí cũ, nó vẫn nằm đó, nhưng khi đến lượt nó được trích xuất, điều kiện in_mst[v] sẽ bỏ qua nó; phiên bản mới với chi phí thấp hơn sẽ được trích xuất sau này.
Kết quả: Ví dụ này chỉ tính tổng trọng số. Để trả về danh sách cạnh, bạn sẽ cần thêm một mảng parent hoặc edge_to để lưu lại cạnh nào đã được sử dụng để nối mỗi đỉnh vào MST, và xây dựng danh sách cạnh sau khi vòng lặp kết thúc.

So sánh mã nguồn

Kruskal: Mã nguồn tập trung vào việc quản lý các cạnh (sắp xếp, duyệt) và sử dụng DSU để theo dõi các thành phần liên thông. Logic chính nằm ở vòng lặp qua các cạnh và kiểm tra dsu.unite().
Prim: Mã nguồn tập trung vào việc quản lý các đỉnh (visited, min_cost) và sử dụng Priority Queue để quản lý các cạnh "xuyên biên giới" giữa cây đang xây dựng và phần còn lại. Logic chính nằm ở vòng lặp lấy đỉnh từ PQ và cập nhật các láng giềng.

Cả hai đều có điểm mạnh riêng. Nếu bạn đã quen với DSU, Kruskal có thể trực quan. Nếu bạn đã quen với Priority Queue và biểu diễn đồ thị, Prim có vẻ dễ dàng hơn.

Khi nào chọn thuật toán nào?

Dựa trên phân tích hiệu quả:

Chọn Kruskal khi:
- Đồ thị rất thưa (số cạnh E nhỏ hơn đáng kể so với V^2).
- Bạn cần tìm Minimum Spanning Forest (MSF) trên đồ thị không liên thông.
- Bạn đã quen thuộc hoặc muốn học cách sử dụng cấu trúc dữ liệu DSU.
Chọn Prim (với Binary Heap) khi:
- Đồ thị thưa hoặc trung bình, hiệu quả tương đương Kruskal.
- Bạn đã quen thuộc với việc biểu diễn đồ thị bằng danh sách kề và sử dụng hàng đợi ưu tiên. Cài đặt có thể cảm thấy tự nhiên hơn.
Chọn Prim (với cài đặt O(V^2)) khi:
- Đồ thị cực kỳ dày đặc (E ≈ V^2). Đây là trường hợp duy nhất mà cài đặt Prim đơn giản lại vượt trội hơn các phiên bản dùng Heap hoặc Kruskal.

Trong thực tế, đối với hầu hết các bài toán trên đồ thị thưa hoặc trung bình (phổ biến hơn trong nhiều ứng dụng), cả Kruskal O(E log E) và Prim O(E log V) đều rất hiệu quả và sự khác biệt về thời gian chạy có thể không đáng kể trừ khi đồ thị rất lớn. Việc lựa chọn có thể dựa nhiều vào sở thích cá nhân, sự quen thuộc với cấu trúc dữ liệu, hoặc tính chất cụ thể của bài toán (ví dụ: cần MSF).

Bài tập ví dụ:

Chuyến đi trên cây

Trong một buổi luyện tập IELTS READING, FullHouse Dev được giao một bài toán thú vị về lý thuyết đồ thị. Họ phải giúp nhân vật Alice ngăn cản Bob thực hiện các chuyến đi trên một cây bằng cách xóa ít cạnh nhất có thể.

Bài toán

Bob dự định thực hiện \(m\) chuyến đi trên một cây. Trong mỗi chuyến đi, anh ta di chuyển từ đỉnh \(u\) đến đỉnh \(v\) theo đường đi đơn giản giữa hai đỉnh này. Alice muốn ngăn cản Bob thực hiện bất kỳ chuyến đi nào trong số \(m\) chuyến đi này. Trước khi Bob thức dậy, Alice lên kế hoạch xóa một số cạnh của cây sao cho Bob không thể thực hiện được bất kỳ chuyến đi nào. Nhiệm vụ của FullHouse Dev là tìm số cạnh ít nhất mà Alice cần phải xóa.

INPUT FORMAT:

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) - số đỉnh của cây và số chuyến đi Bob muốn thực hiện.
\(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) - biểu thị một cạnh của cây.
\(m\) dòng cuối cùng, mỗi dòng chứa hai số nguyên \(u\) và \(v\) - biểu thị điểm bắt đầu và điểm kết thúc của mỗi chuyến đi.

OUTPUT FORMAT:

In ra số cạnh ít nhất mà Alice cần xóa để ngăn cản tất cả các chuyến đi của Bob.

Ràng buộc:

\(1 \leq n \leq 10^5\)
\(1 \leq m \leq 10^5\)
\(1 \leq u, v \leq n\)

Ví dụ

INPUT

OUTPUT

Giải thích

Trong ví dụ trên, cây có 5 đỉnh và Bob muốn thực hiện 2 chuyến đi:

Chuyến đi từ đỉnh 2 đến đỉnh 3
Chuyến đi từ đỉnh 3 đến đỉnh 4

Nếu Alice xóa cạnh (1, 3), Bob sẽ không thể thực hiện được cả hai chuyến đi. Do đó, đáp án là 1 - chỉ cần xóa một cạnh là đủ để ngăn cản tất cả các chuyến đi của Bob. Okay, đây là hướng dẫn giải bài toán "Chuyến đi trên cây" với các bước chi tiết và các kỹ thuật cần sử dụng.

Bài toán yêu cầu tìm số lượng cạnh ít nhất cần xóa trên cây để ngăn chặn tất cả m chuyến đi của Bob. Mỗi chuyến đi là một đường đi đơn giản giữa hai đỉnh u và v. Để ngăn một chuyến đi, ta cần xóa ít nhất một cạnh trên đường đi giữa u và v.

Phân tích và Hướng tiếp cận:

Đường đi trên cây: Trên cây, giữa hai đỉnh bất kỳ chỉ tồn tại duy nhất một đường đi đơn giản. Xóa bất kỳ cạnh nào trên đường đi này sẽ làm hai đỉnh đó bị ngắt kết nối, chuyến đi không thể thực hiện.
Mục tiêu: Tìm tập cạnh có kích thước nhỏ nhất sao cho mỗi trong m đường đi đã cho đều chứa ít nhất một cạnh trong tập này.
Kỹ thuật: Bài toán này có thể giải quyết hiệu quả trên cây bằng cách kết hợp:
- Lowest Common Ancestor (LCA): Đường đi giữa hai đỉnh u và v đi từ u lên tới LCA của chúng (l = LCA(u, v)) rồi từ l xuống v. Mọi cạnh trên đường đi này đều nằm trên đường đi từ u lên gốc và đường đi từ v lên gốc, nhưng không nằm trên đường đi từ l lên gốc (hoặc từ parent(l) lên gốc).
- Difference Array on Tree: Ta có thể "đánh dấu" các cạnh nằm trên mỗi đường đi bằng cách sử dụng một mảng sai phân (difference array) trên các đỉnh và tính tổng tích lũy bằng DFS.
- Dynamic Programming (DP) trên cây / Greedy: Sử dụng một thuật toán tham lam (greedy) kết hợp với duyệt cây (DFS) để quyết định xóa cạnh nào từ dưới lên.

Các bước giải:

Đọc Input và Xây dựng Cây:
- Đọc n và m.
- Xây dựng danh sách kề (adjacency list) biểu diễn cây từ n-1 cạnh đầu tiên.
Tiền xử lý cho LCA:
- Chọn một đỉnh gốc tùy ý (ví dụ, đỉnh 1).
- Thực hiện một DFS từ gốc để tính:
  - Độ sâu (depth) của mỗi đỉnh.
  - Đỉnh cha trực tiếp (parent[u][0]) của mỗi đỉnh u.
- Sử dụng kỹ thuật Binary Lifting để xây dựng bảng parent[u][j] (đỉnh tổ tiên thứ 2^j của u) để tính LCA hiệu quả.
Đánh dấu Đường đi bằng Mảng Sai phân (Difference Array):
- Khởi tạo một mảng diff có kích thước n+1 với tất cả giá trị bằng 0.
- Với mỗi chuyến đi (u, v):
  - Tìm l = LCA(u, v).
  - Tăng diff[u] thêm 1.
  - Tăng diff[v] thêm 1.
  - Giảm diff[l] đi 1.
  - Nếu l không phải gốc (có đỉnh cha), giảm diff[parent[l][0]] đi 1.
- Sau khi xử lý tất cả m chuyến đi, giá trị cuối cùng của diff[u] sẽ được sử dụng trong bước tiếp theo.
Tính Tổng Tích Lũy và Quyết định Xóa Cạnh bằng DFS (Post-order):
- Khởi tạo biến total_removed_edges = 0.
- Thực hiện một DFS theo thứ tự hậu duệ (post-order traversal) từ gốc. Hàm DFS (ví dụ: DFS(u, p)) cho đỉnh hiện tại u và đỉnh cha p:
  - Gọi đệ quy hàm DFS cho tất cả các con v của u (với v != p). Tổng các giá trị trả về từ các cuộc gọi đệ quy này (paths_from_children_up) biểu thị số lượng đường đi bắt đầu trong các cây con của u và cần đi lên qua u, mà chưa bị ngắt quãng bởi các cạnh trong các cây con đó.
  - Tính tổng các đường đi đi lên qua u: paths_crossing_edge_above = diff[u] + paths_from_children_up. (Sử dụng cách đánh dấu +1,+1,-1,-1, giá trị diff[u] + sum(DFS(v,u)) cho mọi con v của u CHÍNH LÀ số lượng đường đi BẮT BUỘC phải đi qua cạnh nối u với p và có một đầu mút nằm trong cây con gốc u).
  - Nếu u không phải là gốc (p != 0) VÀ paths_crossing_edge_above > 0:
    - Điều này có nghĩa là có paths_crossing_edge_above đường đi xuất phát từ cây con gốc u (hoặc tại u) cần đi lên qua cạnh (p, u) và chưa bị ngắt quãng ở dưới.
    - Để ngăn chặn các đường đi này với số cạnh ít nhất, ta phải xóa cạnh (p, u). Đây là điểm thấp nhất có thể xóa để ngăn tất cả các đường đi này đi lên.
    - Tăng total_removed_edges lên 1.
    - Trả về 0. (Các đường đi này đã bị ngắt tại cạnh (p, u), chúng không cần phải đi lên nữa).
  - Ngược lại (nếu u là gốc HOẶc paths_crossing_edge_above <= 0):
    - Trả về paths_crossing_edge_above. (Nếu u là gốc, các đường đi có LCA tại gốc không cần đi lên nữa. Nếu giá trị <= 0, không có đường đi thuần túy cần đi lên qua cạnh (p, u) từ cây con này sau khi tính cả các điểm cuối/LCA tại u).
Kết quả:
- Gọi hàm DFS(1, 0) (hoặc DFS(gốc, đỉnh_giả)).
- Giá trị cuối cùng của total_removed_edges là đáp án.

Giải thích thêm về Logic DP:

Mảng diff sau khi xử lý các chuyến đi và tổng tích lũy bằng DFS (ví dụ: count[u] = diff[u] + sum(count[v] for child v)) sẽ cho biết số lượng đường đi đi qua cạnh nối u với cha nó (parent(u)). Cụ thể hơn với cách đánh dấu +1/+1/-1/-1, count[u] là số đường đi có ĐÚNG MỘT đầu mút nằm trong cây con gốc u. Đây chính là số đường đi sử dụng cạnh (parent(u), u).

Hàm DFS(u, p) trong bước 4 sử dụng ý tưởng này. Nó tính toán số lượng các đường đi xuất phát từ cây con u mà phải đi lên qua cạnh (p, u) và vẫn còn nguyên vẹn (chưa bị xóa cạnh ở dưới). Nếu số này lớn hơn 0, cạnh (p, u) là điểm "nút cổ chai" thấp nhất cho những đường đi này. Xóa nó là lựa chọn tối ưu để ngăn tất cả chúng bằng MỘT cạnh. Sau khi xóa, những đường đi này không cần phải được tính là cần cắt ở các cạnh phía trên nữa, nên hàm trả về 0. Nếu số này là 0 hoặc âm (do hiệu ứng của điểm LCA ở trên), không có đường đi nào từ cây con u cần đi lên qua (p, u) mà chưa được xử lý, nên không cần xóa (p, u) vì lý do này, và không có đường đi nào cần đi lên qua p từ nhánh u.

Kỹ thuật này đảm bảo mỗi đường đi được "bao phủ" bởi một cạnh bị xóa. Khi đi từ dưới lên, ta xóa cạnh (p, u) ngay khi phát hiện có đường đi từ cây con u cần đi lên qua đó và chưa bị chặn. Điều này đảm bảo tính tối thiểu vì ta luôn cố gắng xóa cạnh thấp nhất có thể trên đường đi.

Lưu ý cài đặt:

Kích thước mảng parent cho binary lifting phụ thuộc vào log2(N). Với N=10^5, log2(10^5) \approx 16.6, nên kích thước 18 hoặc 20 là đủ.
Xử lý trường hợp gốc cây (parent của gốc là 0 hoặc giá trị đặc biệt).
Đảm bảo sử dụng kiểu dữ liệu đủ lớn nếu số đường đi trên một cạnh có thể vượt quá giới hạn của int.

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

Comments

There are no comments at the moment.