Tìm kiếm cây khung nhỏ nhất (Kruskal)

Cấu trúc dữ liệu và giải thuật

0.0 (0 đánh giá)
Tạo bởi Katsu Cập nhật lần cuối 14:06 08-07-2022 802 lượt xem 0 bình luận
Tác giả/Dịch giả: huulam3011 K9
Học nhanh

Danh sách bài học

Tìm kiếm cây khung nhỏ nhất (Kruskal)

Dẫn nhập

Trong bài học trước, chúng ta đã cùng nhau đi tìm hiểu thuật toán đầu tiên để có thể tìm cây khung có trọng số nhỏ nhất. Trong bài học ngày hôm nay, chúng ta sẽ tìm hiểu thêm một thuật toán nữa để  có thể tìm cây khung có trọng số nhỏ nhất.


Nội dung

Để có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:

  • Thuật toán Kruskal

Bài toán đặt ra

Ta sẽ xem lại bài toán mà bài học trước chúng ta đã đặt ra:

Một quốc gia có n thành phố được đánh số từ 1 đến n. Hiện tại, chính phủ đang muốn xây dựng các tuyến đường sao cho từ một thành phố có thể di chuyển đến tất cả các thành phố khác. Qua quá trình khảo sát, chính phủ nhận thấy có m tuyến đường giữa hai thành phố u_{i} và v_{i} có thể xây dựng với chi phí là w_{i}. Nhiệm vụ của bạn là tính toán chi phí nhỏ nhất để xây dựng các tuyến đường với yêu cầu như trên.

Input:

  • Dòng 1: 2 số nguyên dương n,m lần lượt thể hiện số thành phố và số tuyến đường có thể xây dựng (n,m \leq 10^{5}) 
  • Dòng 2…m+1: Mỗi dòng gồm ba số nguyên dương u_{i}, v_{i}, w_{i}, trong đó u_{i}, v_{i} thể hiện cho 2 thành phố có thể xây đường kết nối, w_{i} thể hiện cho chi phí xây tuyến đường đó (1\leq u_{i}, v_{i} \leq n, w_{i} \leq 10^{9})

Output:

  • Một số nguyên duy nhất là chi phí để xây dựng các tuyến đường sao cho từ một thành phố có thể di chuyển đến tất cả các thành phố khác

Ví dụ:

Input Output

5 7

1 2 3

2 4 7

3 5 6

4 5 4

2 5 3

1 3 2

2 3 4

12

Giải thích ví dụ:

Đây là hình ảnh minh hoạ cho ví dụ ở trên với các con đường có thể xây dựng

Kruskal

Đây là các con đường được lựa chọn (màu cam)

Kruskal


Thuật toán Kruskal

Ý tưởng

Ý tưởng xuất phát của thuật toán Kruskal khá đơn giản: Muốn tổng trọng số của cây khung mà ta chọn nhỏ nhất thì trọng số của các cạnh mà ta chọn phải nhỏ nhất có thể. Do đó, khi chọn các cạnh vào cây khung ta sẽ ưu tiên các cạnh có trọng số nhỏ trước.

Hãy thử ý tưởng trên với đồ thị dưới đây:

  • Theo như ý tưởng của ta ở trên, ta sẽ ưu tiên chọn các cạnh có trọng số nhỏ trước. Do đó, ta sẽ chọn cạnh nối đỉnh 1 và đỉnh 2 vào cây khung.
  • Tiếp theo, ta sẽ chọn cạnh nối đỉnh 2 và đỉnh 3 vào cây khung. Khi nay, các đỉnh 1, đỉnh 2 và đỉnh 3 liên thông
  • Theo như ý tưởng trên, ta sẽ tiếp tục chọn cạnh nối đỉnh 2 và đỉnh 3 vào cây khung. Tuy nhiên, ta nhận thấy rằng đỉnh 2 và đỉnh 3 lúc này đã liên thông. Do đó, việc chọn thêm cạnh này vào cây khung là vô nghĩa.

Từ nhận xét trên, ta thấy khi chọn cạnh nối sẽ cần kiểm tra xem hai đỉnh được nối đã liên thông chưa. Vậy thì làm sao để kiểm tra được điều này? Đây chính là lúc mà ta sử dụng đến cấu trúc Disjoint Set Union mà mình đã giới thiệu


