✨Thuật toán Kruskal
Thuật toán Kruskal là một thuật toán trong lý thuyết đồ thị để tìm cây bao trùm nhỏ nhất của một đồ thị liên thông vô hướng có trọng số. Nói cách khác, nó tìm một tập hợp các cạnh tạo thành một cây chứa tất cả các đỉnh của đồ thị và có tổng trọng số các cạnh là nhỏ nhất.Thuật toán Kruskal là một ví dụ của thuật toán tham lam.
Thuật toán này xuất bản lần đầu tiên năm 1956, bởi Joseph Kruskal.
Một vài thuật toán khác cho bài toán này bao gồm thuật toán Prim, thuật toán xóa ngược, và thuật toán Borůvka.
Bài toán dẫn nhập
Cho một đồ thị có trọng số với n đỉnh. Yêu cầu tìm ra cây khung nhỏ nhất.
Tư tưởng thuật toán
Thuật toán Kruskal dựa trên mô hình xây dựng cây khung nhỏ nhất bằng thuật toán hợp nhất. Thuật toán không xét các cạnh với thứ tự tuỳ ý. Thuật toán xét các cạnh theo thứ tự đã sắp xếp theo trọng số.
Để xây dựng tập n-1 cạnh của cây khung nhỏ nhất - tạm gọi là tập K, Kruskal đề nghị cách kết nạp lần lượt các cạnh vào tập đó theo nguyên tắc như sau: Ưu tiên các cạnh có trọng số nhỏ hơn. Kết nạp cạnh khi nó không tạo chu trình với tập cạnh đã kết nạp trước đó. Đó là một nguyên tắc chính xác và đúng đắn, đảm bảo tập K nếu thu đủ n - 1 cạnh sẽ là cây khung nhỏ nhất.
Mô tả thuật toán
Giả sử ta cần tìm cây bao trùm nhỏ nhất của đồ thị G. Thuật toán bao gồm các bước sau.
- Khởi tạo rừng F (tập hợp các cây), trong đó mỗi đỉnh của G tạo thành một cây riêng biệt
- Khởi tạo tập S chứa tất cả các cạnh của G
- Chừng nào S còn khác rỗng và F gồm hơn một cây Xóa cạnh nhỏ nhất trong S Nếu cạnh đó nối hai cây khác nhau trong F, thì thêm nó vào F và hợp hai cây kề với nó làm một ** Nếu không thì loại bỏ cạnh đó. Khi thuật toán kết thúc, rừng chỉ gồm đúng một cây và đó là một cây bao trùm nhỏ nhất của đồ thị G.
Mã giả
Cho đồ thị G=(X, E).
Bước 1: Sắp xếp các cạnh của đồ thị theo thứ tự trọng số tăng dần. Bước 2: Khởi tạo T:= Ø Bước 3: Lần lượt lấy từng cạnh thuộc danh sách đã sắp xếp. Nếu T+{e} không chứa chu trình thì gán T:=T+{e}. Bước 4: Nếu T đủ n-1 phần tử thì dừng, ngược lại làm tiếp bước 3.
Kỹ thuật đánh nhãn đỉnh
Kỹ thuật đánh nhãn đỉnh Trong thuật toán Kruskal, để kiểm tra xem T + {e} có chứa chu trình hay không ta có thể dùng kỹ thuật gắn nhãn đỉnh, kỹ thuật này khá đơn giản và hiệu quả. *Ngay sau bước 1 của thuật toán, ta gắn đỉnh i của đồ thị một nhãn là i *Trong bước 2: Nếu hai đầu cạnh e có cùng nhãn (tức là nhãn của e.v1 và nhãn của e.v2 bằng nhau) thì T+{e} tạo chu trình, ta không đưa e vào T. *Ngược lại [nếu Label(e.v1)!= Label(e.v2) ] thì ta đưa e vào T và thực hiện công việc ghép nhãn bằng cách: lab1 = Min(Label(e.v1), Label (e.v2)) lab2 = Max(Label(e.v1), Label (e.v2)) Sửa nhãn của tất cả các đỉnh nào có nhãn là lab2 thành nhãn lab1