How it works?

Union-Find verwaltet ein parent-Array. Jeder Knoten beginnt als seine eigene Wurzel. Zwei Operationen steuern alles:

• find(x): Folge den parent-Links, bis du eine Wurzel erreichst (ein Knoten, der sein eigener Elternknoten ist). Zwei Knoten sind verbunden, wenn sie dieselbe Wurzel teilen.
• union(a, b): Lasse eine Wurzel auf die andere zeigen, wodurch die beiden Mengen zusammengeführt werden.

Kruskals Algorithmus:

1. Verarbeite die Kanten vom kleinsten zum größten Gewicht.
2. find für jede Kante die Wurzeln ihrer Endpunkte. Wenn sie sich unterscheiden, verbindet die Kante zwei separate Teile: Führe sie mit union zusammen und addiere ihr Gewicht zur Gesamtsumme.
3. Wenn die Wurzeln gleich sind, würde die Kante einen Zyklus bilden, also überspringe sie.

Nach der Verarbeitung jeder Kante bilden die gewählten Kanten den MST (bei einem zusammenhängenden Graphen sind es genau n - 1).