Bài toán cây khung (cây bao trùm) nhỏ nhất của đồ thị là một trong số những bài toán tối ưu trên đồ thị có nhiều ứng dụng khác nhau trong đời sống. Để minh hoạ thuật toán, chúng ta tham khảo một vài mô hình thực tế tiêu biểu của bài toán:

Cho G=(X,E) là một đồ thị có trọng số gồm n đỉnh. Thuật toán Kruskal được dùng để tìm ra cây khung/cây bao trùm ngắn nhất của G như sau:

Bước 1: Duyệt các cạnh của đồ thị G và tạo danh sách các cạnh listEdge.

Bước 2: Sắp xếp lại danh sách các cạnh listEdge của đồ thị G theo trọng số tăng

dần, rồi đánh dấu tất cả các cạnh là chưa xét và khởi tạo T := Ø.(T là tập cạnh của cây khung hay cây bao trùm của đồ thị G).

Bước 3: Lấy cạnh e chưa xét có trọng số bé nhất trong danh sách listEdge đã sắp

xếp, nếu T∪{e} không chứa chu trình thì gán T: = T∪{e}. Đánh dấu cạnh e đã xét.

Bước 4: Nếu hết cạnh chưa xét (tức các cạnh đã xét hết) hoặc T có đủ n-1 cạnh

thì dừng, ngược lại làm tiếp tục bước 3. Thuật toán dừng, nếu T không có đủ n-1 cạnh thì đồ thị không liên thông và không có cây khung/bao trùm nhỏ nhất. Ngược lại thì có cây khung/bao trùm. Chú ý: Trong các thuật toán tìm khung ngắn nhất chúng ta có thể bỏ đi hướng các cạnh và các khuyên; đối với cạnh song song thì có thể bỏ đi và chỉ để lại một cạnh trọng lượng nhỏ nhất trong chúng.

2. Ví dụ thi hành thuật toán Kruskal

Cho đồ thị sau:

Tìm cây khung ngắn nhất của đồ thị trên dùng thuật toán Kruskal.

Bước 4: Nếu hết cạnh chưa xét (tức các cạnh đã xét hết) hoặc T có đủ n-1 cạnh thì dừng, ngược lại làm tiếp tục bước 3. T chỉ mới có 1 cạnh < n-1 = 4 -1 = 3 Ł quay lại bước 3. Bước 3 (lần 2): Lấy cạnh e chưa xét có trọng số bé nhất trong danh sách listEdge Ł lấy cạnh (2,4).

T∪{(2,4)} không tạo chu trình Ł T: =

T∪{(2,4)} = {(1,2); (2,4)}. Đánh dấu cạnh (2,4) đã xét bằng màu đỏ.

Bước 4 (lần 2): T chỉ mới có 2 cạnh < n-1 = 4 - 1 = 3 Ł quay lại bước 3. Bước 3 (lần 3): Lấy cạnh e chưa xét có trọng số bé nhất trong danh sách listEdge Ł lấy cạnh (1,2).

T∪{(1,2)} tạo chu trình 1à 2 à 4 à 1 Ł Không thể lấy cạnh (1,2). Ł T = {(1,2); (2,4)}. Đánh dấu cạnh (1,2) đã xét bằng màu đỏ. Bước 4 (lần 3): T chỉ mới có 2 cạnh < n-1 = 4 - 1 = 3 Ł quay lại bước 3. Bước 3 (lần 4): Lấy cạnh e chưa xét có trọng số bé nhất trong danh sách listEdge Ł lấy cạnh (3,4).

T∪{(3,4)} không tạo chu trình Ł T: =

T∪{(3,4)} = {(1,2); (2,4); (3,4)}. Đánh dấu cạnh (3,4) đã xét bằng màu đỏ

Bước 4 (lần 3): T chỉ mới có 3 cạnh = n-1 = 4 - 1 = 3 Ł dừng. Vậy cây khung/bao trùm là màu xanh lá cây tương ứng với những cặp cạnh trong T = {(1,2); (2,4); (3,4)} Khi đó tổng trọng số của cây khung/cây bao trùm là 1+1+2 = 4.

3. So sánh khác biệt Kruskal với Prim

Khác với Prime, Kruskal không cần kiểm tra đồ thị liên thông trước khi thi hành thuật toán. Nếu quá trình thi hành thuật toán tìm được cây khung/bao trùm thì đồ thị liên thông và ngược lại là đồ thị không liên thông. Khác với Prime là mở rộng tập đỉnh đã xét, Kruskal kiểm tra nếu khi thêm cạnh đang xét vào cây khung mà không làm phát sinh chu trình thì sẽ chọn cạnh này. Việc kiểm tra chu trình như thế này sẽ tốn chi phí. Ta có thể áp dụng cách sau để làm giảm chi phí kiểm tra chu trình:

1. Dùng một mảng Nhãn có kích thước bằng số đỉnh của đồ thị. Giá trị Nhãn[i] tại đỉnh i được khởi tạo bằng với chính chỉ số i của đỉnh. Ví dụ: Với đồ thị G ở trên ta có Đỉnh 1 2 3 4 Nhãn 1 2 3 4

Khi chọn một cạnh (u,v) được thêm vào cây khung/cây bao trùm, ta sửa nhãn của tất cả các đỉnh có cùng giá trị với nhãn của đỉnh v thành nhãn của đỉnh u.

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ề:

• 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ẽ 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ó thành phố được đánh số từ 1 đế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ó tuyến đường giữa hai thành phố và có thể xây dựng với chi phí là. 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:

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

Đây là các 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 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

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 < 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à. Do đó, độ phức tạp thời gian 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 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ó”.

---

Tải xuống

Tài liệu

Nhằm phục vụ mục đích học tập Offline của cộng đồng, Kteam hỗ trợ tính năng lưu trữ nội dung bài học Tìm kiếm cây khung nhỏ nhất (Kruskal) dưới dạng file PDF trong link bên dưới.

Ngoài ra, bạn cũng có thể tìm thấy các tài liệu được đóng góp từ cộng đồng ở mục TÀI LIỆU trên thư viện Howkteam.com

Đừng quên like và share để ủng hộ Kteam và tác giả nhé!

---

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.