16Graphen

Graphen als Datenstruktur

Graphen als Datenstruktur sind uns in diesem Buch bereits mehrfach begegnet, etwa bei der Diskussion der verschiedenen Algorithmenmuster. Auch die bereits behandelten Bäume sind ein Spezialfall von Graphen. Tatsächlich handelt es sich bei Graphen um eine der wichtigsten Datenstrukturen in der Programmierung, die in vielen Anwendungsgebieten zum Einsatz kommen.

Ein Graph besteht grob gesprochen aus mit Kanten verbundenen Knoten. Unterschiede gibt es in der Art der Kanten sowie in der Realisierung der Kanten und Knoten in einer Datenstruktur, die sich auf die Effizienz der unterschiedlichen Graphenfunktionen auswirkt.

Wir werden zuerst verschiedene Arten von Graphen betrachten und dann mehrere Implementierungsvarianten für eine Graphendatenstruktur vorstellen und bewerten. Der Hauptteil dieses Kapitels beinhaltet eine Diskussion verschiedener Graphenalgorithmen, um einen Eindruck von der Vielfalt der mit Graphen verbundenen Problemstellungen zu erhalten.

16.1Arten von Graphen

Graphen werden als eine durch Kanten verbundene Menge von Knoten definiert. Wir werden insbesondere die folgenden drei Klassen von Graphen näher betrachten:

Ungerichtete Graphen

1. Bei ungerichteten Graphen wird angegeben, welcher Knoten mit welchem verbunden ist, ohne dass eine Richtung vorgegeben wird. Ist allgemein von Graphen ohne nähere Einschränkung die Rede, sind in der Regel ungerichtete Graphen gemeint. Typische Anwendungen von ungerichteten Graphen sind die Modellierung von Straßenverbindungen (ohne Einbahnstraßen!), der Nachbarschaft von Gegenständen oder eines Telefonnetzes.

Gerichtete Graphen

1. 2.Gerichtete Graphen unterscheiden sich von den ungerichteten dadurch, dass Kanten eine Richtung haben. Auch können zwei Knoten nun durch zwei Kanten (d.h. in jeder Richtung eine) verbunden sein.

Typische Beispiele sind Modelle von Förderanlagen, der Kontrollfluss in Programmen oder auch die bereits vorgestellten Petri-Netze.

DAG: gerichtete azyklische Graphen

1. 3.Ein wichtiger Spezialfall sind gerichtete azyklische Graphen, die oft kurz als DAG für englisch directed acyclic graph bezeichnet werden. In einem DAG gibt es keinen geschlossenen Rundweg entlang der gerichteten Kanten.

Beispiele sind die Vorfahrenbeziehung in Stammbäumen und die Vererbung in Programmiersprachen. Ein DAG ist natürlich als Datenstruktur ein normaler gerichteter Graph; relevant ist hier allerdings der möglichst effiziente Test auf Zyklenfreiheit.

Die Bestandteile von Graphen können mit zusätzlichen Attributen versehen werden, etwa der Länge einer Kante bei der Modellierung eines Straßennetzes. Derartige Graphen werden als gewichtete Graphen bezeichnet.

16.1.1Ungerichtete Graphen

Abbildung 16–1 zeigt ein Beispiel eines ungerichteten Graphen mit sechs Knoten. Die geometrische Lage der einzelnen Punkte und die Wegführung der Kanten ist irrelevant – wichtig ist nur die Information, welcher Knoten mit welchem verbunden ist. Ein Graph beschreibt also nur die topologische Information.

Abb. 16–1 G_u: Beispiel für ungerichteten Graphen

Wir werden den Graphen in Abbildung 16–1 in den folgenden Abschnitten als G_u bezeichnen.

Definition 16.1 Ungerichteter Graph

Die Definition von (ungerichteten) Graphen erfolgt in Form eines Zweitupels G = (V, E). Ein Graph besteht aus

• einer endlichen Menge V von Knoten (V für englisch vertices) und
• einer Menge E von Kanten (E für englisch edges).

Jedes e ∊ E ist dabei eine zweielementige Teilmenge der Knotenmenge V.

Diese Definition lässt also keine Schleifen, d.h. Kanten von einem Knoten zu sich selbst, und auch keine mehrfachen Kanten zwischen zwei Knoten (Parallelkanten) zu. Möglich ist auch eine erweiterte Definition, in der jedes e ∊ E eine ein- oder zweielementige Teilmenge darstellt.

Als Beispiel für diese Formalisierung von Graphen betrachten wir den Graph G_u aus Abbildung 16–1:

• G_u = (V_u, E_u)
• V_u = {1, 2, 3, 4, 5, 6}
• E_u = {{ 1, 2}, {1, 3}, {1, 4}, {2, 6}, {4, 6}, {3, 6}, {5, 6}, {3, 4}, {3, 5}}

16.1.2Gerichtete Graphen

Die Abbildung 16–2 zeigt nun ein Beispiel eines gerichteten Graphen, ebenfalls mit sechs Knoten. Die geometrische Lage der einzelnen Punkte und die Wegführung der Kanten ist auch hier irrelevant.

Abb. 16–2 G_g: Beispiel für gerichteten Graphen

Man beachte die Schleife am Knoten 5 und die Existenz zweier Kanten zwischen den Knoten 1 und 3. Wir werden den Graphen in Abbildung 16–2 in den folgenden Abschnitten als G_g bezeichnen.

Definition 16.2 Gerichteter Graph

Die Definition von gerichteten Graphen erfolgt analog zu den allgemeinen Graphen durch ein Zweitupel G = (V, E) mit

• V, einer endlichen Menge von Knoten, und
• E, einer Menge von Kanten.

Allerdings ist jedes e ∊ E nun ein Tupel (a, b) mit a, b ∊ V. Diese Definition lässt Schleifen (a, a) zu.

Als Beispiel für diese Definition gerichteter Graphen betrachten wir den Graph G_g aus Abbildung 16–2:

• G_g = (V_g, E_g)
• V_g = {1, 2, 3, 4, 5, 6}
• E_g = {(1, 2), (1, 3), (3, 1), (4, 1), (3, 4), (3, 6), (5, 3), (5, 5), (6, 5), (6, 2), (6, 4)}

16.1.3Gewichtete Graphen

Gewichtete Graphen

Gewichtete Graphen besitzen zusätzlich zu den bisherigen Graphenbestandteilen noch Kantengewichte. Kantengewichte sind den Kanten zugeordnete Gewichtswerte, etwa natürliche Zahlen oder int- oder real-Werte. Ein gewichteter Graph kann nun für natürliche Zahlen als Kantengewichte durch G = (V, E, γ) mit

γ: E →

definiert werden. Gewichtete Graphen werfen einige neue Fragestellungen auf, so etwa die Suche nach kürzesten Wegen, dem maximalem Fluss durch einen Graphen oder die Konstruktion minimaler aufspannender Bäume.

Abbildung 16–3 zeigt einen gewichteten, gerichteten Graphen. Natürlich gibt es auch gewichtete, ungerichtete Graphen, etwa um Entfernungen in Verkehrsnetzen zu modellieren.

Abb. 16–3 Beispiel für gewichteten Graphen

Abbildung 16–3 verdeutlicht die Fragestellung der kürzesten Wege: Werden die Gewichte als Kosten oder Entfernungen interpretiert, ist es billiger von 3 über 4 nach 1 zu gehen, als die direkte Kante (3, 1) zu benutzen.

16.1.4Weitere Eigenschaften von Graphen

Knotengrad

Ein weiteres wichtiges Merkmal von Graphen ist der Knotengrad, der für einen gegebenen Knoten i die Anzahl der verbundenen Knoten bezeichnet. So ist der Grad des Knotens 6 in Abbildung 16–3 entsprechend 4. Bei gerichteten Graphen kann noch zwischen Ausgangsgrad (die Anzahl der ausgehenden Kanten) und Eingangsgrad (die Anzahl der eingehenden Kanten) unterschieden werden. Für unseren Knoten 6 ist der Ausgangsgrad damit 3 und der Eingangsgrad 1.

Knotengrade spielen beispielsweise eine wichtige Rolle bei Zentralitätsanalysen und Verteilungen von Knotengraden etwa bei der Bestimmung von Eigenschaften von Graphen.

16.2Realisierung von Graphen

Eine Datenstruktur für Graphen kann unterschiedlich aufgebaut werden. Die Realisierungen unterscheiden sich dabei im Platzbedarf gespeicherter Graphen sowie in der Komplexität der erwähnten Basisoperationen.

Im Folgenden liegt der Fokus auf gerichteten Graphen, wobei die Realisierung ungerichteter Graphen oft analog durchgeführt werden kann. Wir werden verschiedene Realisierungsvarianten betrachten und mit einem Vergleich der Komplexität der Operationen in den verschiedenen Varianten enden.

16.2.1Knoten- und Kantenlisten

Kodierung als Zahlenfolge

Eine sehr einfache (und historisch daher als erste verwendete) Speicherung von Graphen erfolgt als eine Liste von Zahlen, etwa in einem Array, einer sequenziellen Datei oder als verkettete Liste.

Diese Liste von Zahlen dient als Kodierung des Graphen, wobei die Knoten von 1 bis n = |V| durchnummeriert werden. Kanten können dann beispielsweise als Paare von Knotenzahlen dargestellt werden. Wir werden zwei Varianten genauer erläutern, die Realisierung durch Kantenlisten und die durch Knotenlisten.

Realisierung durch Kantenlisten

Die Realisierung durch Kantenlisten baut eine Zahlenfolge wie folgt auf: Das erste Element definiert die Knotenanzahl, das zweite die Kantenanzahl und der Rest der Zahlenfolge definiert die Liste der Kanten, die jeweils als zwei Zahlen notiert werden.

Das Beispiel G_g aus Abbildung 16–2 lautet dann wie folgt:

6, 11, 1, 2, 1, 3, 3, 1, 4, 1, 3, 4, 3, 6, 5, 3, 5, 5, 6, 5, 6, 2, 6, 4

Realisierung durch Knotenlisten

Die Variante der Knotenlisten hingegen baut die Liste wie folgt auf: Die ersten beiden Zahlen legen wieder Knotenanzahl und Kantenanzahl fest, gefolgt von einer Liste von Knoteninformationen. Die Knoteninformation besteht dabei jeweils aus dem Ausgangsgrad ag (i) des Knotens i und den Zielknoten der von diesem Knoten ausgehenden Kanten, also ag(i), v_i1, …, v_iag(i).

