Graphenalgorithmus: Graphen modellieren und lösen

Ein Graph ist eine abstrakte Struktur. Er besteht aus Objekten und den Verbindungen zwischen ihnen. Die Objekte heißen Knoten (auch Ecken). Die paarweisen Verbindungen heißen Kanten (manchmal auch Bögen). Man zeichnet Knoten meist als Punkte und Kanten als Linien.

Ein U-Bahn-Netz ist ein gutes Beispiel: Jeder Knoten stellt eine U-Bahn-Station dar und jede Kante eine direkte Zugverbindung zwischen zwei Stationen. Auch andere Dinge lassen sich so beschreiben. In der chemischen Graphentheorie sind die Atome eines Moleküls die Knoten und die Molekularverbindungen die Kanten. Das Internet ist ein riesiger Graph aus Computern und Datenverbindungen.

Kanten können gerichtet oder ungerichtet sein. Bei einem ungerichteten Graphen haben die Kanten keine Richtung: Jede Kante kann in beide Richtungen durchlaufen werden. Bei einem gerichteten Graphen (auch Digraph genannt) zeichnet man Pfeile, die vom Anfangsknoten zum Endknoten zeigen. Jede Kante kann dann nur in eine Richtung durchlaufen werden. Zwei Knoten heißen benachbart, wenn eine Kante sie verbindet.

Manchmal reicht es nicht zu wissen, welche Knoten verbunden sind. Dann bekommen die Kanten ein Gewicht. In einem Straßennetz könnte das Gewicht zum Beispiel die Entfernung zwischen zwei Orten sein.

Im Computer gibt es im Wesentlichen zwei gebräuchliche Formen, einen Graphen zu speichern: die Adjazenzliste und die Adjazenzmatrix. Praktisch jede algorithmische Lösung für Graphenprobleme greift auf mindestens eine der beiden zurück.

Bei der Adjazenzliste gibst du für jeden Knoten eine Liste an. In einem ungerichteten Graphen stehen darin alle seine Nachbarn, in einem gerichteten Graphen alle seine Nachfolger. Die Reihenfolge der Knoten in der Liste ist beliebig. Im einfachsten Fall speichert man in einem Array für jeden Knoten eine einfach verkettete Liste aller Nachbarn.

Die Adjazenzmatrix ist eine Tabelle mit einer Zeile und einer Spalte für jeden Knoten. Bei n Knoten ist sie eine n × n-Matrix. Der Eintrag in Zeile i und Spalte j sagt, ob eine Kante vom i-ten zum j-ten Knoten führt. Eine 0 bedeutet: keine Kante. Eine 1 bedeutet: Es gibt eine Kante. Bei einem ungerichteten Graphen ist (i, j) genau dann eine Kante, wenn auch (j, i) eine ist. Darum ist seine Matrix immer symmetrisch.

Beide Formen haben Vor- und Nachteile. Die Matrix ist leicht umzusetzen, und man sieht direkt am Eintrag, ob zwei Knoten verbunden sind. Dafür braucht sie Speicher für n × n Einträge. Deshalb wird sie für Graphen in der Praxis selten genutzt.

Breitensuche und Tiefensuche besuchen die Knoten eines Graphen der Reihe nach. Damit das Ergebnis eindeutig ist, legt man vorher fest, in welcher Reihenfolge die Nachbarn eines Knotens drankommen. Zum Beispiel nimmt man die Reihenfolge der Adjazenzliste. Auch der Startknoten und die Frage, ob der Graph gerichtet ist, können die Reihenfolge ändern.

Breitensuche: Du wählst einen Startknoten, markierst ihn als gesehen und legst ihn in eine Warteschlange. Dann wiederholst du: Nimm den vordersten Knoten aus der Warteschlange. Hänge alle seine noch nicht markierten Nachfolger hinten an und markiere sie als gesehen. Ist die Warteschlange leer, ist die Suche zu Ende. So werden zuerst alle Knoten besucht, die vom Start direkt erreichbar sind, und erst danach die Folgeknoten, Ebene für Ebene.

Tiefensuche: Du besuchst den Startknoten. Dann gehst du zum ersten noch nicht besuchten Nachbarn und machst dort dasselbe, also rekursiv. So folgst du einem Pfad immer weiter in die Tiefe. Hat ein Knoten keinen unbesuchten Nachbarn mehr, gehst du Schritt für Schritt zurück und probierst beim vorigen Knoten den nächsten Nachbarn.

Der Unterschied liegt in der Datenstruktur: Die Breitensuche merkt sich die Knoten in einer Warteschlange, die Tiefensuche in einer anderen Datenstruktur, einem Stapelspeicher.

Die Breitensuche kann man für viele Fragen in Graphen nutzen. Sie findet zum Beispiel zwischen zwei Knoten einen kürzesten Pfad, wenn die Kanten kein Gewicht haben. Jede durch Breitensuche gefundene Lösung hat den kürzesten Abstand zum Startknoten, gemessen in Kanten. Haben die Kanten Gewichte, muss die Lösung, die am nächsten am Start liegt, nicht unbedingt die mit den geringsten Kosten sein. Sind alle Kantengewichte gleich, ist sie dagegen optimal.

Der Algorithmus von Dijkstra löst das Problem der kürzesten Pfade für einen gegebenen Startknoten. In einem kantengewichteten Graphen berechnet er einen kürzesten Pfad vom Start zu einem oder zu allen anderen Knoten, sofern der Graph keine Negativkanten enthält. Negative Kantengewichte können zu nicht optimalen Lösungen führen. Die Grundidee: Er folgt immer der Kante, die den kürzesten Streckenabschnitt vom Start aus verspricht. Ein typisches Beispiel ist der Routenplaner. Der Graph ist dort das Verkehrswegenetz, und gesucht ist die kürzeste Route zwischen zwei Punkten.

Der Algorithmus von Kruskal berechnet minimale Spannbäume von ungerichteten Graphen. Der Graph muss dazu zusammenhängend, kantengewichtet und endlich sein. Kruskal sortiert zuerst die Kanten aufsteigend nach ihrem Gewicht. Dann geht er sie der Reihe nach durch. Eine Kante kommt dazu, wenn sie zwei Knoten verbindet, die noch nicht durch einen Pfad der vorher gewählten Kanten verbunden sind. Ein Netzbetreiber, der Städte verbinden und dabei möglichst wenig Geld für Kabel ausgeben will, nutzt solche Berechnungen.

Der Spannbaum, den Dijkstra am Ende liefert, ist nicht notwendigerweise minimal. Für einen minimalen Spannbaum nimmt man zum Beispiel den Algorithmus von Kruskal.