Bài 17.3. Cây khung nhỏ nhất dùng tham lam

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

Trong thế giới muôn hình vạn trạng của đồ thị, chúng ta thường gặp phải những bài toán tối ưu hóa. Tưởng tượng bạn cần xây dựng một mạng lưới đường sá, cáp quang, hoặc đường ống dẫn nước sao cho tất cả các điểm cần kết nối đều được liên thông, và tổng chi phí xây dựng là nhỏ nhất. Đây chính là lúc khái niệm Cây khung nhỏ nhất (Minimum Spanning Tree - MST) tỏa sáng!

Trong bài viết này, chúng ta sẽ cùng nhau tìm hiểu về MST và đặc biệt là cách tiếp cận tham lam (greedy) để giải quyết bài toán này. Phương pháp tham lam thường mang lại những giải thuật đơn giản và hiệu quả đáng ngạc nhiên cho nhiều bài toán tối ưu, và MST là một ví dụ kinh điển.

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

Đầu tiên, hãy làm rõ một vài khái niệm:

Đồ thị có trọng số (Weighted Graph): Là một đồ thị trong đó mỗi cạnh được gán một giá trị số, gọi là trọng số. Trọng số này thường biểu diễn chi phí, khoảng cách, thời gian, v.v.
Cây khung (Spanning Tree): Cho một đồ thị vô hướng, liên thông gồm V đỉnh. Một cây khung là một đồ thị con của đồ thị ban đầu, bao gồm tất cả V đỉnh và chỉ sử dụng một số cạnh của đồ thị ban đầu sao cho đồ thị con này là một cây (nghĩa là liên thông và không có chu trình). Một cây khung của đồ thị V đỉnh luôn có chính xác V-1 cạnh.
Cây khung nhỏ nhất (Minimum Spanning Tree - MST): Đối với đồ thị có trọng số, cây khung nhỏ nhất 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 tất cả các cây khung có thể có của đồ thị đó.

Bài toán của chúng ta là: Cho một đồ thị vô hướng, liên thông, có trọng số, hãy tìm một cây khung nhỏ nhất của nó.

Tại sao lại là "Tham Lam"?

Giải thuật tham lam hoạt động dựa trên nguyên tắc: Tại mỗi bước, đưa ra lựa chọn tối ưu cục bộ (best immediate choice) với hy vọng rằng chuỗi các lựa chọn tối ưu cục bộ sẽ dẫn đến một giải pháp tối ưu toàn cục.

Nghe có vẻ đơn giản, thậm chí hơi liều lĩnh, phải không? Không phải lúc nào phương pháp tham lam cũng hoạt động cho mọi bài toán tối ưu. Tuy nhiên, đối với bài toán tìm MST, may mắn thay, chiến lược tham lam lại cực kỳ hiệu quả! Có hai giải thuật tham lam kinh điển để tìm MST: Giải thuật Kruskal và Giải thuật Prim. Cả hai đều dựa trên nguyên tắc tham lam, nhưng ở hai góc nhìn hơi khác nhau.

Chúng ta sẽ đi sâu vào từng giải thuật và xem cách chúng áp dụng nguyên tắc tham lam như thế nào.

Giải thuật Kruskal: Lựa chọn cạnh rẻ nhất

Ý tưởng cốt lõi của Kruskal là: Luôn chọn cạnh có trọng số nhỏ nhất trong số các cạnh còn lại, 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 đó.

Đây rõ ràng là một chiến lược tham lam: ở mỗi bước, chúng ta chỉ quan tâm đến cạnh rẻ nhất hiện có mà không làm hỏng cấu trúc cây (không tạo chu trình).

Các bước thực hiện giải thuật Kruskal:

Sắp xếp: Sắp xếp tất cả các cạnh của đồ thị theo trọng số tăng dần.
Khởi tạo: Tạo một tập hợp rỗng để chứa các cạnh của cây khung nhỏ nhất. Mỗi đỉnh ban đầu được coi là một thành phần liên thông riêng biệt.
Duyệt cạnh: Lần lượt xét các cạnh theo thứ tự đã sắp xếp.
Kiểm tra chu trình: Với mỗi cạnh (u, v) có trọng số w, kiểm tra xem đỉnh u và đỉnh v có thuộc cùng một thành phần liên thông trong tập hợp các cạnh đã chọn hay không.
- Nếu u và v không thuộc cùng một thành phần liên thông (nghĩa là thêm cạnh (u, v) sẽ không tạo chu trình), thì thêm cạnh (u, v) vào tập hợp các cạnh của MST và hợp nhất (union) hai thành phần liên thông chứa u và v thành một.
- Nếu u và v đã thuộc cùng một thành phần liên thông (nghĩa là thêm cạnh (u, v) sẽ tạo chu trình), thì bỏ qua cạnh này.
Kết thúc: Lặp lại bước 3 và 4 cho đến khi tập hợp các cạnh của MST chứa V-1 cạnh (với V là số đỉnh). Khi đó, chúng ta đã có cây khung nhỏ nhất.