Cách cài đặt

Để có thể cài đặt thuật toán Kruskal, ta sẽ cần một cấu trúc Edge để lưu trữ các cạnh với 3 biến:

  • u, v: hai đỉnh của cạnh
  • w: trọng số của cạnh

Thuật toán diễn ra như sau:

  • Khởi tạo Disjoint Set Union
  • Sắp xếp các cạnh theo trọng số tăng dần
  • Lần lượt xét các cạnh theo thứ tự đã sắp xếp
    • Nếu như cạnh đó nối hai đỉnh đã liên thông thì ta bỏ qua.
    • Nếu như hai đỉnh đó chưa liên thông thì ta sẽ thêm trọng số cạnh đó vào kết quả và dùng Disjoint Set Union để hợp nhất hai tập chứa hai đỉnh
  • Khi đã xét tất cả các cạnh thì sẽ thu được trọng số của cây khung có trọng số nhỏ nhất

Code

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MaxN = 1 + 1e5;

class Edge {
    public:
        int u, v, w;

        Edge(int _u = 0, int _v = 0, int _w = 0) : u(_u), v(_v), w(_w) {}

        bool operator < (const Edge &op) const {
            return w < op.w;
        }
};

int n, m, parent[MaxN];
vector<Edge> edges;

void make_set(int u){
    parent[u] = u;
}

int find_set(int u){
    if(u == parent[u]) return u;
    return parent[u] = find_set(parent[u]);
}

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n >> m;
    for(int i = 0 ; i < m ; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back(Edge(u, v, w));
    }
    for(int i = 1 ; i <= n ; ++i) make_set(i);
    sort(edges.begin(), edges.end());
    ll ans = 0;
    for(int i = 0 ; i < m ; ++i){
        Edge e = edges[i];
        int u = find_set(e.u);
        int v = find_set(e.v);
        if(u != v){
            ans += e.w;
            parent[u] = v;
        }
    }
    cout << ans << endl;

    return 0;
}

Độ phức tạp

Ta thấy chi phí lớn nhất của thuật toán trên nằm ở khâu sắp xếp các cạnh và có độ phức tạp là 0(n \times logn). Do đó, độ phức tạp thời gian của thuật toán là 0(n \times logn).


Kết luận

Qua bài này chúng ta đã nắm về Tìm kiếm cây khung nhỏ nhất với thuật toán Kruskal

Bài sau chúng ta sẽ tìm hiểu về Tính diện tích tam giác - Phần 1

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.


Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.

Nội dung bài viết

Tác giả/Dịch giả

Mình là Nguyễn Hữu Lâm, một người có niềm đam mê rất lớn đối với lập trình. Hiện tại, mình đang là sinh viên Khoa học máy tính của Đại học Bách Khoa Hà Nội. Mong muốn của mình là có thể chia sẻ những kiến thức mà bản thân có cho mọi người, học hỏi, kết bạn với tất cả những người có cùng đam mê với mình.


K9

Nhà sáng lập Howkteam.com, KQuiz.vn & tác giả các khóa học C#, Auto, Unity3D, Python....

Với mong muốn mang đến kiến thức chất lượng, miễn phí cho mọi người, với tâm huyết phá bỏ rào cản kiến thức từ việc giáo dục thu phí. Tôi đã cùng đội ngũ Kteam đã lập nên trang website này để thế giới phẳng hơn.
Hãy cùng chúng tôi lan tỏa kiến thức đến cộng đồng! 

Khóa học

Cấu trúc dữ liệu và giải thuật

Bạn đã từng đau đầu với các cấu trúc stack, queue,.. hoặc cảm thấy cực kỳ khó khăn với các thuật toán sắp xếp, tìm kiếm được sử dụng trong lập trình. Đừng lo lắng! Trong khoá học này, chúng ta sẽ cùng nhau tìm hiểu một cách đơn giản nhất về cấu trúc dữ liệu và giải thuật, cũng như giúp bạn nắm rõ hơn về các kiến thức này.

Hãy cùng xem cấu trúc dữ liệu và giải thuật có gì đáng sợ không nhé!

Đánh giá

Bình luận

Để bình luận, bạn cần đăng nhập bằng tài khoản Howkteam.

Đăng nhập
Không có video.