Algorithmus - Kruskal-Algorithmus

• Involvierte Definitionen:
  • Graph
  • Zusammenhang
  • Spannbaum
  • Greedy-Algorithmus
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Algorithmus: Kruskal-Algorithmus

Sei ein zusammenhängender Graph.
Die Kanten seien außerdem mit Gewichten (in ) ausgestattet. Hierfür sei die Gewichtsfunktion.

Die Kanten des Graphen seien in einer aufsteigend sortierten Liste gegeben.

• Setze .
• For to
  • Falls durch Hinzufügen von zu kein Kreis entsteht, setze .

Anmerkung

Beispiel ohne Kantengewichte

Beispiel mit Kantengewichten