Để kiểm tra xem hai đỉnh có thuộc cùng một thành phần liên thông hay không và để hợp nhất các thành phần liên thông một cách hiệu quả, chúng ta cần sử dụng một cấu trúc dữ liệu đặc biệt gọi là Disjoint Set Union (DSU), hay còn gọi là Union-Find.

Disjoint Set Union (DSU) - Công cụ đắc lực cho Kruskal

DSU quản lý một tập hợp các phần tử được chia thành các tập hợp con không giao nhau (disjoint sets). Nó hỗ trợ hai thao tác chính:

find(i): Trả về đại diện (thường là gốc của cây) của tập hợp chứa phần tử i. Hai phần tử thuộc cùng một tập hợp khi và chỉ khi find() của chúng trả về cùng một giá trị.
unite(i, j): Hợp nhất tập hợp chứa i và tập hợp chứa j thành một tập hợp duy nhất.

Với DSU, bước kiểm tra chu trình của Kruskal trở thành: Nếu find(u) != find(v), thêm cạnh (u, v) và gọi unite(u, v).

Cài đặt Kruskal bằng C++

Chúng ta cần một cấu trúc để lưu trữ cạnh, một hàm so sánh để sắp xếp cạnh và cài đặt DSU.

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

// Cấu trúc biểu diễn một cạnh
struct Edge {
    int u, v;    // Hai đỉnh nối bởi cạnh
    int weight;  // Trọng số của cạnh

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

// Cài đặt Disjoint Set Union (DSU)
struct DSU {
    std::vector<int> parent; // Mảng lưu cha của mỗi phần tử

    DSU(int n) {
        parent.resize(n);
        // Ban đầu, mỗi phần tử là gốc của tập hợp riêng nó
        std::iota(parent.begin(), parent.end(), 0); // parent[i] = i
    }

    // Tìm gốc của tập hợp chứa phần tử i (có Path Compression)
    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]); // Path compression
    }

    // Hợp nhất hai tập hợp chứa i và j (có Union by Rank/Size - ở đây đơn giản là gộp cây)
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j; // Gộp cây gốc root_i vào cây gốc root_j
        }
    }
};

int main() {
    int V, E; // V: số đỉnh, E: số cạnh
    std::cout << "Nhap so dinh va so canh: ";
    std::cin >> V >> E;

    std::vector<Edge> edges(E);
    std::cout << "Nhap cac canh (u, v, trong so):\n";
    for (int i = 0; i < E; ++i) {
        std::cin >> edges[i].u >> edges[i].v >> edges[i].weight;
        // Điều chỉnh đỉnh về chỉ số 0-based nếu nhập 1-based
        edges[i].u--; 
        edges[i].v--;
    }

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

    // Bước 2: Khởi tạo DSU
    DSU dsu(V);

    std::vector<Edge> mst_edges; // Lưu các cạnh của MST
    long long total_weight = 0;  // Tổng trọng số của MST
    int edges_in_mst = 0;        // Đếm số cạnh đã thêm vào MST

    // Bước 3, 4: Duyệt các cạnh đã sắp xếp
    std::cout << "\Cac buoc cua Kruskal:\n";
    for (const auto& edge : edges) {
        // Nếu đã đủ V-1 cạnh thì dừng
        if (edges_in_mst == V - 1) break;

        int root_u = dsu.find(edge.u);
        int root_v = dsu.find(edge.v);

        // Kiểm tra xem hai đỉnh có thuộc cùng thành phần liên thông không
        if (root_u != root_v) {
            // Nếu không, thêm cạnh này vào MST
            mst_edges.push_back(edge);
            total_weight += edge.weight;
            dsu.unite(edge.u, edge.v); // Hợp nhất hai thành phần
            edges_in_mst++;
            std::cout << "  Them canh (" << edge.u+1 << "-" << edge.v+1 << ") trong so " << edge.weight << " vao MST.\n";
        } else {
             std::cout << "  Bo qua canh (" << edge.u+1 << "-" << edge.v+1 << ") trong so " << edge.weight << " vi tao chu trinh.\n";
        }
    }

    // Kiểm tra xem đồ thị có liên thông không (đủ V-1 cạnh trong MST)
    if (edges_in_mst != V - 1) {
        std::cout << "\nDo thi khong lien thong, khong the tao cay khung.\n";
    } else {
        std::cout << "\nDa tim thay Cay khung nho nhat (MST).\n";
        std::cout << "Tong trong so cua MST: " << total_weight << std::endl;
        std::cout << "Cac canh trong MST:\n";
        for (const auto& edge : mst_edges) {
            std::cout << "(" << edge.u+1 << "-" << edge.v+1 << ") - Trong so: " << edge.weight << std::endl;
        }
    }

    return 0;
}