Das bereits mehrfach genutzte Beispiel des Graphen G_g aus Abbildung 16–2 lautet in dieser Darstellung wie folgt:

6, 11, 2, 2, 3, 0, 3, 1, 4, 6, 1, 1, 2, 3, 5, 3, 2, 4, 5

Die Teilfolge 2, 2, 3 beginnend an der dritten Position in dieser Zahlenfolge bedeutet beispielsweise »Knoten 1 hat Ausgangsgrad 2 und herausgehende Kanten zu den Knoten 2 und 3«.

Man sieht bereits an diesem Beispiel, dass für Graphen mit vielen Kanten Knotenlisten weniger Speicherbedarf als Kantenlisten benötigen. Genauer benötigen Kantenlisten 2 + 2 · |E| Zahlen und Knotenlisten 2 + |V| + |E| Zahlen.

16.2.2Adjazenzmatrix

Realisierung durch Adjazenzmatrix

Insbesondere bei sehr vielen Kanten ist eine Speicherung der Verbindungen als n × n-Matrix sinnvoll. Der Wert n entspricht dabei der Knotenanzahl |V|. Eine derartige Matrix wird als Adjazenzmatrix bezeichnet.

Adjazenzmatrix für gerichteten Graphen

Die folgende Adjazenzmatrix stellt den gerichteten Graphen G_g aus Abbildung 16–2 dar:

Adjazenzmatrix für ungerichteten Graphen

Die Idee der Adjazenzmatrix lässt sich direkt auf ungerichtete Graphen übertragen, wobei dann eigentlich nur die eine Hälfte der Matrix gespeichert werden muss, da sich die andere Hälfte durch Spiegelung ergibt. Die folgende Adjazenzmatrix stellt den ungerichteten Graphen G_u aus Abbildung 16–1 dar:

Beim Vergleich des Speicherbedarfs muss man nun beachten, dass die Matrixelemente boolesche Werte sind, die im Gegensatz zu Zahlwerten nur ein Bit benötigen.

16.2.3Graphen als dynamische Datenstrukturen

Graphen als dynamische Datenstrukturen

Die bisherigen Graphendarstellungen waren statische Realisierungen, da eigentlich keine dynamischen Erweiterungen im Sinne verketteter Listen vorgesehen waren (obwohl etwa Knotenlisten natürlich auch als verkettete Liste realisiert werden können). Es gibt nun eine Reihe von Möglichkeiten, Graphen als dynamische Datenstrukturen zu realisieren. Eine nahe liegende Variante ist es, wie bei einem Baum die Knoten als Elemente einer dynamischen Struktur aufzufassen und die Kanten als Verzeigerung zu realisieren. Dies bildet direkt die Graphenstruktur ab und resultiert in einer komplex verzeigerten Struktur mit vielen Zyklen (und damit Fehlermöglichkeiten bei der Programmierung).

Realisierung mit Adjazenzliste

Wir werden uns eine andere Realisierung anschauen, die auch als Adjazenzliste bezeichnet wird. Ein Graph wird dabei durch |V| +1 verkettete Listen realisiert. Die Basisstruktur bildet die Liste aller Knoten. Für jeden Knoten wird eine Liste der Nachfolger entlang gerichteter Kanten abgespeichert, so dass man für n = |V| und m = |E| insgesamt Listenelemente erhält.

Abbildung 16–4 zeigt die Speicherung unseres Standardbeispiels (Graph G_g aus Abbildung 16–2) als Adjazenzliste. Statt der Knotennummern können in den Knoten der ausgehenden Kanten natürlich auch Verweise auf die Knotenelemente gespeichert werden, um das Navigieren zu erleichtern.

16.2.4Transformationen zwischen Darstellungen

Transformationen zwischen Darstellungen

Alle vorgestellten Realisierungsvarianten sind äquivalent; jede Darstellung kann also in jede andere ohne Informationsverlust transformiert werden. Im Wesentlichen erfordert dies das Auslesen der einen Darstellung und anschließend das Erzeugen der jeweils anderen Darstellung.

Abb. 16–4 Graph als dynamische Datenstruktur

Der Aufwand dieser Transformationen variiert von O(n + m) bis O(n²), wobei im schlechtesten Fall m = n² gilt. Der Fall n² tritt immer auf, wenn eine Matrixdarstellung beteiligt ist (da n² Elemente berücksichtigt werden müssen).

16.2.5Vergleich der Komplexität

Tabelle 16–1 gibt einen Überblick über den Aufwand bei der Realisierung der einzelnen Varianten. Hierbei gilt n = |V| und m = |E|.

Tab. 16–1 Vergleich der Komplexität für Graphrepräsentationen

Das Löschen eines Knotens löscht auch zugehörige Kanten, so dass hier der Aufwand in allen Varianten unvermutet hoch ist. Zu den einzelnen Varianten sind einige Bemerkungen angebracht:

• Bei Kantenlisten ist sowohl das Einfügen von Kanten (Anhängen zweier Zahlen) und von Knoten (Erhöhung der ersten Zahl um 1) besonders günstig, falls das Anhängen von Zahlen nicht zum Umkopieren eines Feldes führt. Das Löschen von Kanten kann das Zusammenschieben in einer Liste bedeuten; das Löschen von Knoten eine erneute Durchnummerierung der Knoten.
• Bei Knotenlisten ist insbesondere das Einfügen von Knoten (Erhöhung der ersten Zahl und Anhängen einer 0) günstig.
• In der Matrixdarstellung ist insbesondere das Manipulieren von Kanten eine sehr effizient ausführbare Operation. Der Aufwand bei Knoteneinfügung hängt von der Realisierung der Matrix ab, hier wurde von einem Kopieren der Matrix in eine größere Matrix ausgegangen.
• Bei der Realisierung als Adjazenzliste ergibt sich unterschiedlicher Aufwand, je nachdem ob die Knotenliste als Feld (mit Direktzugriff) oder als verkettete Liste (mit sequenziellem Durchlauf) realisiert wird.

16.2.6Eine Java-Klasse für Graphen

Zur Implementierung einer Klasse Graph lassen sich grundsätzlich alle der oben vorgestellten Repräsentationen verwenden. Im Interesse einer einfachen Handhabung beim Hinzufügen bzw. Löschen von Knoten und Kanten bietet sich jedoch eine dynamische Datenstruktur wie die Adjazenzliste an. Die Klasse Graph aus Programm 16.1 besteht daher im Kern aus einer Hashtabelle nodeSet in Form der Klasse java.util.HashMap, wobei jedes Element wiederum ein Paar aus einem String (dem Knotenbezeichner) und einem Node-Objekt darstellt. Knoten werden im Graphen somit über einen eindeutigen Bezeichner identifiziert, über den sie aus nodeSet ausgelesen werden können. Jeder Knoten als Instanz der Klasse Node enthält neben dem Bezeichner eine Adjazenzliste adjList. Da für gewichtete Graphen nicht nur der Zielknoten, sondern auch noch das Kantengewicht gespeichert werden muss, wird eine Kante durch ein Objekt der Klasse Edge repräsentiert. Diese Klasse umfasst im Wesentlichen nur zwei Attribute dest mit einer Referenz auf den Zielknoten und cost mit dem Gewicht.

Programm 16.1 Repräsentation eines Graphen

Zur Konstruktion eines neuen (leeren) Graphen wird der Konstruktor der Klasse Graph verwendet, der eine leere Hashtabelle erzeugt. Der Graph kann nun schrittweise durch Hinzufügen von Knoten und Kanten aufgebaut werden. In der Methode addNode wird zunächst geprüft, ob bereits ein Knoten mit dem angegebenen Namen existiert. Danach wird der Knoten erzeugt und in die Hashtabelle eingetragen.

Eine Kante wird eingefügt, indem die Methode addEdge mit den Namen des Ausgangs- und des Zielknotens sowie dem Kantengewicht aufgerufen wird. Aus den Knotennamen müssen dabei zuerst über die Hashtabelle die eigentlichen Knoten ermittelt werden, wozu die Hilfsmethode getNode genutzt wird. Anschließend kann ein neues Kantenobjekt erzeugt und in die Adjazenzliste des Ausgangsknotens eingetragen werden.

In der Klasse Node in Programm 16.1 sind noch zwei weitere Methoden zum Zugriff auf die ausgehenden Kanten eines Knotens angegeben. Die Implementierung des Löschens von Knoten und Kanten sei dem Leser als Übung überlassen.

16.3Ausgewählte Graphenalgorithmen

Graphen sind eine vielfältig eingesetzte Datenstruktur und dementsprechend vielfältig sind die für Graphen entwickelten Algorithmen. Wir werden mit dem Breitendurchlauf und dem Tiefendurchlauf zwei für Graphenbearbeitung typische Vorgehensweisen kennen lernen, die es erlauben, jeden Knoten eines Graphen in systematischer Weise zu besuchen bzw. jede Kante zu durchlaufen. Als Anwendung dieser Verfahren werden wir den Test auf Zyklenfreiheit und das topologische Sortieren genauer betrachten.

16.3.1Breitendurchlauf

Breitendurchlauf

Der Breitendurchlauf ist ein Algorithmenmuster, das die Knoten eines Graphen nach der Entfernung von einem Startknoten geordnet durchläuft: Zuerst werden alle von diesem Startknoten direkt durch eine Kante erreichbaren Knoten bearbeitet, danach die nur durch mindestens zwei Kanten, dann die durch drei etc. Das Verfahren ist englisch als breadth-first-search bekannt, abgekürzt als BFS.

Der folgende Algorithmus BFS realisiert einen iterativen Breitendurchlauf durch einen ungerichteten Graphen. Als Hilfsstruktur wird eine Warteschlange Q benutzt. Zur Verdeutlichung wird der Bearbeitungsstatus eines Knotens als Farbwert angegeben: Weiße Knoten sind unbearbeitet, für graue Knoten ist bereits die Entfernung bestimmt, aber diese wurden nicht auf weiterführende Pfade untersucht, und schwarze Knoten sind abgearbeitet. Pro Knoten wird die Distanz d zum Startknoten abgespeichert sowie der Knoten, von dem aus dieser Knoten erreicht wurde. Diese Vorgängerkanten π (für predecessor) ergeben nach Abarbeitung des Graphen einen aufspannenden Baum.

Algorithmus 16.1 Breitendurchlauf

