Minimal aufspannende Bäume

• Ein Baum ist eine Teilmenge von Kanten eines Graphen, die keinen Kreis (bzw. eine Tour von einem Ort zu sich selbst) enthält, wobei jeder Knoten von jedem aus erreichbar sein muss (siehe Beispiel rechts).

 

• Wir suchen einen Baum mit minimaler Summe von Knotengewichten (minimaler aufspannender Baum).

• Algorithmus:

• Starte mit leerem Baum

• Wähle in jedem Schritt eine Kante minimalen Gewichts, die keinen Kreis erzeugt

Neu hinzugenommene Kante

Kante im Baum

Abgelehnte Kante die Kreis erzeugt