Der Algorithmus von Kruskal |
Ordne alle Kanten nach ihren Kosten. |
Beginne mit einem Baum, der allein aus einer Kante mit minimalen Kosten besteht. |
Füge dann jeweils immer die nächste Kante mit den geringsten Kosten ein, die keinen Zyklus erzeugt. |
Brich damit ab, wenn alle Ecken (Knoten) des Graphen zum Baum gehören. |
Man kann nun sehr leicht zeigen, dass der hier beschriebene Algorithmus eine Lösung findet, wenn es überhaupt Lösungen geben kann. Wir sehen uns einmal den Aufbau des Baumes für ein Beispiel an.
Beim Aufbau des Baumes können Teilgraphen entstehen, die nicht zusammenhängend sind, letzlich müssen aber alle Ecken mit dem Graphen verbunden sein. Anderenfalls gäbe es keine Kante von dieser Ecke zu irgendeiner Ecke des Baumes, was der Forderung nach einem zusammenhängenden Ausgangsgraphen widerspricht.
Wegen des anderenfalls auftretenden Zyklusses sind zwei Ecken gemeinsam mit einem zusammenhängenden Abschnitt nicht möglich. Das angegebene Programm löst die gestellte Aufgabe.
Zur Bewertung dieses Verfahrens wird noch einiges anzumerken sein!