Die Arbeitsweise des BFS-Algorithmus soll nun anhand eines Beispiels verdeutlicht werden. Abbildung 16–5 zeigt einen Graphen mit acht Knoten nach der Initialisierungsphase des Algorithmus.

Abb. 16–5 Breitendurchlauf am Beispiel nach initialem Schritt

Die Initialisierungsphase markiert den Startknoten, hier den Knoten s, als grau und alle anderen Knoten als unbearbeitet, also weiß. Die Entfernung des Startknotens wird auf 0 gesetzt, die aller anderen Knoten auf unendlich (∞). Die Warteschlange Q wird mit dem Startknoten initialisiert.

Abbildung 16–6 zeigt nun die folgenden Abarbeitungsschritte (nach jedem Durchlauf der äußeren Schleife). Die Schritte sind zeilenweise von oben links nach unten rechts angeordnet.

Abb. 16–6 Breitendurchlauf in den folgenden Schritten

Der erste Durchlauf (links oben) bearbeitet den (nun zu schwärzenden) Knoten s. Die direkt erreichbaren Knoten r und w werden mit der Distanz 1 versehen, grau markiert und (in beliebiger Reihenfolge) in die Warteschlange aufgenommen (aus der zuvor s entfernt wurde).

Der zweite Durchlauf entnimmt w als vordersten Knoten aus der Warteschlange. Die von ihm erreichbaren Knoten t und x werden mit der Distanz 2 versehen und wie beschrieben bearbeitet. Man beachte, dass auch s von w aus erreichbar ist – s wurde aber bereits als bearbeitet gekennzeichnet und wird deshalb ignoriert. Ähnliches geschieht im vierten Durchlauf mit dem Knoten x, der grau markiert ist und sich daher schon in der Bearbeitung befindet.

Die weiteren Durchläufe folgen dem gleichen Muster, so dass wir auf eine detaillierte Beschreibung verzichten können. Abbildung 16–7 zeigt abschließend den durch das Setzen der Zeiger π während des Breitendurchlaufs erzeugten aufspannenden Baum.

Abb. 16–7 Durch Breitendurchlauf erzeugter aufspannender Baum

Der konkret berechnete aufspannende Baum hängt übrigens von der Reihenfolge ab, in der die ausgehenden Kanten eines Knotens bearbeitet werden (und damit Knoten in die Warteschlange aufgenommen werden). Wird dies nicht durch die Datenstruktur oder die Verfeinerung dieser Auswahl vorgegeben, ist BFS nichtdeterministisch.

Abschließend sei erwähnt, dass die vorgestellte Realisierung dem Buch T. Cormann, C. Leiserson, R. Rivest: Introduction to Algorithms [CLR09] entnommen wurde. Die dortige Präsentation (und die einiger folgender Algorithmen) mit Farbwerten hat uns derart überzeugt, dass wir sie übernommen haben, obwohl die drei Farbwerte im BFS genau genommen redundant sind und aus den aktuellen Distanzwerten und einer Knotenordnung abgeleitet werden können.

Die Implementierung des Breitendurchlaufs auf Basis der Graph-Klasse aus Abschnitt 16.2.6 ist in Programm 16.2 dargestellt. Hierfür ist die Klasse um die Konstanten für die Farbwerte (WHITE, GRAY, BLACK) sowie die Klasse BFSItem zur Repräsentation der Knoteninformationen color, d und π (pred) zu erweitern. In der Methode breadthFirstSearch, die mit der Nummer des Startknotens als Parameter aufzurufen ist, wird zu jedem Knoten des Graphen ein Objekt der Klasse BFSItem benötigt. Daher wird zu Beginn ein Feld table entsprechend der Anzahl der Knoten angelegt, das als i-tes Element ein Objekt mit den Informationen zum Knoten i besitzt. Der Zugriff auf die einzelnen Informationen kann damit direkt über den Index des Knotens erfolgen.

Programm 16.2 Implementierung des Breitendurchlaufs

Die für den Algorithmus benötigte Warteschlange ist unter Nutzung der Klasse ArrayQueue realisiert. Da diese Klasse jedoch nur Objekte und keine einfachen Werte aufnehmen kann, muss der Umweg über die Klasse java.lang.Integer erfolgen. Die weitere Implementierung entspricht Algorithmus 16.1, wobei das Durchlaufen aller Zielknoten über einen Iterator erfolgt. Am Ende der Bearbeitung werden die fertigen (schwarz markierten) Knoten mit ihrer Distanz vom Startknoten ausgegeben. Zu beachten ist außerdem, dass der Algorithmus auf einem ungerichteten Graphen arbeitet. Dies bedeutet, dass für die Implementierung in Programm 16.2 entweder die Methode getEdges der Klasse Graph (Programm 16.1) so angepasst wird, dass nicht nur die ausgehenden, sondern auch die eingehenden Kanten zurückgegeben werden oder dass beim Aufbau des Graphen jede ungerichtete Kante durch zwei entgegengesetzt gerichtete Kanten repräsentiert wird.

16.3.2Tiefendurchlauf

Tiefendurchlauf

Während der Breitendurchlauf in die Breite geht und sich sozusagen Schicht für Schicht weiter vom Startknoten entfernt, geht der Tiefendurchlauf so weit wie möglich einen gewählten Pfad entlang. Der Algorithmus DFS für depth-first search realisiert einen rekursiven Durchlauf durch einen gerichteten Graphen. Auch hier werden wieder Farbmarkierungen für den Bearbeitungsstatus eines Knotens genutzt: Weiß markiert sind noch nicht bearbeitete Knoten, graue Knoten sind in Bearbeitung, schwarze bereits fertig abgearbeitet.

In Pseudocode-Notation kann der Tiefendurchlauf wie in Algorithmus 16.2 skizziert werden.

Algorithmus 16.2 Tiefendurchlauf

Für jeden Knoten des Graphen werden wieder einige Hilfsinformationen abgespeichert. Wie bereits erwähnt, gibt der Farbwert den Bearbeitungsstatus an. Das Attribut d speichert den Beginn der Bearbeitung des Knotens ab, f analog das Ende der Bearbeitung des Knotens. Hierzu wird eine Variable zeit bei jedem Bearbeitungsschritt um 1 erhöht.

Als Erweiterung des Tiefendurchlaufs kann sozusagen »on the fly« eine Klassifikation der bearbeiteten Kanten (u, v) erfolgen:

• Kanten des aufspannenden Baumes werden genau dann gefunden, wenn der Zielknoten weiß ist.
• Mit B werden Kanten gekennzeichnet, deren Zielknoten beim Test grau ist. Es handelt sich um sogenannte Back-Edges oder Rückkanten im aufgespannten Baum. Eine mit B markierte Kante zeigt einen Zyklus an!
• Mit F wird markiert, falls beim Test ein schwarzer Knoten gefunden wird, dessen Bearbeitungsintervall ins Intervall des aktuell bearbeiten Knotens passt. Es handelt sich hierbei um einen Forward-Edge bzw. Vorwärtskante in den aufgespannten Baum.
• Der letzte Fall ist ein schwarzer Zielknoten v, dessen Intervall nicht ins Intervall passt (d[u] > d[v]). Derartige Kanten klassifiziert man als C für Cross-Edge, eine Kante, die zwei aufspannende Bäume verbindet.

Der Ablauf des Tiefendurchlaufs beim DFS wird nun anhand des in Abbildung 16–8 gezeigten Graphen vorgeführt.

Abb. 16–8 Beispielgraph für Tiefendurchlauf

Der Beispielgraph in Abbildung 16–8 ist derart gewählt, dass alle Kantenarten beim Ablauf tatsächlich einmal auftreten. Er ist bereits initialisiert – alle Knoten sind weiß markiert.

In den Abbildungen 16–9 und 16–10 wird nun die Abarbeitung des Graphen in insgesamt 16 Schritten gezeigt. Wieder ist die Reihenfolge von links nach rechts und zeilenweise von oben nach unten.

Abb. 16–9 Die ersten acht Zwischenzustände beim Tiefendurchlauf

Der erste Graph in Abbildung 16–9 zeigt als ersten Schritt, dass zufällig durch die Angabe for each ein noch weißer Knoten ausgewählt wird, in unserem Falle der Knoten u. Für diesen Knoten wird nun die rekursive Prozedur DFS-visit aufgerufen. Die Farbe des Knotens wird beim Aufruf auf grau gesetzt, die untere Intervallgrenze d erhält den ersten Zeitpunkt 1. Bevor nun die Abarbeitung des Knotens damit beendet werden kann, dass der Farbwert auf schwarz gesetzt wird und die obere Grenze f[u] gesetzt werden kann, wird die rekursive Prozedur DFS-visit für alle von u erreichbaren weißen Knoten aufgerufen (damit wird wieder – analog zur BFS – mittels der π-Zeiger der aufspannende Baum konstruiert).

Der zweite Graph in Abbildung 16–9 zeigt nun den Beginn der Bearbeitung des ersten rekursiven Aufrufs, hier für den Knoten v. Der aufspannende Baum wird durch dickere Kanten grafisch dargestellt. Der nächste Schritt ruft von v aus den Knoten y auf. Im fünften Graphen wird mit der Kante (x, v) erstmals eine Back-Edge entdeckt. Der Knoten x ist der Knoten, der fertig abgearbeitet werden kann und schwarz gefärbt wird. Von dort aus geht die Abarbeitung der Rekursionskette über y und v zurück zum Startknoten v, der im 10. Schritt (nach Entdeckung einer Forward-Edge, Abbildung 16–10) abgearbeitet wird.

Abb. 16–10 Die Zwischenzustände 9 bis 16 beim Tiefendurchlauf

Nach Abarbeitung des zehnten Schrittes zeigt sich der Sinn der äußeren Schleife über alle (weißen) Knoten: Durch die Wahl von w als noch weißen Knoten wird die Wurzel eines weiteren aufspannenden Baumes für den verbleibenden Restgraphen bestimmt. Hier wird auch sofort eine Cross-Edge gefunden, die in den ersten aufspannenden Baum führt (Kante (w, y)). Am letzten Knoten z wird schließlich noch gezeigt, dass auch Kanten der Form (z, z) korrekt behandelt werden.

