vorige nächste

Der Aufbau nach dem Algorithmus von Kruskal


Die hinzugefügten Kanten sind fett markiert.
  1. K : 3
  2. F : 4
  3. L : 4 Anmerkung
  4. D : 5
  5. H : 5
  6. I : 5
  7. J : 6
  8. G : 6
  9. C : 7
  10. E : 7
  11. M : 8
  12. B : 8
  13. A : 12

Anmerkung: Da die Kante L auch die Länge 4 hat, hätte sie genau so gut in den Teilgraphen aufgenommen werden können. Der Teilgraph ist in diesem Schritt dann zwar nicht zusammenhängend, das ist beim Algorithmus von Kruskal aber auch nicht notwendig.