Một cây khung nhỏ nhất (Minimum Spanning Tree - MST) hay cây khung trọng số nhỏ nhất là một tập hợp con của các cạnh của một đồ thị liên thông, có trọng số trên cạnh (có hướng hoặc vô hướng), kết nối tất cả các đỉnh với nhau mà không tạo thành bất kỳ chu trình nào và với tổng trọng số cạnh nhỏ nhất có thể. Nói cách khác, đó là một cây khung có tổng trọng số cạnh nhỏ nhất.
Khái niệm cơ bản
Trong lý thuyết đồ thị, MST được sử dụng rộng rãi trong các bài toán tối ưu hóa như thiết kế mạng lưới, định tuyến, phân cụm dữ liệu, và nhiều ứng dụng thực tế khác.
Các thuật toán phổ biến
1. Thuật toán Kruskal
Sắp xếp tất cả các cạnh theo trọng số tăng dần, sau đó thêm lần lượt các cạnh vào MST nếu chúng không tạo thành chu trình. Sử dụng cấu trúc dữ liệu Disjoint Set Union (DSU) để kiểm tra chu trình hiệu quả.
2. Thuật toán Prim
Bắt đầu từ một đỉnh bất kỳ, mở rộng cây bằng cách thêm cạnh có trọng số nhỏ nhất nối một đỉnh trong cây với một đỉnh ngoài cây. Thường triển khai với hàng đợi ưu tiên (priority queue).
Độ phức tạp
- Kruskal: O(E log E) hoặc O(E log V)
- Prim với binary heap: O(E log V)
- Prim với Fibonacci heap: O(E + V log V)
Ứng dụng thực tế
- Thiết kế mạng truyền thông, điện lực, đường ống
- Phân cụm dữ liệu (clustering)
- Xấp xỉ bài toán người du lịch (TSP)
- Mã hóa hình ảnh và nén dữ liệu