Wir werden auf eine genauere Analyse des Tiefendurchlaufs verzichten. Die Prozedur DFS-visit wird nur für weiße Knoten aufgerufen; die äußere Schleife garantiert, dass dies für jeden weißen Knoten geschieht. Da ein Aufruf als Erstes den Knoten grau einfärbt, wird DFS-visit für jeden Knoten genau einmal aufgerufen. Innerhalb des Aufrufs wird eine Schleife über alle von diesem Knoten ausgehenden Kanten durchlaufen – der Aufwand ist somit insgesamt linear: O(|V| + |E|).

16.3.3Zyklenfreiheit und topologisches Sortieren

Der Tiefendurchlauf kann für viele Probleme genutzt werden, die es erfordern, jeden Knoten und jede Kante genau einmal zu inspizieren. Zwei interessante Problemstellungen können ohne größere Modifikationen beim Tiefendurchlauf mit bearbeitet werden: der Test auf Zyklenfreiheit und das topologische Sortieren.

Test auf Zyklenfreiheit

Test auf Zyklenfreiheit mit DFS

In vielen Anwendungen wird ein Test auf Zyklenfreiheit für gerichtete Graphen benötigt, etwa bei der Bearbeitung von logistischen Transportstrecken oder der Analyse von Vererbungshierarchien.

Der Tiefendurchlauf mit DFS bearbeitet dieses Problem mit, indem Back-Edges erkannt werden. Ein gerichteter Graph G ist zyklenfrei genau dann, wenn keine Kante als B markiert wurde.

Gegenüber intuitiv näher liegenden Verfahren zum Test auf Zyklenfreiheit – etwa der Konstruktion der transitiven Hülle des Graphen – zeichnet sich dieses Verfahren insbesondere durch die bereits erwähnte sehr gute Laufzeitkomplexität aus.

Topologisches Sortieren

Topologisches Sortieren

Das topologische Sortieren ist ebenfalls eine Problemstellung, die in vielen graphbasierten Anwendungen ihren praktischen Einsatz findet. Formal lässt sich das Problem wie folgt charakterisieren: Gegeben ist ein azyklischer gerichteter Graph. Gesucht wird eine Reihenfolge der Knoten, so dass jeder Knoten nach all seinen Vorgängern kommt, es also keine »Rückkanten« gibt.

Werden die gerichteten Kanten als kausale oder zeitliche Abhängigkeiten aufgefasst, so spricht man auch vom Scheduling-Problem.

Aus dem DFS-Algorithmus kann man nun leicht wie folgt ein Topological-Sort-Verfahren ableiten. Man lasse DFS(G) laufen, um den Wert f[v] für jeden Knoten v zu bestimmen. Die Werte von f[v] geben nun direkt eine topologische Sortierung vor.

Konkret wird bei jeder Abarbeitung eines Knotens, also dem Setzen des Wertes f[v], der Knoten vorne in eine verkettete Liste eingehängt. Diese Liste gibt nun die gesuchte Ordnung an.

Beispiel für topologisches Sortieren

Als Beispiel für topologisches Sortieren betrachten wir ein in Lehrbüchern häufig verwendetes einfaches Beispiel anstelle eines echten Scheduling-Problems.

Ein zerstreuter Professor hat Probleme, morgens seine Kleidungsstücke in der richtigen Reihenfolge anzuziehen. Daher legt er die Reihenfolgebedingungen beim Ankleiden fest:

Der zerstreute Professor nutzt nun topologisches Sortieren, um eine korrekte Reihenfolge zu bestimmen. Abbildung 16–11 zeigt die Vorgaben notiert als gerichteter Graph.

Abb. 16–11 Eingabe für topologisches Sortieren

Abbildung 16–12 zeigt das Ergebnis eines Laufes mit dem DFS-Algorithmus. Als erster Knoten wurde zufällig das Hemd ausgewählt. Die f-Werte (Zeitpunkt des Verlassens eines Knotens nach rekursiver Abarbeitung) geben uns nun eine gewünschte Ordnung vor.

Die folgende Liste zeigt den jeweiligen f-Wert und das zugehörige Kleidungsstück. Man kann sich leicht vergewissern, dass alle vorgegebenen Bedingungen eingehalten werden.

Abb. 16–12 Topologisches Sortieren durch Tiefensuche mit DFS

Es gibt viele mögliche Ordnungen, die die gegebenen Bedingungen einhalten. So zeigt Abbildung 16–13 einen Fall, bei dem mit dem Gürtel begonnen wurde.

Abb. 16–13 Topologisches Sortieren durch Tiefensuche II

Topologisches Sortieren mit DFS berechnet nichtdeterministisch eine dieser Ordnungen in Abhängigkeit der nichtdeterministischen Wahl weißer Knoten in der äußeren Schleife.

16.4Algorithmen auf gewichteten Graphen

Eine wichtige Erweiterung des einfachen Graphenmodells sind gewichtete Graphen, bei denen den Kanten ein Kantengewicht zugeordnet ist. Es gibt Anwendungen sowohl für gerichtete als auch für ungerichtete gewichtete Graphen. Ungerichtete gewichtete Graphen können zum Beispiel Flugverbindungen mit Meilenangaben oder Straßennetze mit Kilometerangaben modellieren. Das Beispiel der Straßennetze benötigt gerichtete gewichtete Graphen, falls Einbahnstraßen modelliert werden sollen.

Abbildung 16–14 zeigt einen einfachen gewichteten Beispielgraphen. Die Kante (s, u) hat beispielsweise das Gewicht 10. Werden die Gewichte als zu addierende Kosten aufgefasst, ist es also günstiger, indirekt über x von s nach u (mit Gesamtkosten von 8) zu gehen, als die direkte Kante zu nutzen. Die fehlenden Kanten können für viele Zwecke auch als Kanten mit unendlich großem Gewicht aufgefasst werden.

Abb. 16–14 Gewichteter Graph

16.4.1Kürzeste Wege

Eine der wichtigsten Problemstellungen für gewichtete Graphen ist das Finden kürzester Wege, also von Pfaden durch den Graphen, für die es keine »günstigere« Alternativstrecke mit geringeren Kosten gibt. Wir formulieren das Problem zuerst exakter, bevor wir uns passenden Algorithmen zuwenden.

Gewichteter Graph

Ein gerichteter Graph wird als G = (V, E, γ) mit einer Gewichtsfunktion γ: E → notiert, wenn wir als Kantengewichte natürliche Zahlen zulassen wollen. Ein Weg oder auch Pfad durch G ist gegeben durch eine Liste von aneinanderstoßenden Kanten:

P = (v₁, v₂), (v₂, v₃), (v₃, v₄), …, (v_n−1, v_n)

P steht hier für das englische path. Das Gewicht oder auch die Länge eines Pfades wird durch Aufsummierung der einzelnen Kantengewichte bestimmt:

Distanz als Länge kürzester Wege

Die Distanz zweier Punkte d(u, v) ist nun das Gewicht des kürzesten Pfades von u nach v. Derartige Problemstellungen bestehen in vielen Anwendungen: Prominente Beispiele sind die Routenplanung in Navigationssystemen oder die Wegsuche in Computerspielen.

Zu kürzesten Wegen sind zwei Bemerkungen angebracht. Kürzeste Wege sind nicht eindeutig: Es kann mehrere Pfade zwischen zwei Punkten mit gleicher Länge geben. Kürzeste Wege müssen nicht existieren. So kann es vorkommen, dass überhaupt kein Weg existiert. Im Fall von nicht ausschließlich positiven Kantengewichten könnte des Weiteren ein Zyklus mit negativem Gewicht existieren, der beliebig oft durchlaufen wird und bei jedem Durchlauf das Gewicht des Pfades verringert.

Wir werden drei Algorithmen für die Bestimmung kürzester Wege betrachten. Dijkstras Algorithmus ist ein Greedy-Verfahren, das für nichtnegative Gewichte eine optimale Lösung findet. Als zweite Variante behandeln wir den A*-Algorithmus, der ähnlich dem Dijkstra-Verfahren ist, dabei aber zur Klasse der informierten Suchverfahren zählt. Anschließend werden wir einen weiteren Algorithmus betrachten, der auch negative Kantengewichte behandeln kann.

16.4.2Dijkstras Algorithmus

Dijkstras Algorithmus zum Finden kürzester Wege ist ein bekannter Graphenalgorithmus, der von Dijkstra 1959 veröffentlicht und nach ihm benannt wurde. Er basiert auf einer iterativen Erweiterung einer Menge von »billig« erreichbaren Knoten und kann daher als eine auf dem Greedy-Prinzip basierende Weiterentwicklung der Breitensuche für gewichtete Kanten aufgefasst werden. Allerdings funktioniert diese Weiterentwicklung nur für nichtnegative Gewichte.

Das Verfahren von Dijkstra ist in Algorithmus 16.3 in Pseudocode-Notation angegeben.

Algorithmus 16.3 Dijkstras Algorithmus

Pro Knoten wird ein Wert D abgespeichert, der für den Startknoten den Wert 0 erhält und nach Ablauf des Verfahrens den korrekten Distanzwert zum Startknoten abspeichern soll. Während der Berechnungen enthält diese Variable Zwischenwerte, so ist am Anfang die Distanz unendlich.

Die verwendete Prioritätswarteschlange ermöglicht das Herauslesen des jeweils minimalen Elementes, sie entspricht somit einer sortierten Liste, aus der jeweils das erste Element entfernt wird, und könnte beispielsweise unter Verwendung eines Heaps implementiert werden (siehe Abschnitt 14.6.1). Der Algorithmus berechnet die Distanz aller Knoten zum Startknoten. Das eingesetzte Verfahren entspricht einer Breitensuche mit gewichteter Entfernung. Wir werden die Arbeitsweise wieder an einem einfachen Beispiel erläutern.

Abbildung 16–15 zeigt das Ergebnis der Initialisierungsphase für den Graphen aus Abbildung 16–14.

Abb. 16–15 Dijkstras Algorithmus: Initialisierung

Die Prioritätswarteschlange hat nach der Initialisierung die folgende Form:

Q = (s : 0), (u : ∞), (v : ∞), (x : ∞), (y : ∞)

Nach dem ersten Schleifendurchlauf berechnet Dijkstras Algorithmus den in Abbildung 16–16 gezeigten Zustand. Alle von s aus direkt erreichbaren Knoten werden mit dem durch die direkte Kante bestimmten Gewicht versehen. s selbst wurde aus Q entfernt.

Abb. 16–16 Dijkstras Algorithmus nach erstem Durchlauf

