Một minimum spanning tree (MST) kết nối tất cả các đỉnh của một đồ thị có trọng số, liên thông với tổng trọng số cạnh nhỏ nhất và không có chu trình. Kruskal và Prim là hai thuật toán greedy kinh điển.
Sắp xếp tất cả các cạnh theo trọng số; thêm cạnh rẻ nhất mà không tạo thành chu trình.
def kruskal(n, edges): # edges: (trọng số, u, v)
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # nén đường (path compression)
x = parent[x]
return x
mst, total = [], 0
for w, u, v in sorted(edges): # rẻ nhất trước
ru, rv = find(u), find(v)
if ru != rv: # không có chu trình -> lấy nó
parent[ru] = rv
mst.append((u, v, w)); total += w
return mst, total
Bắt đầu từ một đỉnh bất kỳ; liên tục thêm cạnh rẻ nhất rời khỏi cây hiện tại.
| Kruskal | Prim | |
|---|---|---|
| Cách tiếp cận | sắp xếp cạnh + union-find | phát triển từ một nút + heap |
| Thời gian | O(E log E) | O(E log V) |
| Tốt nhất cho | đồ thị thưa | đồ thị dày |
Dùng MST cho thiết kế mạng — lắp đặt cáp, đường ống nước, phân cụm (clustering). Cả hai đều là greedy và chứng minh được là tối ưu ở đây. Kruskal cần union-find để tránh chu trình một cách hiệu quả.
MST tối thiểu hóa chi phí kết nối mọi thứ — áp dụng trực tiếp vào hạ tầng và bố trí mạng.
Đây là một trường hợp rõ ràng mà greedy chứng minh được là tối ưu, củng cố lập luận greedy-choice.
Kruskal cũng phô diễn union-find, một cấu trúc có tầm ảnh hưởng thuật toán rộng.