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 trước tiên để với thể tìm cây khuông với 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 để  với thể tìm cây khuông với trọng số nhỏ nhất.

Nội dung

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

• Những tri 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ẽ 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 với  thành thị trấn được đánh số từ Một tới . Hiện tại, chính phủ đang muốn xây dựng những tuyến đường sao cho từ một thành thị trấn với thể di chuyển tới tất cả những thành thị trấn khác. Qua quá trình khảo sát, chính phủ nhận thấy với  tuyến đường giữa hai thành thị trấn  và  với thể xây dựng với giá thành là . Nhiệm vụ của bạn là tính toán giá thành nhỏ nhất để xây dựng những tuyến đường với yêu cầu như trên.

Input:

• Dòng 1: Hai số nguyên dương  tuần tự thể hiện số thành thị trấn và số tuyến đường với thể xây dựng  
• Dòng 2…m+1: Mỗi dòng gồm ba số nguyên dương  trong đó  thể hiện cho Hai thành thị trấn với thể xây đường kết nối,  thể hiện cho giá thành xây tuyến đường đó

Output:

• Một số nguyên duy nhất là giá thành để xây dựng những tuyến đường sao cho từ một thành thị trấn với thể di chuyển tới tất cả những thành thị trấn khác

Ví dụ:

Giảng giải ví dụ:

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

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

Thuật toán Kruskal

Ý tưởng

Ý tưởng xuất phát của thuật toán Kruskal khá đơn thuần: Muốn tổng trọng số của cây khuông mà ta chọn nhỏ nhất thì trọng số của những cạnh mà ta chọn phải nhỏ nhất với thể. Do đó, lúc chọn những cạnh vào cây khuông ta sẽ ưu tiên những cạnh với 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 những cạnh với trọng số nhỏ trước. Do đó, ta sẽ chọn cạnh nối đỉnh Một và đỉnh Hai vào cây khuông.
• Tiếp theo, ta sẽ chọn cạnh nối đỉnh Hai và đỉnh 3 vào cây khuông. Lúc nay, những đỉnh 1, đỉnh Hai 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 Hai và đỉnh 3 vào cây khuông. Tuy nhiên, ta nhận thấy rằng đỉnh Hai 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 khuông là vô nghĩa.

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

Cách cài đặt

Để với thể cài đặt thuật toán Kruskal, ta sẽ cần một cấu trúc Edge để lưu trữ những 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 những cạnh theo trọng số tăng dần
• Tuần tự xét những 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à sử dụng Disjoint Set Union để thống nhất hai tập chứa hai đỉnh

• Lúc đã xét tất cả những cạnh thì sẽ thu được trọng số của cây khuông với trọng số nhỏ nhất

Code

 #include 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 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 > 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 giá thành to nhất của thuật toán trên nằm ở khâu sắp xếp những cạnh và với độ phức tạp là . Do đó, độ phức tạp thời kì của thuật toán là .

Kết luận

Qua bài này chúng ta đã nắm về Tìm kiếm cây khuông 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 những 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 “Tập luyện – Thử thách – Ko ngại khó”.

Thảo luận

Nếu bạn với bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt thắc mắc 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ự tương trợ từ cùng đồng.