Graphen sind eine abstrakte Struktur, die es uns erlaubt, Zustände (als Knoten) und deren Zusammenhänge (als Kanten zwischen den Knoten) einfach darzustellen.
In der Informatik finden Graphen für unterschiedlichste Probleme eine Verwendung. Wir betrachten für unseren Zweck das "Pathfinding" Problem. Wir versuchen (oftmals so schnell wie möglich) von einem Punkt A zu einem Punkt B zu gelangen.
Die Visualisierung rechts zeigt auf der oberen Hälfte einen solchen Graphen. In diesem Beispiel ist das Ziel, von Zuhause einen Weg zur Schule, das Gymnasium Muttenz, zu finden. Es gibt verschiedene Wege um zum Ziel zu gelangen. Wir laufen auf dem Weg zum Gym Muttenz jeweils immer mindestens an einer anderen Schule vorbei.
Betrachten Sie den Graphen auf der rechten Seite und versuchen Sie zu verstehen, was dargestellt wird. Vergleichen Sie den Graphen mit Google Maps. Der grüne Knoten ist immer der Startknoten. Der rote ist der Zielknoten. Jeder Knoten steht hier für einen Zustand. Der Startknoten bedeutet verdeutscht also: "Ich bin Zuhause". Von diesem Zustand kann ich mich in einer Minute zu den folgenden Zuständen bewegen:
Das Traversieren einer Kante, also das Ändern des Zustandes, ist mit Kosten verbunden, welche neben der jeweiligen Kante angegeben sind. In unserem Beispiel handelt es sich der Einfachheit halber um einen ungewichten Graphen, da alle Kanten gleichteuer sind (es dauert immer genau eine Minute um von der einten Schule zur nächsten zu laufen). Wir betrachten zu einem späteren Zeitpunkt noch gewichtete Graphen.
Wir wollen nun so schnell wie möglich vom Startknoten "Zuhause" zum Zielknoten "Schule" zu gelangen. Für Sie mag die Antwort zu dieser Frage offensichtlich klingen. Doch in der Praxis sollte ein Algorithmus in der Lage sein, für zwei beliebige Orte den schnellsten Weg zu ermitteln. Auch dann, wenn es mehrere Tausend oder gar mehrere Millionen mögliche Wege vom Start zum Ziel gibt. Dafür eignen sich Suchbäume, um verschiedene Wege strukturiert abzubilden.
In der unteren Hälfte ist der Suchbaum des Graphen abgebildet. Bäume bestehen auch aus Knoten und Kanten. (Auch hier gilt, der grüne Knoten ist der Startknoten, der rote ist der Zielknoten.) In einem Baum können Pfade durch einen Graphen abgebildet werden.
Im Einführungsbeispiel ist ein möglicher Schulweg ans Gymnasium Muttenz abgebildet. Es gibt verschiedene Wege, wie Sie zur Schule laufen können. Grundsätzlich möchten Sie natürlich möglichst schnell von Zuhause (Das Hochhaus an der Birsfelderstrasse 51) aus an der Schule ankommen. An den Kanten ist jeweils beschrieben, wie lange es dauert, von der einten Strasse zu nächsten zu laufen.
Im Baum rechts sind fünf mögliche Wege zum Ziel dargestellt, das sind aber nicht alle! (mehr dazu noch später) Es gibt unendlich viele Wege, da Sie sich im Kreis drehen können. Ein Beispiel dafür wäre, wenn Sie von Zuhause zum BBZBL, dann zur FMS und dann wieder zurück nach Hause laufen würden. Dies könnten Sie ja beliebig oft wiederholen.
Es gibt drei schnellste Wege in diesem Beispiel.
Von Zuhause über die FMS zur Schule
Von Zuhause über das BBZBL zur Schule
Von Zuhause über die FOS Mittelschule zum Gymnasium
Alle drei sind schnellste Wege, da die Summe der Kosten der Kanten bei diesen drei Wegen minimal (2) sind.
Es gibt keinen anderen Weg, bei dem Sie mit zwei Schritten (also in zwei Minuten) bei der Schule sind.
Bemerkung zur Lösung: Da der Graph zyklisch ist, würde der Baum unendlich gross werden. Um dies bei der Lösung zu verhindern, wurden Teile des Baumes weggeschnitten, mehr dazu aber später.