Komplexität des Kruskal-Algorithmus

Question

Ich versuche herauszufinden, was die Komplexität von Kruskals disjunktionsbestimmenden Schleifen ist.

In Kruskal's, fügen wir Scheitelpunkte in disjoint sets und erstellen Vereinigungen dieser Mengen, wenn wir eine Kante, die beide Ecken in verschiedenen Sätzen hat, soweit es mich betrifft. So bestimmen wir Schleifen - wenn zwei Ecken bereits in einer Menge sind, fügen wir diese Kante nicht hinzu.

Wie überprüfen wir, ob ein Vertex in der Menge ist? Meiner Meinung nach ist es in O(n) so Kruskal wäre mindestens in O(n^2) + Sortierzeit der Kanten O(nlogn).

Zum Beispiel hier SO Answer, das ist mein Problem auch, sie sagen, dass es möglich ist, Kruskal in O(V+E) zu laufen, wenn Sie nur zwei Arten von Kanten haben. Ich verstehe es, aber ich bekomme das Ding nicht mit disjunkten Sätzen, ich denke, dass es eine schlechtere Komplexität schafft.

Answer 1

Sie können überprüfen, ob ein Scheitelpunkt in einem Satz ist, indem Sie die disjoint-set container überprüfen.

disjunkte Mengen haben allenfalls O (α (n)) Zeitkomplexität für jeden Betrieb. Hier α ist die inverse Ackerman function, die weniger als 5 für jede Eingabe ist, die Sie oder jemand anderes jemals verwenden wird.

Ein disjunktes Set ist wie ein Wald von Baumstrukturen. Die Wurzel des Baums identifiziert eine Menge eindeutig. Disjunkte Sätze erreichen ihre schwarze Magie, indem sie sicherstellen, dass bei der Verknüpfung von zwei Sätzen diese immer verbunden sind, um den kürzest möglichen Weg zum Ursprung zu finden. Darüber hinaus bricht jedes Mal, wenn eine Set-Mitgliedschaftsprüfung für eine Gruppe durchgeführt wird, jede-Knoten auf dem Pfad zum Stamm so ein, dass diese Knoten jetzt ihre Mitgliedschaft in O (1) Zeit überprüft werden können.

Das Ergebnis ist, dass Kruskal Algorithmus endet O (α (n)) Zeit bei jeder Operation mit der Menge, die praktisch ist das gleiche wie keine Zeit darauf verbringen.