MST-Algorithmus von Kruskal

Dieser Algorithmus verwendet die Schnitt-Optimalitätsbedingung.

Python Implementierung

Zwei Arten der Implementierung:

1.

Beim Kruskal Algorithmus wählt man immer die Kanten mit minimaler Distanz, die zwei disjunkte Teilbäume miteinander verbinden aus.

2.

• $T=\emptyset$
• Kanten nach Gewichten sortieren
• Kanten durchlaufen
  • Wenn man die Kante zu $T$ hinzufügen kann ohne, dass ein Kreis entsteht, dann fügt man diese Kante zu $T$ hinzu.
• $T$ ist Minimaler Spannbaum