9.5 Minimum Spanning Tree

Gegeben: Ungerichteter Graph G = (V,E) , gewichtet mit Kostenfunktion.
Gesucht: Billigster Spannbaum.

Idee von Kruskal:

Lasse einen Wald wachsen mit der jeweils billigsten, zulässigen Kante.

Initialisiere Wald mit n isolierten Knoten;
initialisiere Heap mit allen Kanten gemäß ihrer Kosten.

REPEAT
   entferne billigste Kante e aus Heap;
   falls e keinen Kreis verursacht
      dann fuege e in Wald ein.
UNTIL  Wald besteht aus einem Baum

Gewichteter Graph mit Minimum Spanning Tree

Testen der Endpunkte und Vereinigen der Teilbäume werden mit der Union-Find-Prozedur in O(1) gelöst. Die jeweils billigste Kante liefert ein Heap in O(log |E|) .
Also benötigt ein Prozessor O(|E| · log |E|) .
Unter Verwendung des Pipeline-Heap-Algorithmus benötigen log |E| Prozessoren O(|E|) .