Motywacja

Kruskal przechowuje rozrastający się las wybranych krawędzi w strukturze union-find. Aby bezpiecznie dodać krawędź, sprawdza, czy jej dwa końce należą już do tego samego zbioru (co utworzyłoby cykl).

Dlaczego warto poznać algorytm Kruskala?

• Rzeczywiste MST: projektowanie sieci, grupowanie oraz układanie kabli lub dróg przy minimalnym koszcie.
• Union-find: elegancka, wielokrotnego użytku struktura do śledzenia spójności, która pojawia się w wielu dziedzinach informatyki.
• Poprawność algorytmu zachłannego: kolejny przykład, w którym zawsze wybór najtańszej bezpiecznej opcji prowadzi do optimum globalnego.

Wszystkie minimalne drzewa rozpinające grafu wykorzystują ten sam multizbiór wag krawędzi, więc łączna waga (i największa krawędź) jest jednoznacznie określona.