Động lực

Kruskal lưu tập hợp các cạnh đã chọn đang dần phát triển thành rừng trong cấu trúc union-find. Để thêm cạnh một cách an toàn, thuật toán kiểm tra xem hai đầu mút đã nằm trong cùng một tập hợp chưa (nếu rồi, cạnh đó sẽ tạo thành chu trình).

Vì sao nên học Kruskal?

• Cây khung nhỏ nhất trong thực tế: thiết kế mạng, phân cụm và lắp đặt cáp hoặc làm đường với chi phí thấp nhất.
• Union-find: một cấu trúc đẹp mắt, có thể tái sử dụng để theo dõi tính liên thông, xuất hiện trong nhiều lĩnh vực của khoa học máy tính.
• Tính đúng đắn của thuật toán tham lam: một ví dụ khác cho thấy luôn chọn phương án an toàn rẻ nhất sẽ cho ra kết quả tối ưu toàn cục.

Tất cả cây khung nhỏ nhất của một đồ thị đều sử dụng cùng một đa tập trọng số cạnh, vì vậy tổng trọng số (và cạnh lớn nhất) là duy nhất.