Wie könnte Union / Finden Datenstrukturen Kruskals Algorithmus angewendet werden?

Question

http://en.wikipedia.org/wiki/Disjoint_sets

http://en.wikipedia.org/wiki/Kruskal's_algorithm

Union / Suche Datenstruktur für disjunkte Mengen verwendet wird ...

Answer 1

Es wird in dem Eintrag für Kruskals Algorithmus angegeben, aber Sie können die Vereinigung verwenden / finden Struktur Test (über FIND), wenn der Rand zwei verschiedene Bäume verbindet oder ob sie einen Zyklus bilden, wenn sie hinzugefügt.

Die gleiche Struktur kann aktualisiert werden (via UNION), wenn die Kante an den Spannbaum keinen Zyklus bildet und wird hinzugefügt.