Nach dem ersten Schleifendurchlauf sieht Q wie folgt aus:

Q = (x : 5), (u : 10), (v : ∞), (y : ∞)

Der zweite Durchlauf der Schleife bearbeitet nun den Knoten mit dem minimalen Distanzwert aus der Prioritätswarteschlange, in diesem Fall den Knoten x mit Wert 5. Dieser Wert ist tatsächlich der endgültige Distanzwert von x – jeder andere Pfad zu x müsste über (s, u) gehen und (da wir nur nichtnegative Kantengewichte haben) mindestens zu einer Distanz von 10 führen. Abbildung 16–17 zeigt das Ergebnis des zweiten Durchlaufs.

Abb. 16–17 Dijkstras Algorithmus nach zweitem Schleifendurchlauf

Als Ergebnis des zweiten Schleifendurchlaufs wird Q wie folgt angepasst:

Q = (y, 7), (u : 8), (v : ∞)

Man beachte hierbei die Anpassung des Wertes von D[u]. Hier wird notiert, dass der indirekte Weg über x geringere Kosten als die direkte Kante (s, u) erfordert.

Im dritten Schritt wird nun der Knoten y bearbeitet. Abbildung 16–18 zeigt das Ergebnis.

Nach dem dritten Durchlauf sieht Q wie folgt aus:

Q = (u : 8), (v : 13)

Abb. 16–18 Dijkstras Algorithmus nach drittem Schleifendurchlauf

Abb. 16–19 Dijkstras Algorithmus nach viertem Schleifendurchlauf

Im vierten Schritt wird nun der Knoten u bearbeitet (Abbildung 16–19). Q enthält nun nur noch einen Knoten:

Q = (v : 9)

Die Abarbeitung des letzten Knotens ändert nun nichts mehr an den Distanzwerten, Abbildung 16–19 zeigt bereits das Endergebnis der Berechnung. Die Prioritätswarteschlange ist leer: Q = .

Wie immer bei Greedy-Verfahren müssen wir uns nun genau überlegen, ob das Verfahren tatsächlich immer das Optimum berechnet.

Wir wissen, dass nur nichtnegative Kantengewichte vorliegen. Betrachten wir nun einen Iterationsschritt und nehmen an, dass wir in den bisherigen Iterationen jeweils einen Knoten mit korrektem Distanzwert hinzugenommen haben.

In dem Iterationsschritt wird die »billigste« Verbindung zu einem noch nicht bearbeiteten Knoten hinzugenommen. Für diese Verbindung gilt Folgendes:

• Da die bisher bearbeiteten Knoten den korrekten Distanzwert haben, ist der neue Distanzwert durch den »billigsten« aus dem bisher bearbeiteten Teilgraphen um genau eine Kante hinausgehenden Pfad bestimmt.
• Jeder Pfad zum Zielknoten dieses Pfades, der um mehr als eine Kante aus dem bearbeiteten Bereich hinausgeht, ist teurer als die gewählte, da Kosten mit zusätzlich hinzugenommenen Kanten nicht sinken können.

Man beachte, dass die Argumentation nicht für negative Kantengewichte gelten würde.

Der Aufwand von Dijkstras Algorithmus wird durch die Operationen zur Entnahme der Knoten aus der Warteschlange sowie zur Anpassung der Distanzwerte der benachbarten Knoten bestimmt. Für den Fall, dass alle Operationen der Prioritätswarteschlange in O(1) ausgeführt werden können, beträgt der Aufwand bei einem Graphen mit m Kanten und n Knoten demnach O(m + n). Für eine Prioritätswarteschlange auf Basis einer verketteten Liste bedeutet dies somit O(n²), für eine Heap-basierte Variante entsprechend O(m log n). Für beliebige Kantengewichte werden aufwendigere Algorithmen benötigt.

16.4.3A*-Algorithmus

Informierte Suchverfahren

Wie Dijkstras Algorithmus dient der A*-Algorithmus zur Bestimmung des kürzesten Weges zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten. Im Unterschied zu Dijkstras Algorithmus gehört der A*-Algorithmus jedoch zu den informierten Suchverfahren: Er verwendet eine Heuristik – eine Art »Daumenregel« – zur Beschleunigung der Lösungsfindung. Konkret bedeutet dies, dass zuerst die vielversprechendsten Knoten untersucht werden, d.h. diejenigen, die wahrscheinlich schneller zum Ziel führen. Hierzu kommen pro Knoten u drei verschiedene Kostenwerte zur Anwendung:

• g(u) bezeichnet die bisherigen Kosten vom Startknoten bis zu u,
• h(u) die geschätzten Kosten von u bis zum Zielknoten,
• f(u) die Kosten vom Start zum Ziel über den Knoten u, d.h.

f(u) = g(u) + h(u)

Heuristik

Die h-Kosten stellen hierbei die Heuristik dar. Bei der Routenplanung kann hierfür beispielsweise die Entfernung zweier Orte in Luftlinie genutzt werden, die aus den GPS-Koordinaten einfach berechnet werden kann. Eine Mindestanforderung an derartige Heuristiken ist die Zulässigkeit, die besagt, dass Kosten niemals überschätzt werden dürfen: Ist die tatsächliche Entfernung (entlang der Straßen) zwischen zwei Orten etwa d, muss die geschätzte Entfernung h (in Luftlinie) kleiner sein: h < d. Für die Luftlinie ist dies offensichtlich gegeben. Eine schärfere Form ist die Konsistenz (manchmal auch als Monotonie bezeichnet) einer Heuristik, die zusätzlich noch die Erfüllung der Dreiecksungleichung fordert. Hierbei dürfen die geschätzen Kosten h(u) eines Knotens u nicht größer sein als die Summe der tatsächlichen Kosten zu einem Nachbarn γ(u, v) und dessen geschätzte Kosten h(v). Die Kostenschätzung auf Basis der Luftlinie erfüllt diese Eigenschaft ebenfalls. Typischerweise wird eine konsistente Heuristik verwendet – in diesem Fall findet der A*-Algorithmus immer die optimale Lösung.

Zur Suche nach dem kürzesten Weg werden die Knoten in drei Gruppen eingeteilt:

• In der OPEN-Liste werden alle Knoten gesammelt, zu denen schon ein Weg gefunden wurde. Für jeden dieser Knoten wird der f-Wert gespeichert. Im nächsten Schritt wird dann der vielversprechendste Knoten, d.h. der mit dem kleinsten f-Wert, aus dieser Liste entnommen. Für eine effiziente Implementierung sollte daher eine Prioritätswarteschlange verwendet werden.
• In der CLOSED-Liste werden die Knoten erfasst, die fertig bearbeitet sind – zu denen also der kürzeste Weg bekannt ist.
• Alle anderen Knoten sind noch unbekannt, d.h., sie wurden noch nicht untersucht.

Expandieren von Knoten

Der A*-Algorithmus arbeitet nun wie folgt (Algorithmus 16.4). Zunächst wird der Startknoten in die OPEN-Liste eingetragen. Danach wird so lange der Knoten mit dem kleinsten f-Wert aus dieser Liste entnommen und verarbeitet, bis diese Liste leer ist. Bei der Verarbeitung wird zuerst überprüft, ob der entnommene Knoten dem Zielknoten entspricht. In diesem Fall wurde der Weg gefunden und kann ausgegeben werden. Andernfalls wird der Knoten expandiert, d.h., dessen Nachfolgeknoten werden in die OPEN-Liste aufgenommen, der Knoten selbst wird zur CLOSED-Liste hinzugefügt.

Algorithmus 16.4 A*-Algorithmus

Beim Expandieren eines Knotens u werden alle Nachfolgeknoten v untersucht. Ist v bereits in der CLOSED-Liste, kann er ignoriert werden. Sonst wird der f-Wert aus dem Weg bis zum Knoten u (d.h. der g-Wert von u), dem Gewicht γ(u, v) und der geschätzten Entfernung h von v zum Zielknoten bestimmt. Anhand dieses f-Wertes kann ermittelt werden, ob bereits ein kürzerer Weg zu diesem Knoten gefunden wurde. In diesem Fall kann der Knoten bzw. der aktuelle Weg ignoriert werden. Abschließend werden noch die g- und f-Kosten des Knotens aktualisiert und der Knoten selbst in die OPEN-Liste aufgenommen. Zur Speicherung des Weges werden die Knoten rückwärts verkettet: Jeder Knoten hat einen Verweis auf seinen Vorgänger. Am Ende kann dann der kürzeste Weg rückwärts ausgehend vom Zielknoten rekonstruiert werden.

Betrachten wir hierzu ein kleines Beispiel zur Routenplanung zwischen einigen ausgewählten Städten (Abbildung 16–20), wobei die Entfernungen unter Verwendung gängiger Webanwendungen wie maps.google.de und www.luftlinie.org ermittelt wurden. Die Aufgabe ist das Finden des kürzesten Weges zwischen Ilmenau und Magdeburg.

Der A*-Algorithmus übernimmt Ilmenau als Startknoten in die OPEN-Liste. Von hier aus geht es zunächst nur nach Erfurt, wodurch Erfurt in die OPEN-Liste und Ilmenau in die CLOSED-Liste eingetragen werden. Von Erfurt gibt es drei mögliche Varianten – Kirchheim, Sangerhausen und Hermsdorf – die ebenfalls in die OPEN-Liste aufgenommen werden. Unter Nutzung der Heuristik (Entfernung nach Magdeburg in Luftlinie) wird zunächst Sangerhausen weiter untersucht, da die geschätzte Weglänge (f-Kosten) hier 199 km beträgt, im Gegensatz zu Hermsdorf mit 241 km und Kirchheim mit 347 km. Danach wird Erfurt in die CLOSED-Liste verschoben. Abbildung 16–21 zeigt diesen Zustand: Für jeden Knoten sind jeweils die h-Kosten angegeben, die Knoten in der OPEN-Liste sind grau dargestellt, die Knoten der CLOSED-Liste gestrichelt. Weiterhin sind auch die Vorgängerbeziehungen der bereits bearbeiteten Kanten eingetragen.

Abb. 16–20 A*-Algorithmus: Beispiel

Abb. 16–21 A*-Algorithmus: Beispiel im 2. Schritt

Im weiteren Verlauf werden die von Sangerhausen direkt erreichbaren Knoten betrachtet: Erfurt ist bereits in der CLOSED-Liste und kann deshalb ignoriert werden, Göttingen, Magdeburg und Leipzig werden dagegen in die OPEN-Liste eingetragen. Die OPEN-Liste enthält danach folgende Einträge (f-Kosten in Klammern):

