5.1 Algorithmus von Kruskal

Ein Algorithmus zur Berechnung des MST ist der Algorithmus von Kruskal:

     Initialisiere einen Wald mit n isolierten Knoten.
     Initialisiere einen Heap mit allen Kanten.
     REPEAT
          entferne die billigste Kante (x,y) aus dem Heap
          union(x,y) (*füge (x,y) in den Wald ein*)
     UNTIL der Wald besteht nur aus einem Baum

Beispiel:

Sei |E| nun die Anzahl der Kanten im Graphen.

Dann gilt: Der Aufwand für den Kruskal-Algorithmus liegt in O(|E| · log |E|) .

Das log |E| kommt dabei vom Entfernen der jeweils billigsten Kante und der erforderlichen Neuordnung des Heaps.

Die Korrektheit des Kruskal-Algorithmus folgt aus dem folgenden Satz:

Satz:

Gegeben: eine Partition V₁,V₂ der Knotenmenge V . Sei s die billigste Kante zwischen V₁ und V₂ . Dann gibt es einen MST der s enthält. ( s ist sogar in allen MST enthalten).

Beweis:

Annahme:

s sei nicht im MST enthalten. Dann füge s in den MST ein. Es entsteht ein Zyklus, der über s' läuft. Entferne nun s' aus dem MST. Es entsteht ein neuer billigerer MST. Dies ist ein Widerspruch zur Minimalität des Ausgangs-MST.