Giải thích code Kruskal:

struct Edge: Định nghĩa một cạnh với hai đỉnh u, v và trọng số weight. Toán tử < được nạp chồng để std::sort có thể sắp xếp các cạnh dựa trên trọng số.
struct DSU:
- parent: Vector parent lưu trữ mối quan hệ cha-con. parent[i] == i nghĩa là i là gốc của tập hợp chứa nó.
- DSU(int n): Constructor khởi tạo n tập hợp, mỗi tập hợp chứa một đỉnh duy nhất (từ 0 đến n-1).
- find(int i): Tìm gốc của tập hợp chứa i. Kỹ thuật path compression được sử dụng để làm phẳng cây DSU, cải thiện đáng kể hiệu suất cho các lần gọi find sau này trên cùng một tập hợp.
- unite(int i, int j): Hợp nhất hai tập hợp. Phiên bản đơn giản này chỉ gán gốc của tập hợp i làm con của gốc tập hợp j. Các cài đặt DSU hiệu quả hơn sẽ dùng union by rank hoặc union by size để giữ cho cây DSU cân bằng hơn.
main():
- Đọc số đỉnh V và số cạnh E.
- Đọc thông tin các cạnh và lưu vào vector edges. Lưu ý: Chúng ta điều chỉnh đỉnh về chỉ số 0-based (từ 0 đến V-1) để phù hợp với chỉ số mảng/vector trong C++.
- std::sort(edges.begin(), edges.end());: Sắp xếp vector edges dựa trên toán tử < đã định nghĩa trong struct Edge.
- DSU dsu(V);: Khởi tạo DSU cho V đỉnh.
- Vòng lặp chính duyệt qua các cạnh đã sắp xếp. Đối với mỗi cạnh (u, v):
  - dsu.find(edge.u) và dsu.find(edge.v): Tìm gốc của hai đỉnh u và v.
  - if (root_u != root_v): Nếu gốc khác nhau, nghĩa là u và v hiện chưa liên thông. Thêm cạnh này vào mst_edges, cộng trọng số vào total_weight, và gọi dsu.unite(edge.u, edge.v) để hợp nhất hai thành phần.
  - edges_in_mst++: Tăng số cạnh đã thêm. Khi đạt V-1 cạnh, MST đã hoàn thành.
- In ra kết quả hoặc thông báo nếu đồ thị không liên thông.

Ví dụ minh họa Kruskal

Xét đồ thị 5 đỉnh (1..5) và các cạnh với trọng số như sau: (1,2,3), (1,3,2), (1,4,5), (2,3,4), (2,4,2), (3,4,4), (3,5,6), (4,5,3).

Sắp xếp cạnh: (1,3,2), (2,4,2), (1,2,3), (4,5,3), (2,3,4), (3,4,4), (1,4,5), (3,5,6)
DSU khởi tạo: {1}, {2}, {3}, {4}, {5}
Duyệt và thêm cạnh:
- Cạnh (1,3,2): find(1)=1, find(3)=3. Khác nhau. Thêm (1,3). unite(1,3). DSU: {1,3}, {2}, {4}, {5}. MST: {(1,3)}, cost=2.
- Cạnh (2,4,2): find(2)=2, find(4)=4. Khác nhau. Thêm (2,4). unite(2,4). DSU: {1,3}, {2,4}, {5}. MST: {(1,3), (2,4)}, cost=2+2=4.
- Cạnh (1,2,3): find(1)=1, find(2)=2. Khác nhau. Thêm (1,2). unite(1,2). DSU: {1,2,3}, {2,4} -> hợp nhất 1,3 và 2,4. Sau unite(find(1), find(2)) = unite(1,2) (giả sử root(1) thành con root(2)), DSU có thể là {1,2,3,4}, {5}. MST: {(1,3), (2,4), (1,2)}, cost=4+3=7.
- Cạnh (4,5,3): find(4)=1, find(5)=5 (giả sử root của {1,2,3,4} là 1). Khác nhau. Thêm (4,5). unite(4,5). DSU: {1,2,3,4,5}. MST: {(1,3), (2,4), (1,2), (4,5)}, cost=7+3=10.
- Đã có 4 cạnh (V-1 = 5-1 = 4). Dừng lại.

