Ψ Die Informatikseite

Menü
Informatik » Bachelor » Algorithmen der Informatik » Kruskal zur Erstellung des MST
Union-Find-Wälder Algorithmen der Informatik Speichermöglichkeiten von Datenmengen mit dynamischer Größe
Unterabschnitte

Kruskal zur Erstellung des MST

Abbruchkriterium

Sobald der Graph genau $\vert V\vert-1$ Kanten hat, können wir abbrechen, da sonst ein Zyklus sofort erzeugt wird.

Laufzeit

Die Laufzeit des alleinigen Kruskalalgorithmus ist wegen der Sortierung $O(\vert E\vert\log\vert E\vert)$. Dazu muß allerdings noch der Zyklentest kommen, der mittels BFS oder DFS in $O(\vert E\vert+\vert V\vert)$ $\vert V\vert-1$-mal läuft.
Union-Find-Wälder Algorithmen der Informatik Speichermöglichkeiten von Datenmengen mit dynamischer Größe