Cây Khung Nhỏ Nhất (Minimum Spanning Tree - MST) là gì?

TLDR: MST là cây khung có tổng trọng số nhỏ nhất, dùng để kết nối tất cả các đỉnh với chi phí tối thiểu. 3 thuật toán chính: Kruskal (sắp xếp cạnh), Prim (mở rộng từ đỉnh), Boruvka (hợp nhất rừng cây).

Giới thiệu về Cây Khung

Cây khung (spanning tree) là một đồ thị con dạng cây của một đồ thị vô hướng liên thông, bao gồm tất cả các đỉnh của đồ thị ban đầu. Nói cách khác dễ hiểu hơn, đó là một tập con các cạnh của đồ thị tạo thành một cây (không có chu trình), trong đó mọi đỉnh của đồ thị đều là một phần của cây này.

Cây khung nhỏ nhất có tất cả các tính chất của cây khung, với ràng buộc bổ sung là có tổng trọng số nhỏ nhất trong tất cả các cây khung có thể có. Giống như cây khung, một đồ thị có thể có nhiều cây khung nhỏ nhất khác nhau.

Các Tính Chất Của Cây Khung

TLDR: Cây khung có V đỉnh và V-1 cạnh, không có chu trình, liên thông đến tất cả các đỉnh.

Cây khung tuân theo các nguyên tắc sau:

Số lượng đỉnh (V): trong đồ thị gốc và cây khung là như nhau.
Số lượng cạnh cố định: trong cây khung bằng số đỉnh trừ đi 1 (E = V - 1).
Liên thông: Cây khung không được rời rạc (disconnected), nghĩa là chỉ có một thành phần liên thông duy nhất.
Không có chu trình (acyclic): có nghĩa là không có vòng lặp nào trong cây.
Tổng chi phí: được định nghĩa là tổng trọng số của tất cả các cạnh trong cây khung.
Không duy nhất: Một đồ thị có thể có nhiều cây khung khác nhau.

Cây Khung Nhỏ Nhất

Cây khung nhỏ nhất (MST) là một cây khung có tổng trọng số nhỏ nhất trong tất cả các cây khung có thể có.

Cây khung nhỏ nhất có tất cả các tính chất của cây khung với ràng buộc bổ sung là có tổng trọng số nhỏ nhất. Giống như cây khung, một đồ thị cũng có thể có nhiều cây khung nhỏ nhất.

Hãy xem xét MST của ví dụ đồ thị trên:

Các Thuật Toán Tìm Cây Khung Nhỏ Nhất

Có nhiều thuật toán để tìm cây khung nhỏ nhất từ một đồ thị cho trước, một số trong đó được liệt kê dưới đây:

1. Thuật Toán Kruskal

TLDR: Sắp xếp cạnh theo trọng số → Thêm cạnh nhỏ nhất → Bỏ qua nếu tạo chu trình → Lặp lại. Sử dụng DSU để kiểm tra chu trình.

Đây là một trong những thuật toán phổ biến để tìm cây khung nhỏ nhất từ một đồ thị vô hướng liên thông. Đây là một thuật toán tham lam. Quy trình hoạt động như sau:

Bước 1: Sắp xếp tất cả các cạnh của đồ thị theo trọng số tăng dần.
Bước 2: Bắt đầu quá trình lặp để tìm cây khung.
Bước 3: Ở mỗi bước lặp, thuật toán thêm cạnh có trọng số nhỏ nhất tiếp theo, sao cho các cạnh đã chọn đến hiện tại không tạo thành chu trình.

Thuật toán này có thể được triển khai hiệu quả bằng cách sử dụng cấu trúc dữ liệu DSU (Disjoint-Set Union) để theo dõi các thành phần liên thông của đồ thị. Thuật toán được sử dụng trong nhiều ứng dụng thực tế như thiết kế mạng, phân cụm dữ liệu và phân tích dữ liệu.

Tham khảo bài viết về "Thuật toán Kruskal" để hiểu rõ hơn và cách triển khai thuật toán.

2. Thuật Toán Prim

TLDR: Chọn đỉnh ban đầu → Mở rộng MST bằng cách thêm cạnh nhỏ nhất nối MST với đỉnh ngoài → Lặp lại. Sử dụng Priority Queue.

Đây cũng là một thuật toán tham lam. Quy trình hoạt động như sau:

Bước 1: Bắt đầu bằng cách chọn một đỉnh tùy ý và thêm nó vào MST.
Bước 2: Lặp đi lặp lại việc tìm cạnh có trọng số nhỏ nhất kết nối một đỉnh trong MST với một đỉnh chưa có trong MST.
Bước 3: Quá trình này tiếp tục cho đến khi tất cả các đỉnh được bao gồm trong MST.

Để chọn hiệu quả cạnh có trọng số nhỏ nhất cho mỗi lần lặp, thuật toán này sử dụng hàng đợi ưu tiên (Priority Queue) để lưu trữ các đỉnh được sắp xếp theo trọng số cạnh nhỏ nhất hiện tại. Nó cũng đồng thời theo dõi MST bằng một mảng hoặc cấu trúc dữ liệu phù hợp khác.