Magdeburg (216), Hermsdorf (241), Leipzig (307), Kirchheim (347), Göttingen (384)

Aus dieser Liste wird Magdeburg zuerst entnommen, da hier der f-Wert am kleinsten ist. Magdeburg ist gleichzeitig auch der Zielknoten und somit kann die Suche beendet werden. Das Zurückverfolgen des Weges über die Vorgängerbeziehungen liefert schließlich den Weg

Ilmenau → Erfurt → Sangerhausen → Magdeburg

Abschließend wollen wir noch eine Java-Implementierung dieses Algorithmus angeben. Hierzu wurde die Graph-Klasse aus Programm 16.1 erweitert: Die Klasse Node wurde um einen Verweis auf den Vorgänger predecessor sowie drei Kostenwerte ergänzt. Den Kern der Implementierung in Programm 16.3 bildet die Methode search. Für die Heuristik werden im Beispiel einfach feste Werte angenommen, die in einer Methode estimateCost ausgelesen werden. In einer realen Routenplanung würden hier etwa aus den gespeicherten GPS-Koordinaten der Orte die Entfernungen in Luftlinie berechnet werden.

Programm 16.3 A*-Suche in Java

Bei der Java-Variante ist zu beachten, dass die verwendete Implementierung einer Prioritätswarteschlange java.util.PriorityQueue bei einer Änderung des Vergleichskriteriums der Objekte (hier der f-Kosten) keine Umsortierung vornimmt. Daher wird der betroffene Knoten jeweils zunächst aus der OPEN-Liste entfernt und anschließend mit neuem Wert neu eingetragen.

Die Rekonstruktion des Weges erfolgt durch eine eigene Methode reconstructPath, die eine Liste mit den Knoten entlang des kürzesten Weges ausgibt.

Eigenschaften des A*-Algorithmus

Fassen wir abschließend noch einmal die wichtigsten Eigenschaften des A*-Algorithmus zusammen:

• Der Algorithmus ist vollständig, d.h., sofern eine Lösung existiert, wird diese auch gefunden.
• Falls eine konsistente Heuristik zum Einsatz kommt, wird immer die optimale Lösung gefunden.
• Es gibt keinen anderen Algorithmus, der die Lösung bei Nutzung der gleichen Heuristik schneller findet – der A*-Algorithmus ist optimal effizient.

Die Laufzeitkomplexität des A*-Algorithmus ist zunächst quadratisch: O(|V|²). Entscheidenden Einfluss hat jedoch die Realisierung der OPEN-Liste. Bei einer Variante auf Basis binärer Heaps (Abschnitt 14.6.1) beträgt die Komplexität

O((n + e) log n),

wobei n die Anzahl der expandierten Knoten bezeichnet und e die Anzahl der besuchten Kanten. Mit sogenannten Fibonacci-Heaps [FT87] sind sogar O(n log n + e) erreichbar.

Vergleicht man den A*-Algorithmus mit dem Algorithmus von Dijkstra, so fällt die Verwandtschaft auf. Tatsächlich kann der Dijkstra-Algorithmus als eine spezielle Form des A*-Algorithmus angesehen werden, die gerade keine Heuristik verwendet, bei der also h = 0 und damit auch f = g ist. Damit lassen sich auch die Vor- und Nachteile charakterisieren: Der A*-Algorithmus ist besser, wenn eine (konsistente) Heuristik genutzt werden kann, da sich dadurch die Laufzeit verkürzen lässt. Dijkstras Verfahren ist dagegen besser, wenn keine Heuristik zum Einsatz kommen kann, etwa weil das Ziel bei der Suche noch nicht bekannt ist. Ein Beispiel hierfür ist die Umkreissuche: Vom aktuellen Punkt aus soll die nächste Raststätte gefunden werden.

16.4.4Kürzeste Wege mit negativen Kantengewichten

Dijkstras Algorithmus funktioniert nur, wenn Kantengewichte keine negativen Werte annehmen können. Dies kann man sich leicht daran verdeutlichen, dass eine lokal ungünstige nächste Kante durch eine darauf folgende negativ gewichtete Kante nachträglich zu einer besseren Verbindung führt. Allgemein versagen unter diesen Bedingungen Greedy-Verfahren, die nur ein lokales Optimum wählen.

Abbildung 16–22 zeigt einen Graphen mit negativen Kantengewichten. Derartige Graphen können zum Beispiel entstehen, wenn in einem Verbindungsnetz Verbindungen mit negativen Kosten (also Gewinnen) versehen werden, um die Auslastung von Knoten oder Verbindungen durch Anreize zu erhöhen (etwa Auslastung von innerstaatlichen Flugverbindungen durch Bonusangebote).

Abb. 16–22 Graph mit negativen Kantengewichten

Ein Algorithmus, der auch im allgemeinen Fall beliebiger Kantengewichte funktioniert, ist der Bellman-Ford-Algorithmus. Dieser Algorithmus arbeitet nach einem komplett anderen Prinzip: In mehreren Durchläufen wird jeweils die beste bisher mögliche Verbindung bestimmt, wobei der i-te Durchlauf alle Pfade der Länge i berücksichtigt. Der längste Pfad ohne Zyklus hat eine Länge von |E| − 1, so dass man diesen Prozess nach |E| − 1 Durchläufen abschließen kann. Als Optimierung kann man das Verfahren vorzeitig beenden, wenn in einem Durchlauf keinerlei Änderung zur vorigen Wertebelegung mehr auftrat. Das Verfahren von Bellman-Ford ist in Algorithmus 16.5 skizziert (die D[x] sind wieder mit unendlich vorbesetzt).

Algorithmus 16.5 Bellmann-Ford-Algorithmus

Für das folgende Beispiel nehmen wir an, dass in jedem Schritt die D[x] der letzten Iteration genommen werden, also dass for each zu-mindestens konzeptionell parallel ausgeführt wird. Diese Annahme beeinträchtigt aber nicht die Korrektheit der Ausführung.

Abbildung 16–23 zeigt die Initialisierung des Graphen aus Abbildung 16–22 mit den initialen D[x]-Werten. Die Initialisierung des Knotens s mit 0 bestimmt den Knoten, von dem aus die kürzesten Wege berechnet werden.

Abb. 16–23 Bellman-Ford-Algorithmus: Initialisierung

In der Abbildung 16–24 sieht man den Zustand nach der ersten Iteration. Alle Pfade der Länge 1 wurden berücksichtigt. Nur die Knoten u und x haben dadurch einen neuen D-Wert.

Abb. 16–24 Bellman-Ford-Algorithmus: Schleifendurchlauf für i = 1

Nach der ersten Iteration hat der Knoten u einen vorläufigen Wert von 10 bekommen, da er von s direkt mit einer Kante des Gewichtes 10 erreicht werden kann. Man sieht, dass derartige Zwischenergebnisse nicht die endgültigen Entfernungen sind, da mittels eines Pfades der Länge 2 (über x) eine billigere Verbindung mit Kosten 5 + 3 = 8 aufgebaut werden kann.

Die Abbildung 16–25 zeigt den Zustand nach der zweiten Iteration. Pfade der Länge 2 wurden berücksichtigt; der Knoten u hat daher bereits seinen endgültigen Wert zugewiesen bekommen.

Abbildung 16–26 zeigt nun die Berücksichtigung von Pfaden der Länge 3. Die Änderung des Wertes D[u] kann erst jetzt an den Knoten v propagiert werden – die Kante (u, v) wird also zweimal zur Berechnung von D[v] herangezogen.

Abb. 16–25 Bellman-Ford-Algorithmus: Schleifendurchlauf für i = 2

Abb. 16–26 Bellman-Ford-Algorithmus: Schleifendurchlauf für i = 3

Die Abbildung 16–27 zeigt das Ergebnis des letzten Durchgangs, in dem die negativ gewichtete Kante (v, y) zur Berechnung des Wertes D[y] genutzt wird. Ein Greedy-Verfahren, das jeden Knoten nur einmal besucht, hätte für y den in jedem Schritt lokal optimalen Pfad s, x, y gewählt und daher nicht das beste Ergebnis geliefert.

Abb. 16–27 Bellman-Ford-Algorithmus: Schleifendurchlauf für i = 4

Zyklen negativer Länge

Betrachten wir abschließend noch die Situation nach |E| − 1 Iterationen. Eine Kante könnte noch verbessert werden (in einem Schritt) genau dann, wenn der Graph einen Zyklus mit negativer Länge enthält.

Dies kann man mittels einer Argumentation über die Länge möglicher kürzester Pfade beweisen. Derartige Pfade können maximal |E|− 1 Kanten ohne Zyklen enthalten; deren kürzeste Entfernung wird bei |E| − 1 Iterationen korrekt berechnet.

Abbildung 16–28 zeigt einen derartigen Graphen mit negativ gewichtetem Zyklus.

Der Zyklus s, x, u, v, y, s in dem Graphen aus Abbildung 16–28 hat die Kosten 5 + 3 + 1 − 5 − 7 = −3; jeder Durchlauf durch den Zyklus erzeugt also einen Gewinn, es gibt hier keinen günstigsten Pfad endlicher Länge!

Abb. 16–28 Graph mit negativ gewichtetem Zyklus

16.4.5Maximaler Durchfluss

Neben den kürzesten Pfaden gibt es eine Reihe weiterer interessanter Fragestellungen für gewichtete Graphen. Wir werden mit der Frage nach dem maximalen Durchfluss eine weitere praxisrelevante Fragestellung genauer betrachten.

Maximaler Durchfluss durch Netzwerk

Das Problem des maximalen Durchflusses wird durch logistische Aufgaben motiviert. Ein Beispiel ist die Paketvermittlung in Computernetzwerken. Abbildung 16–29 zeigt ein hypothetisches Netzwerk, in dem Verbindungen zwischen zwei Rechnern eine Kapazität von k pro Zeiteinheit zu verschickenden Datenpaketen haben. Sollen nun von dem Rechner Quelle ein große Anzahl von Paketen möglichst schnell (oder gar unter Echtzeitanforderungen, etwa einer Videoübertragung) zum Rechner Ziel übertragen werden, stellt sich die Frage der maximal übertragbaren Pakete.

Abb. 16–29 Paketvermittlung in Computernetzwerk

