Graphenalgorithmen

Gegeben ist ein Labyrinth, etwa wie in Bild 1 dargestellt. Das Labyrinth hat ein Eingangsfeld und ein von dort erreichbares Ausgangsfeld; gesucht ist ein Weg vom Eingang des Labyrinths bis zum Ausgang.

Algorithmus

Der folgende Algorithmus berechnet die kürzesten Wege, gemessen in Anzahl der durch­laufenen Felder, vom Eingangsfeld zu allen anderen Feldern des Labyrinths und damit auch zum Ausgangsfeld.

Algorithmus Kürzester Weg durch ein Labyrinth

Eingabe:

Ein Labyrinth wie in Bild 1 dargestellt

Ausgabe:

Kürzester Weg vom Eingang des Labyrinths bis zum Ausgang

Methode:

1. setze i = 0

markiere das Eingangsfeld mit der Zahl 0

solange nicht alle Felder markiert sind wiederhole

1. für jedes mit der Zahl i markierte Feld f wiederhole
1. verbinde f mit allen noch nicht markierten Nachbarfeldern und markiere diese mit i+1

setze i = i+1

gib die Folge der Felder entlang der Verbindungen vom Ausgang zum Eingang in umgekehrter Reihenfolge aus

Bild 2 zeigt die Markierungen der Felder und die auf diese Weise berechneten Verbindungen zwischen den Feldern.

Modellierung

Wir modellieren das Problem durch einen ungerichteten Graphen. Die Knoten des Graphen entsprechen den Feldern des Labyrinths; zwei Knoten sind durch eine Kante verbunden, wenn die entsprechenden Felder benachbart sind. Bild 3a zeigt den entsprechenden Graphen für das Labyrinth aus Bild 1. Der Kürzeste-Wege-Algorithmus entspricht einer Breitensuche (engl.: breadth-first search) in dem zugehörigen Graphen. Die erzeugten Wege bilden einen Baum mit dem Startknoten als Wurzel, einen Breiten­such­baum (Bild 3b).

Der Algorithmus verwendet die Daten­struktur einer Schlange (Queue), um zu gewähr­leisten, dass die Knoten in der richtigen Reihenfolge, also breadth-first, besucht werden.

Zu jedem Knoten v bedeuten distance(v) die bisher gefundene kürzeste Entfernung zum Startknoten und predecessor(v) den zugehörigen Vorgänger im Baum. Auf diese Weise lässt sich der gesamte Breiten­such­baum darstellen.

Algorithmus Breitensuche

Eingabe:

Zusammenhängender ungerichteter Graph G = (V, E) mit V = {0, ..., n-1}, Startknoten s

Ausgabe:

Kürzeste Wege vom Startknoten s zu allen Knoten

Methode:

1. setze distance(s) = 0

setze predecessor(s) = -1

markiere s als besucht

hänge Knoten s an die Schlange an

solange die Schlange nicht leer ist wiederhole

1. entnimm den vordersten Knoten u aus der Schlange

für alle Nachbarknoten v von u wiederhole

1. wenn v noch nicht als besucht markiert ist dann
1. setze distance(v) = distance(u)+1

setze predecessor(v) = u

markiere v als besucht

hänge Knoten v an die Schlange an

Der Weg von einem bestimmten Knoten v zurück zum Startknoten s lässt sich anhand der Vorgänger zurück­verfolgen.

Implementierung

Die folgende Klasse BreadthFirstTree berechnet die kürzesten Wege in einem Graphen vom Startknoten s zu allen anderen Knoten, sofern diese vom Startknoten aus erreichbar sind. Die Klasse basiert auf einer Klasse RootedTree, in der alle Daten und Methoden zum Aufbau des Breiten­such­baums zur Verfügung stehen. Mit den Methoden toTree und inTree wird Buch darüber geführt, welche Knoten schon besucht worden sind, d.h. schon zum bisher berechneten Baum der kürzesten Wege dazugehören.

Für das Durchlaufen aller Nachbarn eines Knotens wird ein NeighbourIterator verwendet.

Mit der Anweisung

werden die kürzesten Wege in einem Graphen g von einem Startkonten s zu allen anderen Knoten berechnet. Mit den Methoden getDistance und getPredecessor kann anschließend für jeden Knoten die Entfernung zum Startknoten und der jeweilige Vorgänger im Baum ermittelt werden. Die Methode getPathTo liefert die Folge der Knoten vom Startknoten s zu einem Knoten v.

Die im Algorithmus verwendete Queue lässt sich auf Basis einer LinkedList implementieren.

Zusammenfassung

Wir haben ein konkretes Problem als graphen­theoretisches Problem modelliert.

Mit dem Verfahren Breitensuche (breadth-first search) lassen sich die kürzesten Wege in einem Graphen bestimmen. Die Länge eines Weges bemisst sich dabei nach der Anzahl der durch­laufenen Kanten, d.h. jeder Kante wird die Länge 1 zugeordnet.

Häufig werden Probleme durch Graphen modelliert, deren Kanten selbst bereits mit bestimmten Längen oder Gewichten markiert sind. Um die kürzesten Wege in einem Graphen mit Kanten­gewichtung zu finden, ist das Verfahren Kürzeste Wege geeignet.

Wie bereits bemerkt, ist Breitensuche nicht möglich, wenn wir uns real in einem Labyrinth befinden, weil wir dann immer nur Zugriff auf die direkten Nachbar­felder desjenigen Feldes haben, auf dem wir uns gerade befinden. In diesem Fall lässt sich das Verfahren Tiefensuche (depth-first search) anwenden; allerdings findet es nicht unbedingt den kürzesten Weg. Tiefensuche in einem realen Labyrinth angewandt geht so: Wir tasten uns immer an der rechten Wand entlang, dann kommen wir irgendwann zu einem Ausgang.