Graphentheorie

Graphen spielen in der Informatik eine zentrale Rolle. Es gibt zahlreiche Anwendungen, welche die Graphentheorie als grundlegendes Konzept benutzen. Sei es im Social Media Bereich, für Computernetzwerke, endliche Automaten, Routenplanungen oder das Suchen und die Rechtschreibkorrektur in Programmen.

Bei einer Routenplanung zum Beispiel, besteht die Herausforderung darin, einen kürzesten Weg von Punkt A nach Punkt B zu finden. Dieses Anwendungsbeispiel lässt sich sehr gut als Graph interpretieren. Wir werden Algorithmen kennen lernen die uns den kürzesten Weg zwischen zwei Punkten in einem Graphen berechnen.

Gerichtete und ungerichtete Graphen

Ein Graph besteht aus einer endlichen Menge von Kreisen, die durch Verbindungslinien miteinander verbunden sind. Die Kreise werden in der Graphentheorie Knoten genannt und die Verbindungslinien Kanten. Knoten werden also durch Kanten miteinander verbunden.

Zur Darstellung eines gerichteten Graphen, werden Knoten als Kreise und Kanten als Pfeile dargestellt. Ungerichteten Graphen unterscheiden sich von gerichteten, indem Kanten als Linien dargestellt werden. Das bedeutet, dass eine Kante von Knoten a nach b die gleiche Kante ist wie von Knoten b nach a. Kanten in gerichteten Graphen folgen schließlich einer bestimmten Richtung, Kanten ungerichteter Graphen nicht.

Ein Graph wird durch eine Knotenmenge V und eine Kantenmenge E beschrieben.

G = (V, E)

Mit Hilfe dieser beider Darstellungen, können gerichtete und ungerichtete Graphen im Rechner repräsentiert werden. Bei der Adjazenzliste werden zu jedem Knoten seine erreichbaren Nachfolge-Knoten gespeichert.

Die Adjazenzmatrix gibt ebenso Auskunft welche Knoten mit welchen anderen Knoten verbunden sind. Gibt es zum Beispiel eine Kante zwischen Knoten 2 und Knoten 3, wird in der Adjazenzmatrix in der zweiten Zeile an der dritten Spalte eine eins eingetragen. (bzw. in der dritten Zeile an der vierten Spalte, wenn der Graph bei Knoten 0 beginnt). Gibt es keine Kante zwischen zwei Knoten wird ein 0 eingetragen.

Die Breiten- und Tiefensuche sind beides Algorithmen zum Durchsuchen aller, von einem Startknoten s, im Graphen erreichbaren Knoten.

Die Breitensuche (BSF - breadth-first search) besucht zunächst die vom Startknoten direkt erreichbaren Knoten. Erst im Anschluss werden die Knoten der nächst tieferen Ebene besucht. Die Breitensuche kann auch mit Hilfe der Distanz eines Knotens beschrieben werden. Die Distanz eines Knotens ist die Länge des kürzesten Pfades zum Startknoten. Alle Knoten im Graphen werden also in aufsteigender Reihenfolge ihrer Distanz besucht. Also erst alle Knoten mit Distanz 0, dann alle mit Distanz 1 usw.

Die Tiefensuche (DFS - depth-first search) hingegen besucht zuerst einen Pfad bis es keinen direkten Nachfolge-Knoten mehr gibt. Die Tiefensuche versucht also vom Startknoten aus so tief wie möglich in den Graphen vorzudringen. Erst dann wird der nächste komplette Pfad besucht.

Die Reihenfolge, in der die Knoten besucht werden unterscheidet sich folglich je nach Such-Algorithmus.

Es gibt verschiedene Algorithmen zum Finden kürzester Pfade in gewichteten Graphen. Bisher war lediglich die Rede von (ungewichteten) Graphen. In ungewichteten Graphen haben alle Kanten das gleiche Gewicht, bzw. die gleichen Kosten. Somit ist der kürzeste Pfad von einem Knoten zum Startknoten immer der Pfad mit den wenigsten Kanten.

