Jak to działa?

Struktura Union-find przechowuje tablicę parent. Każdy wierzchołek początkowo jest własnym korzeniem. Wszystko opiera się na dwóch operacjach:

• find(x): podążaj za odnośnikami parent, aż dotrzesz do korzenia (wierzchołka, który jest własnym rodzicem). Dwa wierzchołki są połączone, gdy mają ten sam korzeń.
• union(a, b): ustaw jeden korzeń jako rodzica drugiego, łącząc oba zbiory.

Algorytm Kruskala:

1. Przetwarzaj krawędzie od najmniejszej wagi do największej.
2. Dla każdej krawędzi użyj find, aby znaleźć korzenie jej końców. Jeśli są różne, krawędź łączy dwie osobne części: użyj union, aby je połączyć, i dodaj jej wagę do sumy.
3. Jeśli korzenie są takie same, krawędź utworzyłaby cykl, więc ją pomiń.

Po przetworzeniu wszystkich krawędzi wybrane krawędzie tworzą MST (dla spójnego grafu jest ich dokładnie n - 1).