MST tìm được gồm các cạnh: (1,3), (2,4), (1,2), (4,5) với tổng trọng số là 10.

Kruskal hoạt động tốt khi số cạnh ít so với số đỉnh (E nhỏ). Thời gian chạy chủ yếu phụ thuộc vào việc sắp xếp cạnh (O(E log E)) và các thao tác DSU (O(E * alpha(V)), với alpha là hàm inverse Ackermann tăng cực kỳ chậm, coi như hằng số). Tổng cộng là O(E log E).

Giải thuật Prim: Mở rộng cây hiện tại

Trong khi Kruskal xây dựng MST bằng cách thêm các cạnh rẻ nhất trên toàn đồ thị, Prim lại tiếp cận khác: Nó bắt đầu từ một đỉnh bất kỳ và dần dần mở rộng cây hiện tại bằng cách thêm cạnh rẻ nhất nối một đỉnh trong cây với một đỉnh bên ngoài cây.

Đây cũng là một chiến lược tham lam: tại mỗi bước, chúng ta chọn kết nối rẻ nhất để "kéo" một đỉnh mới vào cây đang xây dựng.

Các bước thực hiện giải thuật Prim:

Khởi tạo: Chọn một đỉnh bất kỳ làm đỉnh bắt đầu. Đặt đỉnh này vào tập hợp các đỉnh trong MST. Gán trọng số kết nối đến đỉnh này là 0, và trọng số kết nối đến các đỉnh khác là vô cùng.
Lặp lại: Lặp lại V-1 lần (hoặc cho đến khi tất cả các đỉnh đều được thêm vào MST):
- Tìm cạnh (u, v) có trọng số nhỏ nhất, trong đó u là đỉnh trong MST và v là đỉnh ngoài MST.
- Thêm cạnh (u, v) và đỉnh v vào MST.
Kết thúc: Sau V-1 lần lặp, tất cả V đỉnh đã được thêm vào MST.

Để tìm cạnh (u, v) có trọng số nhỏ nhất một cách hiệu quả ở mỗi bước, chúng ta có thể sử dụng Hàng đợi ưu tiên (Priority Queue). Hàng đợi ưu tiên sẽ lưu trữ các cạnh (hoặc các đỉnh cùng với trọng số kết nối nhỏ nhất đến cây hiện tại) và cho phép ta nhanh chóng lấy ra phần tử có trọng số nhỏ nhất.

Sử dụng Priority Queue cho Prim

Chúng ta có thể lưu trữ các cặp (trọng số, đỉnh đích) trong hàng đợi ưu tiên. Ban đầu, hàng đợi chỉ chứa {0, đỉnh_bắt_đầu}. Khi một đỉnh u được thêm vào cây, chúng ta duyệt qua tất cả các cạnh nối u với các đỉnh v chưa có trong cây. Đối với mỗi cạnh (u, v) với trọng số w, nếu trọng số w này nhỏ hơn trọng số kết nối nhỏ nhất hiện tại được biết đến từ cây đến đỉnh v, chúng ta cập nhật thông tin cho đỉnh v và thêm {w, v} vào hàng đợi ưu tiên.

Cài đặt Prim bằng C++

Chúng ta cần biểu diễn đồ thị bằng danh sách kề (adjacency list), một mảng để lưu trọng số kết nối nhỏ nhất từ cây đến từng đỉnh, và một mảng để đánh dấu đỉnh đã vào cây.

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

// Cấu trúc biểu diễn một cạnh trong danh sách kề
struct EdgeAdj {
    int to;      // Đỉnh đích
    int weight;  // Trọng số

    // Constructor
    EdgeAdj(int t, int w) : to(t), weight(w) {}
};

// Pair cho priority queue: {weight, vertex}
// priority_queue mặc định là max-heap, dùng greater để thành min-heap
typedef std::pair<int, int> WeightVertexPair;