Thuật toán này có thể được sử dụng trong nhiều tình huống như phân đoạn hình ảnh dựa trên màu sắc, kết cấu hoặc các đặc điểm khác. Đối với định tuyến, như tìm đường đi ngắn nhất giữa hai điểm cho xe giao hàng.

Tham khảo bài viết về "Thuật toán Prim" để hiểu rõ hơn và cách triển khai thuật toán.

3. Thuật Toán Boruvka

TLDR: Mỗi đỉnh là một cây riêng → Mỗi cây tìm cạnh rẻ nhất nối với cây khác → Hợp nhất các cây → Lặp lại đến khi còn 1 cây.

Đây cũng là một thuật toán duyệt đồ thị được sử dụng để tìm cây khung nhỏ nhất của một đồ thị vô hướng liên thông. Đây là một trong những thuật toán lâu đời nhất. Thuật toán hoạt động bằng cách xây dựng lặp đi lặp lại cây khung nhỏ nhất, bắt đầu với mỗi đỉnh trong đồ thị như một cây riêng biệt. Trong mỗi lần lặp, thuật toán tìm cạnh rẻ nhất kết nối một cây với một cây khác, và thêm cạnh đó vào cây khung nhỏ nhất. Quy trình hoạt động như sau:

Bước 1: Khởi tạo một rừng cây, với mỗi đỉnh trong đồ thị là một cây riêng.
Bước 2: Đối với mỗi cây trong rừng:
Tìm cạnh rẻ nhất kết nối nó với một cây khác.
Thêm các cạnh này vào cây khung nhỏ nhất.
Cập nhật rừng bằng cách hợp nhất các cây được kết nối bởi các cạnh đã thêm.
Bước 3: Lặp lại các bước trên cho đến khi rừng chỉ chứa một cây duy nhất, đó là cây khung nhỏ nhất.

Thuật toán có thể được triển khai bằng cách sử dụng cấu trúc dữ liệu như hàng đợi ưu tiên để tìm hiệu quả cạnh rẻ nhất giữa các cây. Thuật toán Boruvka là một thuật toán đơn giản và dễ triển khai để tìm cây khung nhỏ nhất, nhưng nó có thể không hiệu quả bằng các thuật toán khác đối với đồ thị lớn có nhiều cạnh.

Tham khảo bài viết về "Thuật toán Boruvka" để hiểu rõ hơn và cách triển khai thuật toán.

Ứng Dụng Của Cây Khung Nhỏ Nhất

TLDR: MST được dùng cho thiết kế mạng (giảm chi phí kết nối), xử lý hình ảnh (phân đoạn), sinh học (cây tiến hóa), mạng xã hội (tìm mối quan hệ quan trọng).

Thiết kế mạng: Cây khung có thể được sử dụng trong thiết kế mạng để tìm số lượng kết nối tối thiểu cần thiết để kết nối tất cả các nút. Cây khung nhỏ nhất đặc biệt có thể giúp giảm thiểu chi phí kết nối bằng cách chọn các cạnh rẻ nhất.
Xử lý hình ảnh: Cây khung có thể được sử dụng trong xử lý hình ảnh để xác định các vùng có cường độ hoặc màu sắc tương tự, hữu ích cho các tác vụ phân đoạn và phân loại.
Sinh học: Cây khung và cây khung nhỏ nhất có thể được sử dụng trong sinh học để xây dựng cây phả hệ biểu diễn mối quan hệ tiến hóa giữa các loài hoặc gen.
Phân tích mạng xã hội: Cây khung và cây khung nhỏ nhất có thể được sử dụng trong phân tích mạng xã hội để xác định các kết nối và mối quan hệ quan trọng giữa các cá nhân hoặc nhóm.

Tham khảo bài viết về "Ứng dụng của Cây Khung Nhỏ Nhất" để hiểu rõ hơn.

So Sánh Các Thuật Toán MST

TLDR: Kruskal tốt cho đồ thị thưa (ít cạnh), Prim tốt cho đồ thị dày (nhiều cạnh), Boruvka có thể song song hóa.

Thuật toán	Cách tiếp cận	Cấu trúc dữ liệu	Độ phức tạp	Phù hợp với
Kruskal	Sắp xếp cạnh, thêm dần	DSU (Union-Find)	O(E log E)	Đồ thị thưa
Prim	Mở rộng từ đỉnh	Priority Queue	O(E log V)	Đồ thị dày
Boruvka	Hợp nhất rừng cây	Priority Queue	O(E log V)	Song song hóa

Một Số Bài Toán Phỏng Vấn Phổ Biến Liên Quan Đến MST

Bài toán cơ bản:

Bài toán nâng cao:

Bài toán ứng dụng:

Tóm Tắt Nhanh

Cây Khung Nhỏ Nhất (MST) là công cụ quan trọng trong:

Tối ưu hóa mạng lưới (thiết kế mạng, đường đi)
Giảm chi phí kết nối
Phân tích dữ liệu và clustering
Xử lý hình ảnh và nhận dạng mẫu

Chọn thuật toán nào?

Đồ thị có ít cạnh → Kruskal
Đồ thị có nhiều cạnh → Prim
Cần xử lý song song → Boruvka