Union-Find-Wälder

Union-Find-Wälder werden dazu benutzt, um die Zusammenhangskomponenten von ungerichteten Graphen zu bestimmen.

Wir starten mit trivialen Zusammenhangskomponenten, in der jeweils ein Knoten vorhanden ist. Wir verringern zwei getrennte Zusammenhangskomponenten zu einer, wenn es eine Kante zwischen zwei in diesen beiden Bäumen enthaltenen Knoten gibt. Um alle Kanten zu bestimmen, gehen wir die alle Adjazenzlisten durch.

Union-Find-Bäume werden vereiningt, indem der jeweils kleinere Baum an den größeren gehängt wird. Die Größe wird zur Laufzeitoptimierung bei jedem Baum mitgespeichert.

Einen Zyklus haben wir gefunden, wenn wir einen Baum des Waldes mit sich selbst vereinigen sollen.

Der Wurzelknoten eines Baumes kann mit gefunden werden, da der Baum für jeden inneren Knoten mindestens 2 Söhne hat. Die Vereinigung geschieht in konstanter Zeit . Führen wir den Union-Find-Algorithmus n-mal aus, so erhalten wir als Kosten .

---