int main() {
    int V, E; // V: số đỉnh, E: số cạnh
    std::cout << "Nhap so dinh va so canh: ";
    std::cin >> V >> E;

    // Biểu diễn đồ thị bằng danh sách kề
    std::vector<std::vector<EdgeAdj>> adj(V);
    std::cout << "Nhap cac canh (u, v, trong so): (u, v la 1-based)\n";
    for (int i = 0; i < E; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        // Điều chỉnh đỉnh về chỉ số 0-based
        u--; 
        v--;
        adj[u].push_back(EdgeAdj(v, w));
        adj[v].push_back(EdgeAdj(u, w)); // Đồ thị vô hướng
    }

    // Mảng lưu trữ trọng số nhỏ nhất để kết nối từ cây MST hiện tại đến mỗi đỉnh
    std::vector<int> min_weight(V, std::numeric_limits<int>::max());

    // Mảng theo dõi các đỉnh đã được thêm vào MST
    std::vector<bool> in_mst(V, false);

    // Tổng trọng số của MST
    long long total_weight = 0;

    // Hàng đợi ưu tiên lưu trữ các cặp {trọng số, đỉnh}
    // Sắp xếp theo trọng số tăng dần (min-heap)
    std::priority_queue<WeightVertexPair, std::vector<WeightVertexPair>, std::greater<WeightVertexPair>> pq;

    // Bước 1: Chọn đỉnh 0 làm đỉnh bắt đầu (có thể chọn đỉnh bất kỳ)
    int start_node = 0;
    min_weight[start_node] = 0;
    pq.push({0, start_node});

    std::cout << "\Cac buoc cua Prim (bat dau tu dinh " << start_node + 1 << "):\n";

    // Lặp cho đến khi tất cả các đỉnh được thêm vào MST (hoặc PQ rỗng)
    while (!pq.empty()) {
        // Lấy cạnh có trọng số nhỏ nhất từ PQ
        WeightVertexPair current = pq.top();
        pq.pop();

        int w = current.first; // Trọng số của cạnh
        int u = current.second; // Đỉnh kết nối đến cây MST

        // Nếu đỉnh u đã ở trong MST rồi thì bỏ qua (có thể có các entry cũ trong PQ)
        if (in_mst[u]) {
             std::cout << "  Bo qua dinh " << u+1 << " voi trong so " << w << " vi da co trong MST.\n";
            continue;
        }

        // Thêm đỉnh u vào MST
        in_mst[u] = true;
        total_weight += w;
        std::cout << "  Them dinh " << u+1 << " vao MST voi trong so ket noi nho nhat la " << w << ".\n";


        // Duyệt qua tất cả các cạnh của đỉnh u
        for (const auto& edge : adj[u]) {
            int v = edge.to;      // Đỉnh kề với u
            int edge_w = edge.weight; // Trọng số cạnh (u, v)

            // Nếu đỉnh v chưa có trong MST VÀ trọng số cạnh (u, v) nhỏ hơn trọng số nhỏ nhất hiện tại để kết nối đến v
            if (!in_mst[v] && edge_w < min_weight[v]) {
                min_weight[v] = edge_w; // Cập nhật trọng số nhỏ nhất để đến v
                pq.push({edge_w, v});    // Thêm/cập nhật v vào PQ
                // std::cout << "    Cap nhat trong so den dinh " << v+1 << " thanh " << edge_w << ", them vao PQ.\n";
            }
        }
    }

     // Kiểm tra xem tất cả các đỉnh đã được thăm (đồ thị liên thông)
    bool all_visited = true;
    for(int i = 0; i < V; ++i) {
        if(!in_mst[i]) {
            all_visited = false;
            break;
        }
    }

    if (!all_visited) {
        std::cout << "\nDo thi khong lien thong, khong the tao cay khung bao trum tat ca cac dinh.\n";
    } else {
        std::cout << "\nDa tim thay Cay khung nho nhat (MST).\n";
        std::cout << "Tong trong so cua MST: " << total_weight << std::endl;
        // Prim không trực tiếp lưu các cạnh, bạn cần thêm logic để lưu nếu muốn
        // Ví dụ: thêm một mảng `parent_edge` để lưu cạnh nào đã được dùng để thêm đỉnh
    }


    return 0;
}

Giải thích code Prim:

struct EdgeAdj: Cấu trúc đơn giản cho danh sách kề, lưu đỉnh đích và trọng số cạnh.
adj: std::vector<std::vector<EdgeAdj>> biểu diễn đồ thị bằng danh sách kề. adj[u] chứa vector các EdgeAdj nối từ đỉnh u.
min_weight: std::vector<int> lưu trữ trọng số cạnh có trọng số nhỏ nhất từ một đỉnh trong MST hiện tại đến mỗi đỉnh bên ngoài MST. Ban đầu tất cả là vô cùng (std::numeric_limits<int>::max()).
in_mst: std::vector<bool> đánh dấu đỉnh nào đã được thêm vào MST.
pq: std::priority_queue lưu trữ các cặp {trọng số, đỉnh}. Trọng số ở đây là trọng số cạnh nhỏ nhất tìm được từ cây MST đến đỉnh này. std::greater<WeightVertexPair> biến nó thành min-heap (phần tử nhỏ nhất ở top).
Khởi tạo: Chọn một đỉnh start_node (ở đây là 0). Gán min_weight[start_node] = 0 và đẩy {0, start_node} vào PQ.
Vòng lặp chính: Lặp khi PQ còn phần tử.
- pq.top() và pq.pop(): Lấy cặp {trọng số, đỉnh} có trọng số nhỏ nhất ra khỏi PQ. Đây là đỉnh u sẽ được thêm vào MST thông qua cạnh có trọng số w.
- if (in_mst[u]) continue;: Quan trọng! PQ có thể chứa các cặp cũ ứng với cùng một đỉnh u nhưng có trọng số lớn hơn (do đỉnh u đã được tìm thấy với trọng số nhỏ hơn trước đó và đã được thêm vào MST). Nếu đỉnh đã vào MST rồi, bỏ qua.
- in_mst[u] = true; total_weight += w;: Đánh dấu u đã vào MST và cộng trọng số cạnh dùng để thêm u vào tổng trọng số.
- Duyệt các cạnh kề của đỉnh u: Đối với mỗi đỉnh kề v với trọng số edge_w:
  - !in_mst[v] && edge_w < min_weight[v]: Nếu v chưa vào MST VÀ trọng số cạnh (u, v) nhỏ hơn trọng số nhỏ nhất đã biết để kết nối đến v.
  - min_weight[v] = edge_w; pq.push({edge_w, v});: Cập nhật min_weight[v] và đẩy cặp {edge_w, v} vào PQ. Điều này có nghĩa là chúng ta vừa tìm thấy một cách rẻ hơn để kết nối đỉnh v vào cây MST.
Kiểm tra liên thông: Sau vòng lặp, kiểm tra xem tất cả các đỉnh có được đánh dấu in_mst không để xác định đồ thị có liên thông hay không.

Ví dụ minh họa Prim

Sử dụng lại đồ thị 5 đỉnh (1..5) và các cạnh với trọng số như ví dụ Kruskal. (1,2,3), (1,3,2), (1,4,5), (2,3,4), (2,4,2), (3,4,4), (3,5,6), (4,5,3). Bắt đầu từ đỉnh 1 (chỉ số 0).

Khởi tạo: min_weight = {0, inf, inf, inf, inf}, in_mst = {F, F, F, F, F}, total_weight = 0. PQ: {0, 0} (0-based index).
Bước 1:
- PQ: {0, 0}. Pop {0, 0}. u=0 (đỉnh 1). in_mst[0]=F. Mark in_mst[0]=T. total_weight += 0. Print "Thêm đỉnh 1".
- Duyệt cạnh từ đỉnh 0:
  - (0,1,3): v=1 (đỉnh 2), edge_w=3. !in_mst[1] (T) && 3 < min_weight[1] (inf). Update min_weight[1]=3. Push {3, 1} vào PQ.
  - (0,2,2): v=2 (đỉnh 3), edge_w=2. !in_mst[2] (T) && 2 < min_weight[2] (inf). Update min_weight[2]=2. Push {2, 2} vào PQ.
  - (0,3,5): v=3 (đỉnh 4), edge_w=5. !in_mst[3] (T) && 5 < min_weight[3] (inf). Update min_weight[3]=5. Push {5, 3} vào PQ.
