NỘI DUNG
Giới thiệu thuật toán Kruskal
Thuật toán Kruskal là một thuật toán trong lý thuyết đồ thị được sử dụng để tìm cây khung nhỏ nhất của một đồ thị vô hướng có trọng số. Được đặt tên theo nhà toán học người Mỹ Joseph Kruskal, thuật toán này là một trong những phương pháp phổ biến nhất để giải quyết bài toán tìm cây khung nhỏ nhất.
Cây khung nhỏ nhất của một đồ thị là một cây con của đồ thị đó, bao gồm tất cả các đỉnh và một số cạnh sao cho tổng trọng số của các cạnh đó là nhỏ nhất. Thuật toán Kruskal làm việc bằng cách xử lý tất cả các cạnh của đồ thị theo thứ tự tăng dần của trọng số, và thêm cạnh đó vào cây khung nếu việc thêm cạnh đó không làm cho cây khung trở thành một đồ thị không liên thông.
Các bước Thuật toán Kruskal
Các bước của thuật toán Kruskal để tìm cây khung nhỏ nhất của đồ thị vô hướng có trọng số là như sau:
- Sắp xếp các cạnh của đồ thị theo thứ tự tăng dần của trọng số.
- Khởi tạo một Disjoint Set để lưu trữ các đỉnh trong cây khung.
- Duyệt qua từng cạnh của đồ thị theo thứ tự đã sắp xếp:
- Nếu hai đỉnh của cạnh đó đã nằm trong cùng một tập hợp của Disjoint Set, bỏ qua cạnh đó vì việc thêm cạnh đó vào cây khung sẽ làm cho cây khung trở thành một đồ thị không liên thông.
- Nếu hai đỉnh của cạnh đó nằm trong các tập hợp khác nhau của Disjoint Set, thêm cạnh đó vào cây khung và gộp hai tập hợp lại thành một tập hợp mới.
Khi thuật toán kết thúc, cây khung nhỏ nhất sẽ được tạo ra từ các cạnh được chọn. Thuật toán Kruskal có độ phức tạp O(E log E), trong đó E là số lượng cạnh của đồ thị.
Ví dụ về thuật toán Kruskal
Giả sử ta có đồ thị vô hướng sau đây với 4 đỉnh và 5 cạnh, mỗi cạnh được gán một trọng số:
2
1-----2
| |
3-----4 3
1
Ta sẽ sử dụng thuật toán Kruskal để tìm cây khung nhỏ nhất của đồ thị này.
Bước 1: Sắp xếp các cạnh theo thứ tự tăng dần của trọng số:
Cạnh | Trọng số
---------|----------
1 - 2 | 2
3 - 4 | 3
1 - 3 | 3
2 - 4 | 3
1 - 4 | 4
Bước 2: Khởi tạo Disjoint Set để lưu trữ các đỉnh trong cây khung.
Disjoint Set: {1}, {2}, {3}, {4}
Bước 3: Duyệt qua từng cạnh của đồ thị theo thứ tự đã sắp xếp:
Cạnh 1 – 2 có trọng số 2. Đỉnh 1 và 2 nằm trong các tập hợp khác nhau của Disjoint Set. Thêm cạnh này vào cây khung và gộp hai tập hợp lại thành {1, 2} và {3}, ta có cây khung nhỏ nhất như sau:
2
1-----2
|
3-----4 3
Cạnh 3 – 4 có trọng số 3. Đỉnh 3 và 4 nằm trong các tập hợp khác nhau của Disjoint Set. Thêm cạnh này vào cây khung và gộp hai tập hợp lại thành {1, 2, 3, 4}, ta có cây khung nhỏ nhất như sau:
2
1-----2
| |
3-----4 3
- Cạnh 1 – 3 có trọng số 3. Đỉnh 1 và 3 thuộc cùng một tập hợp của Disjoint Set, bỏ qua cạnh này.
- Cạnh 2 – 4 có trọng số 3. Đỉnh 2 và 4 thuộc cùng một tập hợp của Disjoint Set, bỏ qua cạnh này.
- Cạnh 1 – 4 có trọng số 4. Đỉnh 1 thuộc tập hợp {1, 2, 3, 4} và đỉnh 4 thuộc tập hợp {1, 2}, bỏ qua cạnh này vì việc thêm cạnh này sẽ làm cho cây khung trở thành một đồ thị không liên thông.
Sau khi duyệt qua tất cả các cạnh, ta có cây khung nhỏ nhất của đồ thị ban đầu như sau:
2
1-----2
|
3-----4 3
Cây khung này có tổng trọng số là 8, là cây khung nhỏ nhất của đồ thị ban đầu.
Bước 4: Kết thúc thuật toán và trả về cây khung nhỏ nhất tìm được.
Ở ví dụ trên, cây khung nhỏ nhất tìm được là:
2
1-----2
|
3-----4 3
Cây khung này có tổng trọng số là 8, là cây khung nhỏ nhất của đồ thị ban đầu.
Cài đặt Thuật toán Kruskal với Python
Đây là code Python để thực hiện thuật toán Kruskal trên một đồ thị có trọng số, trong đó ta sử dụng Union-Find để kiểm tra xem hai đỉnh có thuộc cùng một thành phần liên thông hay không:
# Cài đặt thuật toán Kruskal trong Python
# Hàm tìm thành phần liên thông của một đỉnh sử dụng phương pháp Union-Find
def find(parent, i):
if parent[i] == i:
return i
return find(parent, parent[i])
# Hàm để hợp nhất hai thành phần liên thông sử dụng phương pháp Union-Find
def union(parent, rank, x, y):
xroot = find(parent, x)
yroot = find(parent, y)
# Gộp hai cây khung liên thông khác nhau dựa vào rank
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else :
parent[yroot] = xroot
rank[xroot] += 1
# Hàm Kruskal để tìm cây khung nhỏ nhất
def kruskal(graph, V):
# Sắp xếp các cạnh theo thứ tự tăng dần của trọng số
graph = sorted(graph, key=lambda item: item[2])
result = [] # Khởi tạo cây khung nhỏ nhất
i = 0 # Biến đếm số cạnh đã được thêm vào cây khung
parent = [] ; rank = []
# Khởi tạo parent và rank
for node in range(V):
parent.append(node)
rank.append(0)
while i < V - 1 :
# Lấy cạnh với trọng số nhỏ nhất
u, v, w = graph[i]
i = i + 1
x = find(parent, u)
y = find(parent, v)
# Kiểm tra xem có tạo thành chu trình không
# Nếu không tạo thành chu trình, thì thêm cạnh vào cây khung
if x != y:
result.append([u,v,w])
union(parent, rank, x, y)
# In kết quả
print("Các cạnh được chọn trong cây khung nhỏ nhất:")
for u, v, weight in result:
print("%d - %d: %d" % (u, v, weight))
Sau khi cài đặt xong, ta có thể thực hiện thuật toán trên một đồ thị với cấu trúc dạng danh sách cạnh (list of edges) và số lượng đỉnh (V) như sau:
# Thêm các cạnh vào đồ thị
graph.append([0, 1, 10])
graph.append([0, 2, 6])
graph.append([0, 3, 5])
graph.append([1, 3, 15])
graph.append([2, 3, 4])
# Thực hiện thuật toán Kruskal
kruskal(graph, V)
Kết quả trả về sẽ là danh sách các cạnh được chọn trong cây khung nhỏ nhất:
Các cạnh được chọn trong cây khung nhỏ nhất:
2 - 3: 4
0 - 3: 5
0 - 1: 10
Đánh giá độ phức tạp của thuật toán Kruskal
Độ phức tạp của thuật toán Kruskal là O(E log E) hoặc O(E log V), tùy thuộc vào cách triển khai. Trong đó, E là số lượng cạnh của đồ thị và V là số lượng đỉnh của đồ thị.
Thuật toán Kruskal sử dụng kỹ thuật sắp xếp cạnh theo trọng số để lựa chọn cạnh có trọng số nhỏ nhất trước tiên, đồng thời sử dụng Disjoint Set để xác định xem hai đỉnh có thuộc cùng một tập con hay không. Vì vậy, độ phức tạp của thuật toán Kruskal phụ thuộc vào độ phức tạp của thuật toán sắp xếp và thuật toán Disjoint Set.
Trong trường hợp sử dụng thuật toán sắp xếp quicksort để sắp xếp các cạnh, độ phức tạp của thuật toán Kruskal là O(E log E). Trong trường hợp sử dụng thuật toán sắp xếp heapsort để sắp xếp các cạnh, độ phức tạp của thuật toán Kruskal là O(E log V).
Trong tổng quát, thuật toán Kruskal có độ phức tạp khá tốt với độ phức tạp trung bình là O(E log E) hoặc O(E log V). Vì vậy, thuật toán Kruskal là một lựa chọn tốt để giải quyết bài toán tìm cây khung nhỏ nhất trong đồ thị có trọng số.