Thuật toán Kruskal

Sắp xếp các cạnh, lấy cạnh ngắn nhất, không bao giờ khép vòng. Thuật toán Kruskal có lẽ là thuật toán tham lam đơn giản nhất, vậy mà nó luôn tìm ra cách rẻ nhất để nối mọi đỉnh của đồ thị.

Một đồ thị có nhiều mảnh cây cùng lớn dần, một cạnh bị bỏ qua vì sẽ tạo chu trình được vẽ nét đứt màu đỏ, và danh sách các cạnh còn chờ thử bên dưới
Một đồ thị có nhiều mảnh cây cùng lớn dần, một cạnh bị bỏ qua vì sẽ tạo chu trình được vẽ nét đứt màu đỏ, và danh sách các cạnh còn chờ thử bên dưới

Ý tưởng

Cây khung nhỏ nhất nối mọi đỉnh của một đồ thị có trọng số với tổng độ dài cạnh nhỏ nhất có thể. Thuật toán Kruskal không phát triển một cây từ điểm xuất phát. Nó nhìn toàn bộ đồ thị cùng lúc, bắt đầu với mỗi đỉnh là một phần riêng, và liên tục nối các phần bằng cạnh ngắn nhất còn dùng được cho đến khi chỉ còn một phần.

Từng bước

Sắp xếp các cạnh từ ngắn nhất đến dài nhất. Thử chúng theo thứ tự đó. Nếu hai đầu của một cạnh nằm ở hai phần khác nhau, thêm nó vào cây: hai phần trở thành một. Nếu cả hai đầu đã ở cùng một phần, cạnh sẽ tạo chu trình, nên bỏ qua. Với n đỉnh, cây hoàn chỉnh sau n − 1 cạnh, và các cạnh còn lại không cần xét đến.

Một ví dụ

Lấy các cạnh A–B dài 1, B–C 2, A–C 3, C–D 4 và B–D 5. Kruskal thêm A–B, rồi B–C, nối C vào phần A–B. Tiếp theo là A–C, nhưng A và C đã ở cùng một phần, nên nó sẽ tạo chu trình A–B–C và bị bỏ qua. C–D nối D vào, và giờ cả bốn đỉnh tạo thành một cây ba cạnh, tổng độ dài 7. B–D, cạnh dài nhất, thậm chí không bao giờ được thử.

Union-find

Câu hỏi khó duy nhất mà thuật toán Kruskal đặt ra là: hai đỉnh này đã ở cùng một phần chưa? Cấu trúc union-find trả lời câu hỏi đó. Mỗi phần là một cây nhỏ gồm các liên kết trỏ đến một đại diện. Find đi theo các liên kết đến đại diện; union treo đại diện này dưới đại diện kia. Nén đường đi, cho mọi đỉnh đã đi qua trỏ thẳng đến đại diện, cùng với hợp theo kích thước giữ các liên kết ngắn đến mức mỗi câu hỏi gần như chỉ mất thời gian hằng số.

Lịch sử và tốc độ

Joseph Kruskal công bố thuật toán năm 1956, trong một bài báo ngắn trên Proceedings of the American Mathematical Society. Sắp xếp các cạnh là phần chậm nhất, nên khối lượng công việc tăng theo E log E với E cạnh. Nếu các cạnh đã được sắp xếp sẵn, hoặc độ dài là các số nguyên nhỏ, nó gần như tuyến tính.

Khám phá

Mở ứng dụng và nhấn Bước. Các cạnh còn chờ thử được liệt kê dưới đồ thị, ngắn nhất đứng đầu. Mỗi cạnh nối hai phần chuyển sang màu xanh lá; mỗi cạnh sẽ tạo chu trình được vẽ nét đứt màu đỏ. Hãy xem nhiều phần nhỏ lớn dần ở các vùng khác nhau của đồ thị rồi gộp lại, và để ý rằng các cạnh cuối thường không bao giờ được thử.

Câu hỏi thường gặp

Vì sao thuật toán Kruskal sắp xếp các cạnh?

Để mỗi cạnh nó thêm vào là cạnh ngắn nhất vẫn còn nối hai phần. Lựa chọn tham lam đó luôn an toàn nhờ tính chất lát cắt, và mọi cạnh bị bỏ qua đều là cạnh dài nhất trên chu trình mà nó sẽ tạo, nên không bao giờ cần đến.

Cấu trúc tập hợp rời nhau là gì?

Một tên khác của union-find: cấu trúc giữ một tập các tập hợp riêng biệt, ở đây là các phần của rừng đang lớn dần, có thể cho biết một phần tử thuộc tập nào và gộp hai tập nhanh chóng.

Thuật toán Kruskal có dùng được trên đồ thị không liên thông không?

Có. Nó đơn giản kết thúc với một cây cho mỗi phần liên thông của đồ thị, tức một rừng khung nhỏ nhất, vì không cạnh nào có thể nối các phần không liên thông với nhau.

Thuật toán Kruskal còn được dùng vào việc gì khác không?

Dừng nó sớm, trước khi các phần cuối cùng gộp lại, sẽ chia các đỉnh thành các cụm, đó là phân cụm liên kết đơn. Chạy nó trên một lưới có độ dài cạnh ngẫu nhiên sẽ tạo ra một mê cung.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Thử thuật toán Kruskal