- PQ: {2, 2}, {3, 1}, {5, 3} (min-heap).
Bước 2:
- PQ: {2, 2}, {3, 1}, {5, 3}. Pop {2, 2}. u=2 (đỉnh 3). in_mst[2]=F. Mark in_mst[2]=T. total_weight += 2. Print "Thêm đỉnh 3".
- Duyệt cạnh từ đỉnh 2:
  - (2,0,2): v=0 (đỉnh 1), edge_w=2. in_mst[0] (T). Bỏ qua.
  - (2,1,4): v=1 (đỉnh 2), edge_w=4. !in_mst[1] (T) && 4 < min_weight[1] (3). 4 < 3 là Sai. Bỏ qua.
  - (2,3,4): v=3 (đỉnh 4), edge_w=4. !in_mst[3] (T) && 4 < min_weight[3] (5). 4 < 5 là Đúng. Update min_weight[3]=4. Push {4, 3} vào PQ.
  - (2,4,6): v=4 (đỉnh 5), edge_w=6. !in_mst[4] (T) && 6 < min_weight[4] (inf). 6 < inf là Đúng. Update min_weight[4]=6. Push {6, 4} vào PQ.
- PQ: {3, 1}, {4, 3}, {5, 3}, {6, 4}.
Bước 3:
- PQ: {3, 1}, {4, 3}, {5, 3}, {6, 4}. Pop {3, 1}. u=1 (đỉnh 2). in_mst[1]=F. Mark in_mst[1]=T. total_weight += 3. Print "Thêm đỉnh 2".
- Duyệt cạnh từ đỉnh 1:
  - (1,0,3): v=0 (đỉnh 1). in_mst[0] (T). Bỏ qua.
  - (1,2,4): v=2 (đỉnh 3). in_mst[2] (T). Bỏ qua.
  - (1,3,2): v=3 (đỉnh 4). edge_w=2. !in_mst[3] (T) && 2 < min_weight[3] (4). 2 < 4 là Đúng. Update min_weight[3]=2. Push {2, 3} vào PQ.
- PQ: {2, 3}, {4, 3}, {5, 3}, {6, 4}. (Lưu ý: PQ có thể có nhiều entry cho đỉnh 3, nhưng entry nhỏ nhất {2,3} sẽ được pop trước).
Bước 4:
- PQ: {2, 3}, {4, 3}, {5, 3}, {6, 4}. Pop {2, 3}. u=3 (đỉnh 4). in_mst[3]=F. Mark in_mst[3]=T. total_weight += 2. Print "Thêm đỉnh 4".
- Duyệt cạnh từ đỉnh 3:
  - (3,0,5): v=0 (đỉnh 1). in_mst[0] (T). Bỏ qua.
  - (3,2,4): v=2 (đỉnh 3). in_mst[2] (T). Bỏ qua.
  - (3,1,2): v=1 (đỉnh 2). in_mst[1] (T). Bỏ qua.
  - (3,4,3): v=4 (đỉnh 5). edge_w=3. !in_mst[4] (T) && 3 < min_weight[4] (6). 3 < 6 là Đúng. Update min_weight[4]=3. Push {3, 4} vào PQ.
- PQ: {3, 4}, {4, 3}, {5, 3}, {6, 4}. (Lưu ý: các entry cũ cho đỉnh 3 bị bỏ qua ở bước pop tiếp theo vì in_mst[3] đã True).
Bước 5:
- PQ: {3, 4}, {4, 3}, {5, 3}, {6, 4}. Pop {3, 4}. u=4 (đỉnh 5). in_mst[4]=F. Mark in_mst[4]=T. total_weight += 3. Print "Thêm đỉnh 5".
- Duyệt cạnh từ đỉnh 4:
  - (4,2,6): v=2 (đỉnh 3). in_mst[2] (T). Bỏ qua.
  - (4,3,3): v=3 (đỉnh 4). in_mst[3] (T). Bỏ qua.
- PQ: {4, 3}, {5, 3}, {6, 4}. (Các entry này ứng với các đỉnh đã vào MST hoặc đã bị tìm thấy đường đi rẻ hơn, sẽ bị bỏ qua ở bước pop).
PQ không rỗng nhưng tất cả các đỉnh đã vào MST. Tổng trọng số: 0 + 2 + 3 + 2 + 3 = 10.

MST tìm được có tổng trọng số là 10. Prim xây dựng cây bằng cách lần lượt thêm các đỉnh 1, 3, 2, 4, 5 vào cây hiện tại thông qua cạnh rẻ nhất nối vào cây.

Prim thường hiệu quả hơn Kruskal trên các đồ thị đậm đặc (dense graphs), nơi số cạnh E gần với V^2. Sử dụng priority queue nhị phân, thời gian chạy của Prim là O(E log V) hoặc O(E log E) (vì E <= V^2, log E <= 2 log V). Với Fibonacci heap (phức tạp hơn), thời gian có thể đạt O(E + V log V), hiệu quả hơn nữa với đồ thị rất đậm đặc. Tuy nhiên, với priority queue chuẩn, O(E log V) là phổ biến nhất.

