Der Algorithmus von Kruskal
Ein weiterer Greedy-Algorithmus zur Berechnung eines minimalen aufspannenden Baumes ist der Algorithmus von Kruskal. Dieser 1956 von Joseph Kruskal (ebenfalls von den Bell Labs) veröffentlichte Algorithmus untersucht in jedem Schritt eine billigste unbehandelte Kante und wählt diese, falls sie keinen Kreis schließt. Anders al der Algorithmus von Prim wird also nicht von einem Knoten ausgegangen. Stattdesen startet man mit allen Knoten und verschmilzt in jedem Schritt zwei Zusammenhangskomponenten zu einer neuen, bis ein aufspannender Baum entsteht.
Dieser Algorithmus ist sogar noch etwas einfacher zu programmieren als der Algorithmus von Prim, wenn man das Handling der Zusammenhangskomponenten geschickt betreibt. Die Idee dabei ist, dass in jedem Knoten eine Markierung gespeichert wird, die besagt, zu welcher Zusammenhangskomponente dieser Knoten gehört. Hat man nun eine Kante als Kandidat gewählt, so vergleicht man nur, ob die beiden Endknoten die gleiche Markierung haben. Ist dies der Fall, so läßt man diese Kante außen vor. Anderenfalls wählt man die Kante und verschmiltz die beiden Zusammenhangskomponenten, indem man die Markierungen aktualisiert.
Das Ergebnis des Algorithmus wird in dem folgenden Applet gezeigt.
Dieser Algorithmus ist sogar noch etwas einfacher zu programmieren als der Algorithmus von Prim, wenn man das Handling der Zusammenhangskomponenten geschickt betreibt. Die Idee dabei ist, dass in jedem Knoten eine Markierung gespeichert wird, die besagt, zu welcher Zusammenhangskomponente dieser Knoten gehört. Hat man nun eine Kante als Kandidat gewählt, so vergleicht man nur, ob die beiden Endknoten die gleiche Markierung haben. Ist dies der Fall, so läßt man diese Kante außen vor. Anderenfalls wählt man die Kante und verschmiltz die beiden Zusammenhangskomponenten, indem man die Markierungen aktualisiert.
Das Ergebnis des Algorithmus wird in dem folgenden Applet gezeigt.
| Die Implementation dieses Algorithmus wollen wir nicht verraten. Bitte probieren Sie es selbst! Als Hilfe geben wir jedoch die einzelnen Schritte in CindyScript als Kommentare vor. Damit erhalten wir folgenden Pseudocode: |
// Algorithmus von Kruskal
// Erzeuge eine Liste aller Knoten und speichere sie unter einem geeigneten Namen
// Jeder Knoten bildet zunächst eine eigene Zusammenhangskomponente.
// Markiere jeden Knoten mit dem Namen dieser Zusammenhangskomponente
// Hinweis: Den Namen eines Knotens v bekommt man mit v.label
// Erzeuge eine Liste aller Kanten und speichere sie unter einem geeigneten Namen
// Sortiere die Kantenliste aufsteigend nach Gewicht und speichere diese sortierte Liste
// Färbe alle Kanten rot und halbdurchsichtig
// Durchlaufe alle Kanten, in der Reihenfolge des aufsteigenden Gewichts
// Lies die beiden Endknoten der Kante
// In welchen Komponenten liegen die Knoten?
// Teste, ob die aktuelle Kante zwei Zusammenhangskomponenten verbindet
// Ja, die aktuelle Kante ist eine Baumkante!
// Färbe sie grün und ganz sichtbar
// Markiere beide Zusammenhangskomponenten als eine!
// Gehe dazu alle Knoten durch und setze bei einer Komponente die Markierung um
// Ende: Alle Knoten durchgehen
// Ende: Test auf Zusammenhangskomponenten
// Ende: Durchlaufe aller Kanten