Unterabschnitte
Sobald der Graph genau

Kanten hat, können wir abbrechen, da sonst ein Zyklus sofort erzeugt wird.
Die Laufzeit des alleinigen Kruskalalgorithmus ist wegen der Sortierung

. Dazu muß allerdings noch der Zyklentest kommen, der mittels BFS oder DFS in

-mal läuft.