So sánh Kruskal và Prim

Cả Kruskal và Prim đều là giải thuật tham lam tìm MST và đều cho kết quả đúng. Sự khác biệt chính nằm ở cách chúng mở rộng cây:

Kruskal: Duyệt các cạnh theo thứ tự trọng số và thêm vào nếu không tạo chu trình. Nó xây dựng MST từ nhiều thành phần liên thông nhỏ ban đầu và dần dần hợp nhất chúng. Thích hợp với đồ thị thưa. Dựa vào DSU.
Prim: Bắt đầu từ một đỉnh và dần thêm các đỉnh lân cận rẻ nhất vào một cây duy nhất đang phát triển. Thích hợp với đồ thị đậm đặc. Dựa vào Priority Queue.

Bài tập ví dụ:

[Tham Lam]. Nối dây 1.

Cho N sợi dây, biết chi phí nối 2 sợ dây là tổng độ dài của 2 sợi dây đó. Nhiệm vụ của bạn là nối N sợi dây này thành 1 sao cho chi phí nối dây là nhỏ nhất.

Input Format

Dòng 1 chứa số nguyên N; Dòng 2 chứa N số nguyên là độ dài các sợ dây. (1<=N<=10^5; Các sợi dây có độ dài không quá 10^5)

Constraints

Output Format

In ra chi phí nối dây tối thiểu.

Ví dụ:

Dữ liệu vào

6
7 7 6 10 4 8

Dữ liệu ra

Chào bạn, đây là hướng dẫn giải bài "Nối dây 1" bằng chiến lược tham lam (greedy) sử dụng C++.

Ý tưởng chính:

Để giảm thiểu tổng chi phí, tại mỗi bước nối dây, chúng ta nên nối hai sợi dây có độ dài ngắn nhất hiện có. Việc này đảm bảo rằng chi phí được cộng vào tổng (là tổng độ dài của hai dây được nối) là nhỏ nhất tại bước đó, và sợi dây mới tạo thành (có độ dài nhỏ nhất có thể) sẽ tham gia vào các phép nối sau này. Ta lặp lại quy trình này cho đến khi chỉ còn một sợi dây duy nhất.

Các bước thực hiện:

Đọc dữ liệu: Đọc số lượng dây N và độ dài của N sợi dây ban đầu.
Sử dụng cấu trúc dữ liệu: Cần một cấu trúc dữ liệu cho phép lấy ra phần tử nhỏ nhất một cách hiệu quả và chèn thêm phần tử mới. Hàng đợi ưu tiên cực tiểu (min-priority queue) là lựa chọn phù hợp nhất cho việc này. Trong C++, bạn có thể dùng std::priority_queue với std::greater.
Khởi tạo: Đưa tất cả độ dài của các sợi dây ban đầu vào hàng đợi ưu tiên. Khởi tạo một biến để lưu tổng chi phí, sử dụng kiểu dữ liệu long long để tránh tràn số, vì tổng chi phí có thể rất lớn.
Thực hiện nối dây: Lặp lại các bước sau cho đến khi trong hàng đợi chỉ còn duy nhất một phần tử:
- Lấy ra hai phần tử nhỏ nhất từ hàng đợi (gọi là day1 và day2).
- Tính tổng độ dài của chúng (tong_do_dai = day1 + day2).
- Cộng tong_do_dai vào tổng chi phí.
- Đưa sợi dây mới có độ dài tong_do_dai trở lại vào hàng đợi.
Kết quả: Sau khi vòng lặp kết thúc, biến tổng chi phí sẽ chứa chi phí nối dây nhỏ nhất. In giá trị này ra màn hình.

Lưu ý quan trọng:

Sử dụng long long cho biến tổng chi phí và có thể cả cho các giá trị độ dài dây khi cộng, vì tổng chi phí cuối cùng có thể vượt quá phạm vi của kiểu int.
Hàng đợi ưu tiên trong C++ (std::priority_queue) mặc định là cực đại (max-priority queue). Để dùng làm cực tiểu (min-priority queue), bạn cần khai báo thêm template parameters: std::priority_queue<Kiểu_Dữ_Liệu, std::vector<Kiểu_Dữ_Liệu>, std::greater<Kiểu_Dữ_Liệu>>.

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

Comments

There are no comments at the moment.