Vorlesung Informatik 2 Algorithmen und Datenstrukturen (22 - Graphen)
Prof. Th. Ottmann
Motivation
Pregel Wie komme ich am besten von Freiburg nach Ulm?
Was ist die kürzeste Rundreise durch eine gegebene Menge von Städten?
Welche Menge an Wasser kann die Kanalisation von Freiburg maximal verkraften?
Gibt es einen Rundweg über die Brücken von Königsberg (Kaliningrad), derart dass jede Brücke nur einmal überquert wird und man zum Ausgangspunkt zurückgelangt?
Diese und viele andere Probleme lassen sich als Graphenprobleme definieren.
V x V E Í E v v Î ´) , ( ¥ < V Definition: Ein gerichteter Graph G = (V,E) (englisch: digraph) besteht aus einer Menge V = {1, 2, . . . , |V |} von Knoten (englisch: vertices) und einer Menge von Pfeilen oder Kanten (englisch: edges, arcs). Ein Paar heißt Pfeil oder Kante von v nach v´.
Darstellung:
Knoten werden durch Punkte dargestellt und
Kanten bzw. Pfeile werden durch Verbindungslinien mit Pfeilspitze auf den Endknoten dargestellt.
Einschränkung: Endliche Graphen, d.h.
Adjazenzmatrizen
î í ì Î Ï = ; falls ; falls E j i E j i a ij ) , ( 1 ) , ( 0 Adjazenzmatrizen dienen der Speicherung von Graphen.
Ein Graph G = (V,E) wird in einer Boole’schen |V | x |V |-Matrix AG = (aij), mit 1 i |V |, 1 j |V | gespeichert, wobei
class graph{ graph(int n){ this.numberOfNodes = n; this.a = new boolean[n][n]; } private int numberOfNodes; private boolean[][] a; }
Bei der Speicherung eines Graphen mit Knotenmenge V in einer Adjazenzmatrix ergibt sich ein Speicherbedarf von Θ(|V |2).
Dieser Speicherbedarf ist nicht abhängig von der Anzahl der Kanten im Graphen.
Demnach sind Adjazenzmatrizen ungünstig, wenn der Graph vergleichsweise wenige Kanten enthält.
Wegen der erforderlichen Initialisierung der Matrix oder der Berücksichtigung aller Einträge der Matrix benötigen die meisten Algorithmen Ω(|V |2) Rechenschritte.
Adjazenzlisten
E j i Î ) , ( Bei Adjazenzlisten wird für jeden Knoten eine lineare, verkettete Liste der von diesem Knoten ausgehenden Kanten gespeichert.
Die Knoten werden als lineares Feld von |V | Anfangszeigern auf je eine solche Liste verwaltet.
Die i-te Liste enthält ein Listenelement mit Eintrag j für jeden Endknoten eines Pfeils .
Adjazenzlisten unterstützen viele Operationen, z.B. das Verfolgen von Pfeilen in Graphen, sehr gut.
Andere Operationen dagegen werden nur schlecht unterstützt, insbesondere das Hinzufügen und Entfernen von Knoten.
Implementierung von Adjazenzlisten
class graphAL{ graphAL(int n){ this.numberOfNodes = n; this.edgeTo = new edge[n]; } private int numberOfNodes; private edge[] edgeTo; }
class edge { edge(int node, edge next){ this.node = node; this.next = next; } int node; edge next; }
Ein Beispiel
3 7 2 6 4 6 5 8 5 1 1 2 3 4 5 6 7 8 9
Doppelt verkettete Kantenliste
Die bei Adjazenzlisten fehlende Dynamik kann erreicht werden, indem man die Knoten in einer doppelt verketteten Liste speichert, anstatt sie in einem Feld fester Größe zu verwalten.
Jedes Listenelement dieser Liste enthält drei Verweise, zwei davon auf benachbarte Listenelemente und einen auf eine Kantenliste, wie bei Adjazenzlisten.
Jede Kantenliste ist doppelt verkettet; statt einer Knotennummer besitzt jedes Kantenlistenelement einen Verweis auf ein Element der Knotenliste.
Doppelt verkettete Kantenliste am Beispiel
1 2 3 4 5 6 7 8 9
Durchlaufen von Graphen
Für manche Probleme ist es wichtig Graphen vollständig zu traversieren, d.h. alle Knoten eines Graphen zu betrachten.
Fasst man die Web-Seiten im Internet als Knoten und die Links auf diesen Seiten als Kanten auf, so muss man beim Suchen nach einem bestimmten Schlüsselwort alle Knoten dieses Web-Seiten-Graphen inspizieren.
Das Betrachten oder Inspizieren eines Knotens in einem Graphen nennt man auch oft Besuchen des Knotens.
Manchmal ist es wichtig die Knoten nach einer gewissen Systematik zu besuchen.
Wir werden im Folgenden die Tiefensuche und die Breitensuche als zwei Spezialfälle eines allgemeinen Knotenbesuchsalgorithmus kennen lernen.
Ein allgemeines Schema für das Traversieren
Im Gegensatz zu Bäumen kann es bei Graphen Zyklen geben.
Deswegen kann es beim Traversieren passieren, dass wir bei einem schon einmal besuchten Knoten ankommen.
Aus diesem Grund müssen wir uns die bereits besuchten Knoten in einer Tabelle merken, um Endlosschleifen zu vermeiden.
Da jeder Knoten mehrere Nachfolger haben kann, müssen wir darüber hinaus eine Datenstruktur verwenden, in der wie die noch zu besuchenden Knoten ablegen.
Allgemeiner Knotenbesuchsalgorithmus für einen Graphen G = (V,E)
Konkrete Traversierungsverfahren
Die Reihenfolge, in der die Knoten ausgegeben werden, hängt offensichtlich von der Datenstruktur für den Rand ab, d. h. der Art, wie die Knoten darin abgelegt werden.
Verwendet man für die Knotenliste einen Stack, so ergibt sich ein Tiefendurchlauf durch den Graphen.
Verwendet man hingegen eine Queue, so entspricht das Verhalten einem Breitendurchlauf.
8 9 1 2 3 6 7 5 4 V v Î Definition: Das Single-Source-Shortest-Path-Problem besteht darin, für einen Graph G = (V,E) und einen Knoten die kürzesten Pfade von v zu allen anderen Knoten in G zu bestimmen.
Beispiel:
Graph g Kürzeste Pfade ausgehend von Knoten 1
1 2 1 3 1 7 1 7 5 1 7 5 4 1 7 5 4 6
Lösung des Single-Source-Shortest-Path-Problems
Der Knoten v ist von sich selbst genau 0 Schritte weit entfernt.
Die Nachbarn von v sind genau 1 Schritt entfernt.
Die Knoten der Entfernung j sind alle Knoten, die von den j -1 Schritt entfernten in genau einem Schritt erreicht werden können.
Also können wir dieses Problem durch einen Breitendurchlauf lösen.
Anstelle der Besucht-Markierungen verwenden wir jedoch ein Feld distance, um den Abstand der einzelnen Knoten abzulegen.
Dabei ist |V | - 1 die Maximaldistanz eines Knoten von v.
Damit ist die Komplexität bei Verwendung von Adjazenzlisten O(|V | + |E|).
Comments