Minimal spannende Bäume (minimal spanning tree)

Begriffe: Minimaler Spannbaum, gewichteter Graph, Zusammenhangskomponente

Der Bildungsplan schreibt vor, einen Algorithmus zur Bestimmung eines minimal spanning trees zu behandeln (Kruskal oder Prim). Es ist sinnvoll, diesen Algorithmus am Ende der Einheit anzusiedeln, da es sich bei den beiden vorgeschlagenen Algorithmen um Greedy-Algorithmen handelt, die aber im Gegensatz zu den anderen Greedy-Algorithmen keine Näherungslösung, sondern die optimale Lösung liefern. Damit wird die Einheit zu den Graphen abgerundet.

Zu beiden Algorithmen gibt es im Internet jede Menge Videos und Erklärungen. Allerdings sind diese Beschreibungen ungenau oder nicht so leicht in Code umzusetzen:

Kruskal:

Hier wird meistens lapidar gesagt, dass eine Kante nicht hinzugefügt werden darf, wenn dadurch der Graph einen Zyklus bekommt. Das ist in der Adlerperspektive leicht zu erkennen, in der Froschperspektive aber nicht. Daher ist es bei der Implementierung nicht so einfach, einen Zyklus zu erkennen. Dazu müsste man jedes Mal eine Tiefen- oder Breitensuche durchführen.

Alternativ kann man die Knoten einfärben und diese Farben nutzen, um zu erkennen, ob ein Zyklus vorliegt. Jede Zusammenhangskomponente des neu entstehenden minimal spanning trees (während der Ausführung des Algorithmus ist es noch ein Wald) bekommt eine eigene Farbe. Ist der ganze Graph in einer Farbe eingefärbt, ist der minimal spanning tree gefunden. Die Knoten werden nach einfachen Regeln (siehe Aufgabenblatt) eingefärbt. Beim Zusammenführen zweier Zusammenhangskomponenten werden alle Knoten der zweiten Komponente mit der Farbe der ersten Komponente eingefärbt. Dies kann man entweder mit Tiefen- oder Breitensuche oder mit einer Schleife über alle Knoten, bei der jeder Knoten einer bestimmten Farbe umgefärbt wird, bewerkstelligen. Außerdem wird durch das Einfärben der Zusammenhangskomponenten die grundsätzliche Arbeitsweise des Algorithmus besser sichtbar.

Ein Greedy-Algorithmus ist der Kruskal-Algorithmus, da in jedem Schritt die günstigste Kante ausgewählt wird, die nicht zu einem Zyklus führt.

Prim (gesprochen wie "Primm"):

Bei diesem Algorithmus wird in der Literatur oft mit Schnitten durch den Graph argumentiert. Man müsste also erst mal klären, was ein Schnitt überhaupt ist. Darauf kann man aber auch verzichten. Wichtig ist nur, dass man nicht wie bei Kruskal viele einzelne Teilbäume allmählich zu einem Baum zusammenführt, sondern hier einen Baum sukzessive erweitert. Diese Erweiterung erfolgt durch Hinzufügen der kürzesten Kante, die einen Knoten aus dem bisherigen Baum mit einem Knoten aus dem restlichen Graphen verbindet. Diese Aufteilung in zwei (nicht leere) Knotenmengen heißt Schnitt. Dieser Schnitt wird für den Beweis der Korrektheit benötigt, der in der Schule aber keine Rolle spielt.

Markiert man jeden Knoten, den man dem Baum hinzufügt, sucht man also die kürzeste Kante, bei der genau einer der anliegenden Knoten markiert ist. Da auch hier immer die kürzeste Kante gewählt wird, ist auch Prim ein Greedy-Algorithmus.

Zur Erarbeitung eines der Algorithmen könnte man die Schülerinnen und Schüler gut mit dem Graphentester den fertigen Algorithmen untersuchen und ihn beschreiben lassen. Das Hilfefenster des Graphentesters bietet dabei zusätzliche Unterstützung. Dann wenden die Schülerinnen und Schüler den Algorithmus auf einen weiteren Graphen an, um ihr Verständnis zu festigen.

Zur Erfüllung des Bildungsplans reicht es dabei, einen der beiden Algorithmen zu untersuchen. Schnelle Schülerinnen und Schüler können aber auch beide Algorithmen analysieren. Eine schöne Ergänzung bietet der Bezug zum Traveling Salesman Problem, da beide Algorithmen nur leicht verändert werden müssen (siehe Hintergrund.odt), um als Näherungsalgorithmus für das TSP zu dienen.

Unterrichtsverlauf: Herunterladen [odt][298 KB]

Weiter zu Weitere Übungen