In gewichteten Graphen wird zusätzlich zu jeder Kante ein Kantengewicht zugeordnet. Dieses Gewicht kann einer Distanz, einer Zeitdauer oder Kosten entsprechen.

Unser Ziel ist es nun kürzeste Pfade in einem gewichteten Graphen zu finden. Hierfür benötigen wir in erster Linie die Gewichte der einzelnen Kanten. Die Summe der Kantengewichte geben wir als Gewicht eines Pfades an. Der Pfad mit dem geringsten Gewicht stellt den kürzesten Pfad zwischen einem beliebigen Knoten und dem Startknoten dar. Somit können bei gewichteten Graphen Pfade mit mehr Kanten bzw. mehr Knoten kürzer sein als Pfade mit weniger Kanten. Das Gewicht eines Pfades kann prinzipiell auch negativ sein. Einige Algorithmen erlauben allerdings nur positive Kantengewichte.

Als ersten Algorithmus zum Finden kürzester Pfade betrachten wir den bekannten Algorithmus von Dijkstra, benannt nach seinem Erfinder Edsger W. Dijkstra. Hierbei handelt es sich um einen Algorithmus der Klasse der Greedy Algorithmen. Gierige Algorithmen entscheiden sich in jedem Schritt für den momentan besten Folgezustand, der zum aktuellen Zeitpunkt am erfolgversprechendsten erscheint. Der Algorithmus weist eine gewisse Ähnlichkeit zur Breitensuche auf, da zuerst direkt erreichbare Knoten besucht werden und erst dann die nächst tiefere Ebene besucht wird. In jedem Schritt wird also der nächst beste Knoten in eine Erebnissmenge aufgenommen und aus der Mene der noch zu bearbeitenden Knoten entfernt. Der Dijkstra Algorithmus erlaubt keine negativen Kantengewichte.

Zeitkomplexität: O((|V| + |E|) log |V|)

Platzkomplexität: O(|V|)

Im Gegensatz zum Dijkstra Algorithmus erlaubt der Bellman und Ford Algorithmus auch negative Kantengewichte. Die Erfinder dieses Algorithmus sind Richard Bellmann und Lester Ford. Häufig ist auch die Rede vom Moore-Bellman-Ford-Algorithmus, da Edward Moore ebenfalls zu seiner Entwicklung beigetragen hat. Der Unterschied zwischen diesem Algorithmus und dem Dijkstra Algorithmus ist der, dass die Knoten zu keinem Zeitpunkt abschließend betrachtet werden. Erst wenn der Algorithmus endet, sind die kürzesten Entferunungen zwischen allen Knoten bekannt.

Zeitkomplexität: O(|V||E|)

Platzkomplexität: O(|V|)

Der Floyd und Warshall Algorithmus erlaubt wie der Bellman und Ford Algorithmus negative Kantengewichte und ermittelt den ebenso kürzesten Pfad zwischen allen Knotenpaaren eines gewichteten Graphen. Allerdings werden Zyklen mit negativer Länge nicht erkannt. Der Algorithmus ist nach Robert Floyd und Stephen Warshall benannt, und setzt sich genau genommen aus zwei Algorithmen zusammen.

Zeitkomplexität:  O(|V|³)

Platzkomplexität: O(|V|²)

Ein Graph muss nicht zwangsläufig zusammenhängend sein. Folglich ist die Rede von schwachen Zusammenhangskomponenten. Ist ein Graph zusammenhängend, also jeder Knoten von allen anderen Knoten erreichbar, dann spricht man von starken Zusammenhangskomponenten. Es gibt zwei gängige Algorithmen um Graphen in Zusammenhangskomponenten zu zerlegen – Algorithmus vonKruskal und Algorithmus von Prim.