Doppelstunde 10: Tiefen- und Breitensuche

In dieser Doppelstunde werden die rekursive Implementation der Baumtraversierung mit der iterativen Implementation verglichen. Die rekursive Variante ist zwar einfacher zu formulieren und zu schreiben, stößt aber bei tiefen Bäumen an ihre Grenzen. Dies kann man mit dem BlueJ-Projekt 12_tiefer_baum (im Ordner Software) demonstrieren. Die Methode erzeugeTiefenBaum(tiefe: int) baut einen Binärbaum auf, in dem die Knoten als rechtes Kind einen Blattknoten haben und als linkes Kind eine beliebig lange Kette von Baumknoten. Man erzeugt einen solchen Baum mit einer Tiefe von mindestens 30.000 Ebenen und holt ihn auf die Objektleiste. Dann lässt man die Baumalgorithmen-Klasse die Anzahl der Knoten im Baum bestimmen. Das Ergebnis wird sein, dass das Programm mit einem „Stack Overflow“-Fehler beendet wird. Der Grund ist, dass der Speicherplatz im Stack-Segment stets relativ gering ist, selbst wenn noch genug Speicherplatz im Daten-Segment (wo beliebige Daten abgelegt werden können, also vom Programmierer angelegte Variablen) vorhanden ist.

Die Präsentation 12_baeume_3.odp zeigt, wie man dieses Problem umgeht, indem man den Stack „manuell“ verwaltet, dazu benötigt man ein eigenes Stack-Objekt, das die noch zu verarbeitenden Baumknoten verwaltet („Todo-Liste“). Auf diese Weise kann auch eine Suche nach einem Knoten mit einer bestimmten Eigenschaft durchgeführt werden. Hierbei handelt es sich um eine Tiefensuche, weil man den Baum zunächst „nach unten“ durchsucht, bevor man weiter zur Seite wandert.

Als Gegenstück dazu wird die Breitensuche demonstriert, indem man als Verarbeitungsstrategie von „Last-in-first-out“ zu „First-in-first-out“ wechselt. Dazu muss die Todo-Liste nur durch eine Queue ersetzt werden. Eine Breitensuche geht beim Suchen „zunächst in die Breite“, weil zuerst die nebeneinanderliegenden Knoten einer Schicht verarbeitet werden, bevor man weiter in die Tiefe geht. Die Unterscheidung zwischen Tiefen- und Breitensuche ist bei Bäumen weniger interessant als bei allgemeinen Graphen, da ein Pfad zu einem bestimmten Knoten im Baum immer eindeutig ist. Wenn es nur einen zu suchenden Knoten gibt, liefern Tiefen- und Breitensuche also dasselbe Ergebnis. In der Unterrichtseinheit zum Thema Graphalgorithmen werden Tiefen- und Breitensuche nochmals thematisiert.

Abschließend kann man feststellen, dass Stack und Queue sich strukturell sehr ähnlich sind. Abgesehen von der Benennung sind die Signaturen der beiden ADTs identisch. Man kann also eine gemeinsame Oberklasse „Container“ definieren, die z.B. push(x: T) und enqueue(x: T) unter dem Namen „einfuegen(x: T)“ zusammenfasst. Auf diese Weise kann man die beiden Suchalgorithmen zusammenfassen und durch Wahl der konkreten Containerstruktur entscheiden, welcher tatsächlich ausgeführt werden soll.

Zur praktischen Umsetzung wird das Aufgabenblatt 12_tiefen_und_breitensuche.odt bearbeitet. Dort werden Tiefen- und Breitensuche in der iterativen Variante implementiert. Man benötigt also die bereits geschriebenen ADTs Stack und Queue aus den vorangegangenen Unterrichtsstunden.

Unterrichtsverlauf: Herunterladen [odt][187 KB]

Weiter zu DS 11: Sudoku [nur LF, optional]