Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


29. Elementare Algorithmen für Graphen



Labyrinthe

Unsere systematische Methode der Betrachtung jedes Knotens und jeder Kante eines Graphen hat eine bemerkenswerte Geschichte: Tiefensuche wurde schon vor Jahrhunderten erstmals formal beschrieben, und zwar als ein Verfahren zum Durchqueren von Labyrinthen. Zum Beispiel ist in Abbildung 29.15 links ein bekanntes Labyrinth dargestellt, und rechts ist der Graph abgebildet, der erzeugt wird, indem an jeder Stelle, wo mehr als ein Weg gewählt werden kann, ein Knoten angeordnet wird und die Knoten dann entsprechend den Wegen verbunden werden. Dies ist wesentlich komplizierter als die noch älteren englischen Gartenlabyrinthe, die als von hohen Hecken umgebene Wege angelegt waren. In diesen Labyrinthen waren alle Mauern mit den äußeren Mauern verbunden, so daß die Damen und Herren hineinspazieren konnten und die klügeren wieder hinausfinden konnten, indem sie einfach so gingen, daß die Mauer stets zu ihrer Rechten blieb (angeblich haben sogar Labormäuse diesen Trick erlernt). Wenn unabhängige Mauern im Inneren vorhanden sein können, ist eine kompliziertere Strategie vonnöten, um sich in einem Labyrinth zurechtzufinden, was uns zur Tiefensuche führt.

Abbildung 29.15
Abbildung 29.15 Ein Labyrinth und ein zugehöriger Graph.

Wenn wir die Tiefensuche anwenden wollen, um in einem Labyrinth von einem Ort zu einem anderen zu gelangen, verwenden wir visit, wobei wir bei dem Knoten des Graphen beginnen, der unserem Ausgangspunkt entspricht. Jedesmal, wenn visit mittels eines rekursiven Aufrufs eine Kante »verfolgt«, gehen wir den entsprechenden Weg im Labyrinth entlang. Der Trick, der zum Erfolg führt, besteht darin, daß wir auf dem Weg, auf dem wir zu dem jeweiligen Knoten gelangt sind, zurückgehen müssen, wenn visit für diesen Knoten abgeschlossen ist. Dadurch kommen wir zurück zu dem Knoten, der sich im Tiefensuchbaum einen Schritt weiter oben befindet und sind bereit, seiner nächsten Kante zu folgen. (Dieser Prozeß entspricht genau der Traversierung des Tiefensuchbaumes für den Graph.) Tiefensuche ist für eine Person zweckmäßig, die in einem Labyrinth etwas sucht, da der »nächste Ort, an dem zu suchen ist«, stets in der Nähe liegt; Breitensuche entspricht eher einer Gruppe von Personen, die etwas suchen, indem sie in alle Richtungen ausschwärmen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]