Implementierung von Graphen-Algorithmen im Graphentester
Der Graphentester ist nicht nur für die Erforschung und Simulation von Algorithmen geeignet, sondern auch für die Implementation eigener Algorithmen. Diese können dann genauso im Simulationsfenster ausgeführt und untersucht werden, wie schon fertige Algorithmen. Damit kann die im Leistungsfach geforderte Implementierung mindestens eines Graphenalgorithmus erfüllt werden2.
Dazu muss für jeden Algorithmus eine eigene von der Klasse GraphAlgo abgeleitete Klasse erstellt werden, deren Name mit "GraphAlgo_" beginnt. Diese Klassen werden im Unterordner "eigeneAlgorithmen" abgelegt. Innerhalb dieser Klasse müssen die zwei Methoden getBezeichnung() und fuehreAlgorithmusAus() implementiert werden. getBezeichnung gibt nur den Namen des Algorithmus zurück, der im Graphentester im Simulationsfenster zur Auswahl angezeigt wird. fuehreAlgorithmusAus implementiert den Algorithmus. Dafür stehen folgende Attribute und Methoden bereit:
| Attribute: | |
Graph g |
Referenz auf den kompletten Graph. Eine Beschreibung der wichtigsten Methoden der Klassen Graph, Knoten und Kante befinden sich im Ordner 03_tauschordner. Die vollständige JavaDoc- Dokumentation liegt im Unterordner doc des Graphentesters. |
| Methoden: | |
getStartKnoten() |
liefert den beim Start des Algorithmus ausgewählten Knoten zurück. Wurde kein Knoten ausgewählt, wird der Knoten mit Nummer 0 zurückgegeben. Eine Beschreibung der Klasse Knoten befindet sich im Ordner 03_tauschordner. |
step() |
legt fest, dass der Algorithmus an dieser Stelle im Einzelschrittmodus angehalten werden soll. |
info(String text) |
gibt einen Text im Hilfefenster aus, um den Ablauf des Algorithmus zu beschreiben. Dabei wird automatisch auch der Zustand des Graphen im Hilfefenster gespeichert. Daher sollte die Methode nach der Ausführung der Änderung am Graphen aufgerufen werden, die durch den Text beschrieben wird. |
infoIndentMore() |
die folgenden Infotexte werden eine Ebene tiefer eingerückt. Der zuletzt eingefügte Text wird mit einem Aufklappmechanismus versehen. |
infoIndentLess() |
die Einrückung wird eine Ebene zurückgenommen. |
melde(String text) |
gibt einen Text in einem Popup-Fenster aus, um das Ergebnis eines Algorithmus dem Anwender mitzuteilen. Dabei wird automatisch auch der Befehl info ausgeführt. |
Bei der Implementierung der Algorithmen ist es sinnvoll, viel mit Listen von Knoten und Kanten zu arbeiten. Die Klasse Graph ermöglicht es, Listen aller Knoten/Kanten, die Liste der Nachbarknoten und der ausgehenden/eingehenden Kanten zu erhalten. Dabei kann durch einen Lambda-Ausdruck die Auswahl beschränkt werden (z.B. nur nicht markierte, aber schon besuchte Knoten):
List knoten = g.getAlleKnoten(k->!k.isMarkiert() && k.isBesucht());
Mit Collections.sort(...) können Knoten oder Kanten aufsteigend nach ihrem Wert / Gewicht sortiert werden, da Knoten und Kanten das Interface Comparable implementieren. Dadurch ist es recht einfach, z.B. den Knoten mit dem geringsten Wert zu finden (Dijkstra- oder topologische Sortierung). Natürlich leidet die Performance eines Algorithmus darunter, da die Ermittlung eines kleinsten Elements in O(n) implementiert werden kann und das Sortieren mit anschließendem Entnehmen des ersten Elements in O(n log n) liegt. Hier muss der Fokus aber auf der einfachen Implementierung liegen, da in diesem Bereich nur wenig implementiert wird.
Für viele Algorithmen ist eine toDo-Liste mit noch zu bearbeitenden Knoten / Kanten notwendig. Mit dieser toDo-Liste kann z.B. Tiefen- und Breitensuche realisiert werden, je nachdem ob man ein Schlange oder einen Stapel verwendet. Hier bietet es sich auch an, die selbst geschriebenen Klassen aus dem Kapitel ADT (siehe dort) zu verwenden. In den Musterlösungen wurden sie nicht verwendet, da Sie als Lehrer die Reihenfolge der Unterrichtseinheiten frei wählen können.
Einige Hilfekarten zu Standardimplementationen befinden sich im Ordner 02_kopiervorlagen.
2 Bildungsplan Informatik: 3.3.1.2 (11) einen Algorithmus auf Graphen implementieren (unter Verwendung geeigneter Bibliotheken oder Frameworks)
Unterrichtsverlauf: Herunterladen [odt][298 KB]
Weiter zu Struktur der Arbeitsblätter