Thuật giải – Bài tập – Tìm cây bao trùm nhỏ nhất bằng thuật giải Kruskal

Hôm nay rảnh rỗi lục lại xem lại một số bài blog từ hồi năm 2. Nhớ lúc đó đang học môn thuật giải, mỗi lần học xong thì hay về viết blog mấy thứ học ở trường. Hứng hứng nên code lại chơi. Lần này chủ yếu code demo ngắn gọn, đủ hiểu. Thôi thì lâu rồi không viết blog, cũng làm biếng copy lại mấy bài viết từ bên blogspot qua wordpress (hồi trước xài blogspot). Vậy nên chơi bài mới luôn :”>

Tìm cây bao trùm nhỏ nhất  bằng  thuật giải Kruskal

1.       Mục đích?

Chúng ta học cái gì đó, đầu tiên hay thắc mắc: “học cái này để làm gì?”.

Học cái gì đó mà không rõ tác dụng của nó thì người ta thường đâm ra chán và không thèm quan tâm.

Vậy nên lần này tôi xin lấy một cái ứng dụng của cái thuật giải trên để cho các bạn chưa hiểu thuật giải này cảm thấy đáng để tiếp tục quan tâm.

“Ví dụ như một hãng TV truyền hình cáp muốn nối cáp đến một khu dân cư mới. Khổ cái là chỉ được chôn cáp ở ngoài đường và chỉ cho 1 cọng cáp đi vào thôi. Đường thì có ngắn có dài, chỗ phẳng chỗ gồ ghề.  Nếu đường nào mình cũng chôn cáp thì tốn lắm. Mà nếu không muốn tốn thì giờ phải suy nghĩ xem là chọn ra mấy cái đường nào đỡ tốn nhất nhưng phải đảm bảo được cáp phải đến mọi nhà” . (ví dụ lấy từ wiki, có chỉnh sữa ngôn từ)

Hình ảnh minh họa:

Một trong những cách giải quyết cho bài toán trên là thuật giải Kruskal trên lý thuyết đồ thị.

Về định nghĩa cây bao trùm, cây bao trùm nhỏ nhất, kruskal, độ phức tạp,… thì chắc mọi người đọc slide rồi nên thôi tôi xin vào ngay thẳng vấn đề chính.

Tóm 1 cách siêu gọn: Kruskal sẽ ưu tiên những cạnh có trọng số nhỏ, nếu bị quay vòng thì bỏ cạnh đó ra, xét tiếp cạnh khác.

2.       Mã giả Kruskal:

//Lấy từ trong quyển Introduction to Algorithms

Mọi người có lẽ sẽ bỡ ngỡ là tại sao bên ý tưởng trình bày khá đơn giản vậy mà cái mã giả lại quá rối rắm.

Thật ra, Ý tưởng là ý tưởng. Từ ý tưởng hiện thực sang mã giả sẽ cần đến một số bước chuyển đổi kỹ thuật nhằm mục đích cụ thể hóa bước lập trình tới.

Ở đây, Bước chuyển đổi kỹ thuật yêu cầu chúng ta sử dụng đến một cấu trúc dữ liệu sau:

Disjoint-set data structure: Bạn nào chưa hiểu thì có thể vào link sau để đọc. Dễ hiểu nhất là cứ chạy tay. Cần nắm được cấu trúc, thế nào là MakeSet? FindSet? Union?

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

Nếu đã hiểu cấu trúc trên thì bắt tay vào code thôi.

Tôi làm một cái demo rất đơn giản trên đồ thị vô hướng.

Đồ thị được thể hiện bằng một danh sách cạnh: edges

Kết quả cây bao trùm nhỏ nhất tôi cũng thể hiện bằng một danh sách cạnh: mst

Đây là cấu trúc 1 cạnh trong danh sách cạnh: (gồm đỉnh bắt đầu, đỉnh kết thúc, trọng số)

struct Edge {

    int beginVertex, endVertex, weight;

};

Vì mục đích hướng đến học tập và demo nên tôi bỏ qua luôn bước nhập bằng cin hay nhập bằng file lằng nhằng, thế là tôi khởi tạo cứng trong code luôn:

Edge edges[SIZE*SIZE] = {{0,1,6},{0,2,5},{0,3,4},{1,3,8},{2,3,3},{2,4,2},{3,4,1}};

int vertexNumber = 5;

int edgeNumber = 7;

Dữ liệu đầu vào tương ứng với hình vẽ đồ thị sau: (5 đỉnh, 7 cạnh)

Tôi không canh vẽ đúng tỉ lệ trọng số trên hình vì muốn nhắc lại rằng “trọng số không nhất thiết phải là chiều dài”.

Việc xuất kết quả thì tôi làm đơn giản chỉ là in ra thông tin các cạnh trong mảng mst.

Vậy thôi, chuyển từng bước từ mã giả sang mã C++, kết hợp thêm 1 số hàm làm việc với disjoint-set là sẽ ra chương trình.

Sẵn đây, giới thiệu với các bạn về thư viện algorithm trong C++ STL. Nó bao gồm rất nhiều hàm xử lý rất hay, giúp việc lập trình nhẹ nhàng hơn. Trong đó có hàm sort. Chỉ cần khai báo thư viện là có thể sử dụng hàm sort với độ phức tạp N*LogN.  Nếu không sử dụng thư viện cũng chả sao, chúng ta vẫn có thể tự lập trình lấy. Muốn khỏe thì bubble sort, tối ưu hơn thì có heap sort, quick sort.

Oke xong, ngắn nên show source code luôn:

 
#include<iostream>
#include<algorithm>
#define SIZE 100
using namespace std;

struct Edge {
    int beginVertex, endVertex, weight;
};

Edge edges[SIZE*SIZE] = {{0,1,6},{0,2,5},{0,3,4},{1,3,8},{2,3,3},{2,4,2},{3,4,1}};
int vertexNumber = 5;
int edgeNumber = 7;

Edge mst[SIZE*SIZE];
int mstNumber;
int parent[SIZE];

bool compareEdge(const Edge& e1, const Edge& e2) {
    return (e1.weight < e2.weight);
}

int findSet(int u) {
    int v = u;
    while(parent[v] >= 0)
        v = parent[v];
    return v;
}

void unionSet(int u,int v) {
    int x = findSet(u);
    int y = findSet(v);
    if (parent[x] > parent[y]){
        parent[y] += parent[x];
        parent[x] = y;
    } else {
        parent[x] += parent[y];
        parent[y] = x;
    }
}

void kruskal() {
    int i, beginRoot, endRoot;

    for(i=0; i<vertexNumber; i++)
        parent[i] = -1;

    sort(edges, edges+edgeNumber, compareEdge);

    for(i = 0; i<edgeNumber; ++i) {
        beginRoot = findSet(edges[i].beginVertex);
        endRoot = findSet(edges[i].endVertex);
        if(beginRoot != endRoot) { 

            mst[mstNumber++] = edges[i];
            unionSet(beginRoot, endRoot);
            if(mstNumber == vertexNumber - 1) break; 
        }
    }
}

int main() {
    kruskal();

    int i;
    for(i=0; i<mstNumber; ++i)
        cout<<mst[i].beginVertex<<" "<<mst[i].endVertex<<" "<<mst[i].weight<<endl;
    return 0;
}