Netzwerk als Graph mit Kapazitäten

Dieses Problem ist als die Bestimmung des maximalen Durchflusses durch ein Netzwerk bekannt. Wir werden diese Fragestellung nun konkretisieren, indem wir das Netzwerk als gerichteten Graphen G mit Kapazitäten modellieren.

Aktueller Fluss

Ein (Durch-)Fluss F legt für jede Kante einen aktuellen Fluss fest, der in einem korrekten Fluss unter der maximalen Kapazität liegt. In einem Fluss kennen wir für jede Kante den Wert c der maximalen Kapazität und den Wert f des aktuellen Flusses. Indirekt ist uns damit mit c − |f| auch die verbleibende, nicht genutzte Kapazität bekannt. Diese verbleibende Kapazität wird als verfügbare Kapazität bezeichnet.

Ein Sonderfall sind Verbindungen, die in beiden Richtungen genutzt werden können. Dies wird mittels zweier entgegengesetzt gerichteter Kanten mit identischer Kapazität modelliert. Wir werden im Algorithmus einen positiven Fluss in eine Richtung durch einen (imaginären) negativen Fluss in die andere Richtung ausgleichen. Als Resultat entsteht der unerwartete Effekt, dass ein aktueller Fluss für eine dieser Kanten dabei einen negativen Wert annimmt.

Korrekter Durchfluss

Wir haben bereits den Begriff des korrekten Flusses erwähnt. Ein korrekter Fluss muss die folgenden Bedingungen erfüllen:

Korrekheitsbedingungen für Durchfluss

1. Die Einschränkungen der Kapazität der Kanten werden eingehalten (auch bei negativem Fluss!):

   |f(u, v)| ≤ c((u, v))

2. Die Konsistenz des Flusses besagt, dass auch bei in beiden Richtungen nutzbaren Verbindungen als Nettoeffekt nur in eine Richtung gesendet wird, und der entstehende negative Fluss den korrekten Wert annimmt:

   f(u, v) = −f (v, u)

3. Wichtigstes Korrektheitskriterium ist die Bewahrung des Flusses für jeden Knoten v ∊ V − {q, z} mit Ausnahme der Quelle q und des Ziels z :

   

Maximaler Durchfluss

Der Wert eines Flusses für eine Quelle q ist durch den dort herausfließenden aktuellen Fluss bestimmt:

Alternativ könnte man auch den am Ziel ankommenden Fluss bestimmen – bei einem korrekten Fluss müssen diese Werte identisch sein.

Maximaler Flusses

Gesucht wird nun für einen gegebenen Graphen G mit Kapazitäten, einer Quelle q und einem Ziel z der maximale Fluss, der wie folgt definiert ist:

max{val(G, F, q) | F ist korrekter Fluss in G bezgl. q und z}

Im folgenden Abschnitt werden wir einen effizienten Algorithmus zur Berechnung des maximalen Flusses vorstellen.

16.4.6Der Ford-Fulkerson-Algorithmus für die Bestimmung des maximalen Flusses

Der Ford-Fulkerson-Algorithmus

Der Ford-Fulkerson-Algorithmus bestimmt für einen mit Kapazitäten versehenen Graphen den maximalen Durchfluss von einer Quelle zu einem Ziel. Der Algorithmus arbeitet mit einer Mischung aus Zufallsauswahl und Greedy-Vorgehen.

Als nutzbaren Pfad bezeichnen wir einen (zyklenfreien) Pfad von der Quelle q zum Ziel z, der an allen verwendeten Kanten eine verfügbarer Kapazität (also c − |f| ≥ 1 für ganzzahlige Kapazitäten) hat. Ein derartiger Pfad hat einen nutzbaren Fluss, gegeben durch das Minimum der verfügbaren Kapazitäten der einzelnen Kanten.

Der Algorithmus arbeitet nun nach einem einfachen Prinzip: Füge so lange verfügbare Pfade zum Gesamtfluss hinzu wie möglich. Der Ford-Fulkerson-Algorithmus kann in Pseudocode-Notation daher wie folgt skizziert werden:

Wir werden nicht auf das Verfahren zur Auswahl eines nutzbaren Pfades eingehen – dies kann etwa durch Tiefensuche entlang nutzbarer Kanten erfolgen. Stattdessen werden wir das Funktionieren des Verfahrens anhand eines einfachen Beispielszenarios demonstrieren.

Die Abbildung 16–30 zeigt ein Beispielnetzwerk, bestehend aus sieben Knoten. Die Kanten werden mit drei Werten beschriftet, wobei der dritte Wert nur zur Verdeutlichung dient, da er aus den ersten beiden berechnet werden kann.

Abb. 16–30 Graph mit Kapazitäten mit leerem Fluss

Der erste notierte Wert ist der aktuelle Fluss f entlang der Kante. Im initialisierten Graphen ist dieser Wert überall 0. Der zweite Wert ist die vorgegebene Kapazität c. Die abgeleitete noch verfügbare Kapazität c − f wird als dritter Wert notiert.

In den folgenden Beispielabbildungen wird der jeweils ausgewählte nutzbare Pfad fett dargestellt. Kanten ohne verbleibende Kapazität sind gestrichelt gezeichnet.

Die Abbildung 16–31 zeigt als ersten Schritt die Auswahl eines nutzbaren Pfades. Am Beginn wird aus der Vielzahl nutzbarer Pfade zufällig oder mit einer geeigneten Heuristik ein Pfad ausgewählt.

Abb. 16–31 Ford-Fulkerson: Auswahl des ersten Pfades

Im Beispiel wird der Pfad q → c → e → z mit der nutzbaren Kapazität 2 ausgewählt, obwohl sowohl kürzere Pfade als auch nutzbare Pfade mit höherer Kapazität existieren.

Abb. 16–32 Ford-Fulkerson: Adjustierung der Kantenbeschriftung und Auswahl des zweiten Pfades

In Abbildung 16–32 sind das Ergebnis dieses Schrittes – die Adjustierung der Kantenbeschriftungen – sowie die Auswahl des zweiten Pfades q → e → d → z dargestellt. Da die Kapazität der Kante c → e nach dem ersten Schritt bereits erschöpft ist, ist diese gestrichelt gezeichnet. Der Suchraum nutzbarer Pfade hat sich nach diesem Schritt bereits verkleinert, da (c, d) nicht mehr verfügbar ist.

Die adjustierten Kantenbeschriftungen sind in Abbildung 16–33 angegeben. Eine Besonderheit ist hierbei die Adjustierung der Rückkante d → e mit einem negativen Wert. Die Auswahl des dritten Pfades q → a → b → z mit der Kapazität 2 ist ebenfalls in dieser Abbildung dargestellt.

Abb. 16–33 Ford-Fulkerson: Auswahl des dritten Pfades

Als vierter Pfad wird q → a → d → e → z mit einer Kapazität von 1 ausgewählt. Dieser Schritt ist gemeinsam mit den aktualisierten Kantenbeschriftungen nach Schritt 3 in Abbildung 16–34 zu sehen.

Abb. 16–34 Ford-Fulkerson: Auswahl des vierten Pfades

Nach diesem Schritt muss auch die Kante d → e mit der negativen Kapazität adjustiert werden. Dies zieht eine Aktualisierung der Rückkante e → d nach sich (deren Kapazität danach nicht mehr erschöpft ist), so dass sich die in Abbildung 16–35 angegebenen Kapazitäten ergeben. Schließlich wird noch als fünfter Pfad q → c → d → z ausgewählt.

Da damit keine weiteren Pfade möglich sind, ist die Berechnung des maximalen Flusses beendet und es ergibt sich die in Abbildung 16–36 dargestellte Nutzung der verfügbaren Kapazitäten.

Abb. 16–35 Ford-Fulkerson: Auswahl des fünften Pfades

Abb. 16–36 Ford-Fulkerson: Abschluss der Berechnung

Aus der obigen Beschreibung des Verfahrens von Ford-Fulkerson wird ersichtlich, dass es sich eigentlich noch nicht um einen »wirklichen« Algorithmus handelt: Welcher Pfad in jedem Schritt ausgewählt wird, bleibt offen und man kann sich vorstellen, dass die Anzahl der Iterationen von der Wahl der Pfade beeinflusst wird. So wurden Verbesserungen in Form von Heuristiken zur Auswahl geeigneter Pfade vorgeschlagen. Das Verfahren von Edmonds und Karp basiert beispielsweise auf der Eigenschaft, dass die Anzahl der Pfade, die in einem Graphen G = (V, E) bis zum Finden des maximalen Flusses verfolgt werden müssen, kleiner als |V ||E| ist, wenn jeweils der kürzeste verfügbare Pfad von der Quelle q zum Ziel z gewählt wird. Demzufolge kann zur Auswahl des jeweils nächsten Pfades eine Variante des Breitendurchlaufs verwendet werden, die für jede Iteration den kürzesten Pfad ermittelt.

16.5Zentralitätsanalyse in Graphen

Analyse von Graphen
Soziales Netzwerk

Neben den Such- und Traversierungsverfahren gibt es für Graphen noch eine Reihe weiterer Fragestellungen. So spielt die Analyse von Graphen in vielen Anwendungen eine wichtige Rolle, sei es in Logistik und Transport zur Routenoptimierung, bei den Betreibern von Kommunikationsnetzen, in der Biologie zur Analyse von Proteinstrukturen oder Genexpressionen oder in der Chemie zur Analyse komplexer chemischer Verbindungen. Auch in den Sozialwissenschaften werden Graphen untersucht: Hier bilden die Beziehungen zwischen Individuen, ihre sozialen Strukturen wie etwa Freundschaftsbeziehungen oder soziale Position und Rollen ein soziales Netzwerk. In der Vergangenheit wurden derartige Beziehungen durch Befragungen untersucht. Mit der Verfügbarkeit von webbasierten Plattformen wie Facebook, LinkedIn oder Twitter, die Millionen Nutzer haben, sind inzwischen riesige Datenmengen mit extrem großen Graphen vorhanden. Gerade diese Datenbasis mit den Möglichkeiten einer darauf aufbauenden Analyse stellt den größten Wert dieser Unternehmen dar.

Im Mittelpunkt der sozialen Netzwerkanalyse stehen Fragestellungen wie:

Zentralitätsanalyse

