Cách hoạt động?

Cấu trúc union-find duy trì một mảng parent. Mỗi đỉnh ban đầu là gốc của chính nó. Mọi thao tác đều dựa trên hai thao tác sau:

• find(x): lần theo các liên kết parent cho đến khi bạn đến một gốc, tức là đỉnh có đỉnh cha là chính nó. Hai đỉnh được kết nối khi chúng có cùng gốc.
• union(a, b): trỏ một gốc đến gốc còn lại, gộp hai tập hợp.

Thuật toán Kruskal:

1. Xử lý các cạnh theo thứ tự trọng số từ nhỏ nhất đến lớn nhất.
2. Với mỗi cạnh, tìm gốc của hai đầu mút bằng find. Nếu chúng khác nhau, cạnh đó nối hai phần riêng biệt: gộp chúng bằng union rồi cộng trọng số của cạnh vào tổng.
3. Nếu hai gốc giống nhau, cạnh đó sẽ tạo thành một chu trình, vì vậy hãy bỏ qua.

Sau khi xử lý mọi cạnh, các cạnh đã chọn tạo thành MST (với đồ thị liên thông, có đúng n - 1 cạnh).