Bài tập

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

avatar
Huy Erick
00:00 12/04/2024

Trong bài viết này, chúng ta sẽ tìm hiểu về thuật toán Kruskal để tìm cây khung có trọng số nhỏ nhất. Dẫn nhập Trong bài học trước, chúng ta đã tìm hiểu về thuật...

Trong bài viết này, chúng ta sẽ tìm hiểu về thuật toán Kruskal để tìm cây khung có trọng số nhỏ nhất.

Dẫn nhập

Trong bài học trước, chúng ta đã tìm hiểu về thuật toán để tìm cây khung có trọng số nhỏ nhất. Hôm nay, chúng ta sẽ tìm hiểu thêm một thuật toán khác để giải quyết bài toán này.

Nội dung

Để hiểu bài học này một cách tốt nhất, ta cần có kiến thức cơ bản về:

Xem thêm:
  • Các kiến thức cần thiết để theo dõi khóa học
  • Đồ thị và cây
  • BFS và DFS
  • Disjoint Set Union

Trong bài học ngày hôm nay, chúng ta sẽ tìm hiểu về thuật toán Kruskal.

Bài toán đặt ra

Bài toán được đặt ra như sau: Một quốc gia có n thành phố được đánh số từ 1 đến n. Chính phủ 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. Sau quá trình khảo sát, chính phủ đã tìm ra m tuyến đường có thể xây dựng giữa hai thành phố u và v với chi phí là w. Nhiệm vụ của chúng ta là tính toán chi phí nhỏ nhất để xây dựng các tuyến đường đáp ứng yêu cầu trên.

Input:

  • Dòng 1: 2 số nguyên dương n và m, thể hiện số thành phố và số tuyến đường có thể xây dựng (1 ≤ n, m ≤ 10^5)
  • Dòng 2...m+1: Mỗi dòng chứa ba số nguyên dương u_i, v_i, w_i, trong đó u_i và v_i là hai thành phố có thể xây đường kết nối, w_i là chi phí xây dựng tuyến đường đó (1 ≤ u_i, v_i ≤ n, 1 ≤ w_i ≤ 10^9)

Output:

  • Một số nguyên duy nhất là chi phí nhỏ nhất để 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:

5 7
1 2 3
2 4 7
3 5 6
4 5 4
2 5 3
1 3 2
2 3 4

Output:

12

Thuật toán Kruskal

Ý tưởng

Thuật toán Kruskal có ý tưởng đơn giản: để có cây khung có trọng số nhỏ nhất, ta cần chọn các cạnh có trọng số nhỏ nhất. Do đó, khi chọn các cạnh vào cây khung, chúng ta ưu tiên các cạnh có trọng số nhỏ trước.

Hãy thử áp dụng ý tưởng này vào đồ thị dưới đây:

  • Đầu tiên, ta chọn cạnh nối đỉnh 1 và đỉnh 2 vào cây khung.
  • Tiếp theo, ta chọn cạnh nối đỉnh 2 và đỉnh 3 vào cây khung. Lúc này, các đỉnh 1, 2 và 3 đã được nối thông.

Từ ví dụ trên, ta thấy khi chọn cạnh nối, ta cần kiểm tra xem hai đỉnh đã nối có liên thông hay chưa. Đây là lúc chúng ta sử dụng cấu trúc Disjoint Set Union mà đã được giới thiệu trước đây.

Cách cài đặt

Để cài đặt thuật toán Kruskal, ta cần sử dụng 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:

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

Độ phức tạp

Độ phức tạp của thuật toán Kruskal phụ thuộc vào việc sắp xếp các cạnh và có độ phức tạp là O(n log n). Do đó, độ phức tạp thời gian của thuật toán là O(n log n).

#include
#include
using namespace std;
struct dt
{
    int d1, d2, gt;
}dt[100005];
int n,m,dsu[100005];
bool ss(dt a,dt b)
{
    return a.gt>n>>m;
    for(int i=1;i=m;i++)
        cin>>dt[i].d1>>dt[i].d2>>dt[i].gt;
    sort(dt+1,dt+m+1,ss);
    for(int i=1;i=n;i++)
        dsu[i]=i;
    int d=0,kq=0;
    for(int i=1;i=m;i++)
    {
        int p=cha(dt[i].d1),q=cha(dt[i].d2);
        if(p!=q)
        {
            dsu[p]=q;
            kq+=dt[i].gt;
            d++;
            if(d==n-1)
                break;
        }
    }
    cout

Kết luận

Qua bài viết này, chúng ta đã tìm hiểu về thuật toán Kruskal để tìm cây khung nhỏ nhất. Hy vọng bài viết này giúp bạn hiểu rõ hơn về thuật toán này.

Xin chân thành cảm ơn bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý để chúng tôi 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 hoặc thắc mắc nào về khóa học, hãy đặt câu hỏi trong phần bình luận bên dưới hoặc trong mục HỎI & ĐÁP trên trang web Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.

BÀI LIÊN QUAN
1