• die Zentralitätsanalyse zur Identifikation der »wichtigsten« Akteure (Influencer oder Opinion Leader),
• die Erkennung von Communitys, d.h. Gruppen oder Teilgraphen, durch die Analyse von Netzwerkstrukturen und Topologien,
• die Rollenanalyse zur Bestimmung der Rolle verschiedener Akteure in Interaktionen, z.B. als »Brücke« zwischen verschiedenen Communitys,
• die Informationsdiffusion als Analyse der Propagierung von Informationen durch das Netzwerk (z.B. Dynamik, Infektion).

PageRank-Algorithmus

Wir wollen an dieser Stelle stellvertretend die Zentralitätsanalyse betrachten und dafür mit dem PageRank-Algorithmus auch einen konkreten, sehr bekannten Algorithmus vorstellen. Grundsätzlich gibt es verschiedene Möglichkeiten, »zentrale« Knoten in einem Graphen zu bestimmen. Die einfachste Form ist die Bestimmung der Knotengrade (siehe Abschnitt 16.1.4): Hierbei liegt die Annahme zugrunde, dass ein Akteur (Knoten) mit vielen Verbindungen (Kanten, z.B. Freunden oder Followern) wichtiger oder zentraler ist als ein Akteur mit weniger Verbindungen. Andere Verfahren berücksichtigen nicht nur die direkten, sondern auch die indirekten Beziehungen im Graphen, die Nähe (in Form der Distanzen) zu allen anderen Knoten oder die Wichtigkeit der Nachbarknoten.

Eine Variante der letzteren Form (der sogenannten Eigenvektor-Zentralität) ist der PageRank-Algorithmus, der ursprünglich für die Google-Suchmaschine von Larry Page und Sergey Brin entwickelt wurde. Ziel war es dabei, ein Ranking der Webseiten als Antwort auf eine Suchanfrage zu bestimmen. Die Annahme von PageRank ist, dass ein Webseite mit mehr Verweisen darauf (d.h. mit eingehenden Links) und insbesondere mit mehr einflussreichen (d.h. wichtigen) Verweisen relevanter ist als Seiten mit weniger Verweisen. PageRank bestimmt somit den transitiven Einfluss von Webseiten. Das von der Suchmaschine erfasste Web wird dazu als Graph aufgefasst: Webseiten sind Knoten und Links zwischen Seiten bilden die Kanten.

Der PageRank-Wert R_i einer Seite i wird wie folgt berechnet:

Hierbei sind

• R_j der PageRank-Wert der Seite j, die auf Seite i verweist,
• N_j die Gesamtzahl der ausgehenden Links der Seite j,
• d ein Dämpfungsfaktor mit 0 ≤ d ≤ 1, der die Weitergabe des PageRank-Wertes einer Seite auf eine andere verringert. 1 − d ist damit die Wahrscheinlichkeit, dass der Knoten auch direkt ohne Links erreicht wird.

Aus der Gesamtheit aller Seiten ergibt sich ein Gleichungssystem, das allerdings für sehr große Graphen nicht mehr auf praktikable Weise gelöst werden kann. Daher wird der PageRank-Algorithmus üblicherweise iterativ berechnet, indem jedem Knoten zunächst ein initialer PageRank-Wert zugewiesen wird, der anschließend in mehreren Iterationen aktualisiert wird – entweder bis die Berechnung konvergiert oder eine bestimmte Zahl von Iterationen erreicht wird.

Das Beispiel in Abbildung 16–37 illustriert diesen Ablauf. Gegeben sind die 5 Knoten A-E, die Webseiten repräsentieren. Die Kanten stellen Verweise (Links) auf die jeweiligen Seiten dar. Initial wird jedem Knoten ein PageRank-Wert von 1/5 = 0.2 zugewiesen (links oben in der Abbildung). Damit können die PageRank-Werte auf die ausgehenden Kanten aufgeteilt und so die Link-Werte berechnet werden. Für den Knoten A mit zwei ausgehenden Kanten bedeutet dies 0.2/2 = 0.1 für jede Kante, für den Knoten B dementsprechend 0.2/3 = 0.067 pro Kante (links unten).

Im nächsten Iterationsschritt werden darauf aufbauend neue PageRank-Werte der Knoten aus der Summe der Link-Werte berechnet – im Beispiel zum einfachen Nachvollziehen ohne Anwendung des Dämpfungsfaktors. Damit ergibt sich für den Knoten A der neue Wert 0.06, für B der Wert 0.1, für C 0.36, für D 0.2 und für E demzufolge 0.26 (Mitte oben), woraus wiederum die Link-Werte berechnet werden können.

Abb. 16–37 Beispiel der PageRank-Berechnung

Betrachten wir abschließend eine einfache Implementierung dieses Algorithmus in Java.

Programm 16.4 PageRank-Implementierung

Den Kern dieser Implementierung bildet die Methode updatePageRank, die einen kompletten Iterationsschritt durchführt. Dazu werden zunächst die PageRank-Werte aus dem Vorgängerschritt gesichert. Anschließend werden die neuen PageRank-Werte wie folgt berechnet: Für jeden Knoten j, der eine Kante zum betrachteten Knoten i besitzt, wird der alte PageRank-Wert durch die Anzahl der ausgehenden Kanten dividiert und auf den PageRank-Wert von Knoten i summiert. In der abschließenden Schleife wird noch der Dämpfungsfaktor angewendet. Diese Methode wird von der eigentlichen calc-Methode aufgerufen, die nach der Initialisierung der PageRank-Werte aller Knoten updatePageRank wiederholt ausführt. In der angegebenen Implementierung erfolgt dies zur Vereinfachung konstant hundertmal, alternativ sollte als Abbruchkriterium der Berechnung das Unterschreiten eines Schwellwertes der Änderung der PageRank-Werte von einem Iterationsschritt zum nächsten verwendet werden.

In der Praxis besteht die Herausforderung einer effizienten Implementierung insbesondere in der Größe der Matrix, die hier in der main-Methode als 5x5-Matrix für den Graphen aus Abbildung 16–37 angelegt wird. Für sehr große Graphen etwa bei Suchmaschinen oder in sozialen Netzwerken ergeben sich aber Matrizen mit Millionen oder gar Milliarden Zeilen und Spalten, deren Berechnung deutlich aufwendiger ist.

16.6Weitere Fragestellungen für Graphen

Auf dem Gebiet der Graphenalgorithmen gibt es noch eine Vielzahl interessanter Problemstellungen, deren detaillierte Betrachtung allerdings den Rahmen dieses Buches sprengen würde. Wir werden daher als Abschluss dieses Kapitels nur kurz einige ausgewählte Probleme skizzieren, um einen Eindruck über die Aufgaben und auch die Anwendungsgebiete zu vermitteln.

Problem des Handlungsreisenden

Problem des Handlungsreisenden
NP-vollständig

Eine der wohl bekanntesten Aufgabenstellungen im Bereich der Graphentheorie ist das Problem des Handlungsreisenden (engl. travelling salesman problem). Hierbei soll ein Handlungsreisender nacheinander n Städte besuchen und am Ende wieder an seinem Ausgangspunkt ankommen. Dabei soll jede Stadt nur einmal besucht werden und der Weg mit den minimalen Kosten gewählt werden. Alternativ kann auch ein Weg ermittelt werden, dessen Kosten unter einer vorgegebenen Schranke liegen. Ein naiver Ansatz zur Lösung dieses Problems ist das erschöpfende Durchsuchen des Graphen, indem alle möglichen Rundreisen betrachtet werden und schließlich die mit den geringsten Kosten ausgewählt wird. Allerdings versagt dieses Verfahren bei größeren Graphen aufgrund der hohen Komplexität. Tatsächlich ist das Problem des Handlungsreisenden ein NP-vollständiges Problem, wobei die Komplexität nach heutigem Wissensstand bei O(2ⁿ) liegt. Üblicherweise verwendet man daher zur Lösung Optimierungsverfahren, die suboptimale Lösungen liefern.

Planare Graphen

Eine weitere Aufgabenstellung mit einem praktischen Bezug ist das Problem planarer Graphen. Gegeben ist hierbei ein beliebiger Graph G. Die Frage ist nun: Lässt sich dieser Graph G planar zeichnen, d.h. ohne sich überschneidende Kanten? Diese Aufgabe besteht beispielsweise beim Chip- oder auch Leiterplatten-Design, wo Leiterbahnen zwischen elektronischen Bauelementen möglichst kreuzungsfrei zu gestalten sind.

Eine vorgeschlagene Lösung besteht darin, zu untersuchen, ob der Graph ein (isomorphes) Abbild von K₅ oder K_3,3-Graphen als Teilgraphen (Abbildung 16–38) besitzt. In diesem Fall gibt es keinen planaren Graphen.

Abb. 16–38 K₅und K_3,3

Weitere Fragestellungen in diesem Kontext sind u.a.:

• Das Finden »schöner« planarer Darstellungen, wobei die Winkel zwischen Kanten an Knoten nicht zu klein werden, die Längen der Kanten nicht zu stark differieren oder die Knoten gemäß bestimmten geometrischen Strukturen angeordnet sind.
• Darstellungen mit einer minimalen Anzahl von Kantenüberschneidungen, beispielsweise zur Minimierung der Anzahl von Brücken in Förderanlagen oder auch in elektronischen Schaltungen.
• Das Zerlegen eines nichtplanaren Graphen in eine minimale Anzahl planarer Teilgraphen, wenn z.B. im Chip-Design Leiterbahnen in mehreren Ebenen angeordnet werden sollen.

Abb. 16–39 Ländernachbarschaft in Europa als Graph

Einfärben von Graphen

Ein letztes hier zu betrachtendes Problem ist das Einfärben von Graphen. Hierbei sollen die Knoten so eingefärbt werden, dass keine zwei benachbarten Knoten dieselbe Farbe haben. Mit dieser Fragestellung sind eigentlich zwei Probleme verbunden:

• die eigentliche Einfärbung,
• die Bestimmung der minimal benötigten Anzahl von Farben.

Eine nahe liegende Anwendung dieses Problems ist das Einfärben von Landkarten. Betrachtet man die Nachbarschaft von Ländern als Kanten wie in Abbildung 16–39, so entspricht das Einfärben der Länder auf der Karte dem Einfärben von Knoten.

Eine andere Anwendung ist etwa die Vergabe von überschneidungsfreien Klausurterminen. Hierbei bilden die Fächer die Knoten. Eine Kante wird eingefügt, wenn ein Student beide zu den Knoten korrespondierenden Fächer hört.