38
G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa Städte - Verbindungswege Personen - Relationen zwischen ihnen Rechner - Verbindungen Aktionen - zeitliche Abhängigkeiten Grundlegende Konzepte (Whlg.) Gerichteter Graph (Digraph) G = (V,E) V: Menge von Knoten (vertices) E V x V: Menge von (gerichteten) Kanten (edges) wenn v und v' Anfangs- und Endknoten einer Kante sind, so heißen sie adjazent

G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

Embed Size (px)

Citation preview

Page 1: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II1

Graphalgorithmen ( elementare A. )Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwaStädte - VerbindungswegePersonen - Relationen zwischen ihnenRechner - VerbindungenAktionen - zeitliche Abhängigkeiten

Grundlegende Konzepte (Whlg.)Gerichteter Graph (Digraph) G = (V,E)

V: Menge von Knoten (vertices)E V x V: Menge von (gerichteten) Kanten (edges)

wenn v und v' Anfangs- und Endknoten einer Kante sind, so heißen sie adjazent

Page 2: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II2

Eingangsgrad: indeg(v) = |{v' | (v', v) E}|

Ausgangsgrad: outdeg(v) = |{v' | (v, v') E}|G' = (V', E') heißt Teilgraph von G = (V, E), gdw. V' V und E' E.G' = (V', E') heißt Untergraph von G = (V, E), gdw.

V' V und E' {(v,v') E | v, v' V'}.Eine Folge von Knoten (v0, v1, ..., vk) heißt Weg (der Länge k) von v0 nach vk, wenn gilt: für alle i, 0 i < k, (vi,vi+1) E. Ein Zyklus ist ein Weg von v nach v.

Baum: gerichteter Graph, so daß es einen Knoten v gibt mit1) indeg(v) = 0 und2) v v impliziert indeg(v') = 1.G heißt ungerichteter Graph wenn gilt (v,v') E impliziert (v',v) E.

Page 3: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II3

Speicherung von Graphen

a) Adjazenzmatrix

Speichere Graphen G durch |V| x |V| -Matrix AG, wobei Aij = 1 falls (vi,vj) E, 0 sonst.

Beispiel:

Speicherbedarf: O(|V|2)

b) Adjazenzlisten

Array A[1 .. |V|] von Zeigern. Jeder Zeiger A[ i ] zeigt auf eine verkettete Liste, die alle direkten Nachfolger von vi

enthält.

Beispiel:Speicherbedarf: O(|V| + |E|)

Page 4: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II4

Welche Repräsenation geeigneter ist, hängt von dem Problem ab:

Frage: Gibt es Kante von a nach b: MatrixDurchsuchen von Knoten in durch Nachbarschaft gegebener Reihenfolge: Listen

Breitensuche:

Bearbeite einen Knoten, der in n Schritten von u erreichbar ist, erst, wenn alle Knoten, die in n-1 Schritten erreichbar sind, abgearbeitet wurden.

Kann einfach verwendet werden zur Berechnung der Länge des kürzesten Wegs von vorgegebenem v0 zu anderen KnotenAdj(u) bezeichnet direkte Nachbarn von u;Q ist FIFO-Warteschlange.

Page 5: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II5

Abstände werden in array d gespeichertfor (v in V ) d [v] = °;

d [v0] = 0;Q = {v0};while (Q {}) u = pop(Q); /*erstes Element aus Q entfernt und an v zugewiesen*/

for (v in Adj(u) ) { if (d [v] == ° )

{ d [v] = d [u] + 1; Q = push (v,Q);

} }Komplexität: jede Kante und jeder Knoten einmal besucht, deshalb O(|V| + |E|),falls G zusammenhängend |E| > |V| -1, damit Komplexität O(E).

Page 6: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II6

Tiefensuche:Bearbeite einen Knoten v erst dann, wenn alle seine Söhne bearbeitet sind (außer wenn ein Sohn auf dem Weg zu v liegt)

Tiefensuche ( Knoten u ){ farbe [u] = „grau“;

while (v in Adj(u)) if (farbe[v] == „weiss“) Tiefensuche(v);

farbe[u] = „schwarz“;}

weiss: noch nicht besuchtgrau: besucht, noch nicht abgeschlossenschwarz: abgeschlossen

Komplexität O(E)

Page 7: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II7

Topologisches Sortieren:Eine topologische Sortierung eines gerichteten Graphen ist eine Sortierung der Knoten, d.h. eine bijektive Abbildung ord: V -> {1,...,|V|}, so daß gilt: (v,v') E impliziertord(v) < ord(v').Satz: Ein Graph G ist azyklisch gdw er sich topologisch sortieren läßt.Beweis: <= klar=> Induktion über |V|.Induktionsanfang: |V| = 1, keine Kante, bereits topologisch sortiertInduktionsschluß: |V| = n. Da G azyklisch ist, muß es einen Knoten v ohne Vorgänger geben. Setze ord(v) = 1. Durch Entfernen von v erhalten wir einen azyklischen Graphen G' mit |V'| = n-1, für den es nach Induktionsvoraussetzung topologische Sortierung ord' gibt. Die gesuchte topologische Sortierung für G ergibt sich durch ord(v') = ord'(v') + 1, für alle v' v.

Page 8: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II8

Aus dem Beweis ist rekursiver Algorithmus abzuleiten.Eleganter: Verwendung von Tiefensuche

n = |V|;while (v in V) farbe[v] = „weiss“ ; { while ( v in V ) if (farbe[v] == „weiss“ ) Tiefensuche(v); }

dabei muss Tiefensuche ergänzt werden um:ord[u] = n;n = n-1;

Komplexität wieder O(|V| + |E|)Bemerkung: Algorithmus setzt voraus, daß Graph azyklisch ist. Soll zusätzlich Test auf Azyklizität vorgenommen werden: ergänze while-Schleife in Tiefensuche um

if (farbe[v] == „grau“ ) { „Abbruch, Graph nicht azyklisch“}

Page 9: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II9

Transitive Hülle: Warshall-AlgorithmusSei G = (V, E) ein Graph. Die (reflexive) transitive Hülle

von G ist der Graph G* = (V, E*) mit (u,v) E* gdw es gibt Pfad von u nach v in G (einschließlich Pfade Länge 0).

Sei V = {1,...,n}. Definiere Boolesche Variable mi,jk wie folgt:

mi,jk = 1 wenn es Pfad von i nach j über Knoten aus

{1,...,k} gibt, 0 sonst.

Es gilt offensichtlich mi,j0 = 1 gdw. (i,j) in E oder i=j.

Außerdem:

mi,jk = mi,j

k-1 v (mi,kk-1 & mk,j

k-1)( i,j ) E* gdw mi,j

n = 1.

Idee: berechne Matrizen mi,jk für k = 0,1,...n.

Page 10: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II10

Sei A[i,j] Adjazenzmatrix. Algorithmus berechnet Adjazenzmatrix von G*.for ( k = 1; i = n ; i++) A[k,k] = 1;for ( k = 1; k = n ; k++) { for (i = 1; i = n; i++) { if (A[i,k]) { for (j = 1; j = n; j++) if ( A[k,j] ) A[i,j] = 1;

}}

}Fehler bei Schöning: Diagonale muß mit 1 vorbelegt sein (reflexive transitive Hülle enthält Kante ( i, i ) auch wennE ( i, i ) nicht enthält). Komplexität: Offensichtlich (n3)

Page 11: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II11

Läßt sich einfach modifizieren, um kürzeste Wege zwischen allen Knotenpaaren zu berechnen. Kanten erhalten Werte > 0, die "Länge, Kosten" der Kante repräsentieren. Werden in Matrix E gespeichert, ° in Matrix bedeutet "keine Kante". E[i,i] mit 0 vorbelegt.

for ( k = 1; k = n; k++) { for (i = 1; i = n; i++) { for (j = 1; j = n ; j++ )

{ if (E[i,k] + E[k,j] < E[i,j] ) E[i,j] = E[i,k] + E[k,j] ;

} }

}Algorithmus beruht auf

ei,jk = min( ei,j

k-1, ei,kk-1 + ek,j

k-1)

wobei ei,jk = die kürzeste Weglänge von i nach j mit

Zwischenknoten aus {1,...,k}.

Page 12: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II12

Beispiel: Kürzeste Wege von einem Knoten (Dijkstra-Algorithmus)

gegeben: kanten-bewerteter Graph G = (V,E) mitw: E -> R+, Kantengewichte

In folgendem Algorithmus ist:

W: Liste der noch zu behandelnden Knoten

F: Liste von Kanten, die auf kürzestem Weg von u zu anderen Knoten liegen

l(v): kürzeste bisher gefundene Weglänge von u nach v

k(v): optimale zu v führende Kante

Page 13: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II13

for (v in V )

{ if ((u,v) in E ) { l(v) = w((u,v)); k(v) = (u,v) ; } else l(v) = °; W = V; F = {}; l(u) = 0;for (i = 1; i= n ; i++) { (finde einen Knoten v in W mit l(v) minimal;) W = W - {v}; if (v u) F = F + k(v); for (alle Nachfolger v' von v mit v' in W ) if (l(v) + w((v,v')) < l(v') )

{ l(v') = l(v) + w((v,v')); k(v') = {v,v'};

} } }

Page 14: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II14

Beispiel: Kürzeste Wege von einem Knoten

w((1,2)) = 2w((2,3)) = 4w((2,4)) = 1w((3,2)) = 4w((4,3)) = 1alle anderen °u = 1W = {1,2,3,4}, gestrichen wird in der Reihenfolge 1, 2, 4, 3F = {(1,2), (2,4), (4,3)}

l[1]: °, 0, l[2]: 2l[3]: °, 6, 4l[4]: °, 3

k[1]: k[2]: (1,2)k[3]: (2,3),(4,3)k[4]: (2,4)

Page 15: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II15

Korrektheitsbeweis:

nach i Schleifendurchgängen sind die Längen von i Knoten, die am nächsten an u liegen, korrekt berechnet und diese Knoten sind aus W entfernt.

Induktionsanfang: u wird gewählt, l(u) = 0Induktionsschritt: Nimm an, v wird aus W genommen. Der kürzeste Pfad zu v gehe über Vorgänger v' von v. Da v' näher an u liegt, ist v' nach Induktionsvoraussetzung mit richtiger Länge bereits entfernt. Da der kürzeste Weg zu v die Länge l(v') + w((v',v)) hat und dieser Wert bei Entfernen von v' bereits v zugewiesen wurde, wird v mit der richtigen Länge entfernt.Schleife muß bis n gehen, sonst F unvollständig.

Komplexität: O(|V|2)

Page 16: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II16

Flüsse in Netzen: Ford-FulkersonAnwendungsprobleme:

Wieviele Autos können durch ein Straßennetz fahren? Wieviel Abwasser fasst ein Kanalnetz? Wieviel Strom kann durch ein Leitungsnetz fließen?

Probleme als Graphen repräsentieren:

Def.: Ein (Fluß-) Netzwerk ist ein gerichteter Graph G = (V,E) mit ausgezeichneten Knotenq (Quelle) und s (Senke), sowie einer Kapazitätsfunktion c : E -> Z+.

Ein (zulässiger) Fluss für das Netzwerk ist eine Funktion f: E -> Z, so daß gilt:Kapazitätsbeschränkung: f(e) c(e), für alle e in E.Flußerhaltung: für alle v in V\{q,s}:

(v',v) E f((v',v)) = (v,v') E f((v,v')) Der Wert von f, w(f), ist die Summe der Flußwerte der q verlassenden Kanten: (q,v) E f((q,v))

Page 17: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II17

Gesucht: Fluß mit maximalem WertDef.: Ein Schnitt (A,B) eines Fluß-Netzwerks ist eine

Zerlegung von V in disjunkte Teilmengen A und B, so dassq A und s B. Die Kapazität des Schnitts ist

c(A,B) = uA,vB c((u,v)).

Def.: Sei f ein zulässiger Fluß für G = (V,E). Sei E^ = {(v,w) | (v,w) E oder (w,v) E}Wir definieren die Restkapazität einer Kante e = (v,w) E^ wie folgt:

rest(e) = c(e) - f(e) falls e Ef((w,v)) falls (w,v) E

Der Restgraph von f (bzgl. G) besteht aus den Kanten e E^, für die rest(e) > 0 .Jede Kante e des Restgraphen ist mit rest(e) markiert.

Page 18: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II18

Jeder gerichtete Pfad von q nach s im Restgraphen heißt zunehmender Weg.

Beispiel:Kante Kapazität Fluß(q,v) 5 5(q,w) 5 3(v,w) 2 2(v,s) 5 3(w,s) 5 5

w(f) = 8, nicht maximalRestgraph:Kante Restkap(q,w) 2(w,v) 2(v,s) 2

Page 19: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II19

f kann so abgeändert werden:Kanten aus Restgraph, die in E sind, werden um 2 erhöht,Kanten, deren Umkehrungen in E sind, um 2 erniedrigt.

Kante Kapazität neuer Fluß(q,v) 5 5(q,w) 5 5(v,w) 2 0(v,s) 5 5(w,s) 5 5

Theorem (Min-Cut-Max-Flow-Theorem):Sei f zulässiger Fluß für G.

Folgende Aussagen sind äquivalent:

1) f ist maximaler Fluß in G.2) Der Restgraph von f enthält keinen zunehmenden Weg.3) w(f) = c(A,B) für einen Schnitt (A,B) von G.

Page 20: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II20

Daraus ergibt sich folgender Algorithmus:

for (alle e in E ) f(e) = 0;while ( es gibt zunehmenden Weg p im Restgraphen Gf ) { r = min{rest(e) | e liegt in p}; for (alle e = (v,w) auf Pfad p )

if (e in E)f(e)= f(e) + r ;

else f((w,v)) = f((w,v)) - r; }

Page 21: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II21

Beispiel:Kante Kapazität f0 f1 f2 f3(q,v) 5 0 4 4 5(q,w) 5 0 0 5 5(v,w) 2 0 0 0 1(v,s) 4 0 4 4 4(w,s) 6 0 0 5 6

1. Pfad: q,v,s2. Pfad: q,w,s3. Pfad: q,v,w,s

Laufzeit kann erheblich sein, schlimmstenfalls O(|f*| * |E|), wobei f* maximaler Fluß. Günstig ist, jeweils einen kürzesten Pfad (minimale Kantenzahl) von q nach s in Gf zu wählen.Edmonds und Karp haben gezeigt, daß die Komplexität dann O(|V| * |E|2 ) ist.

Page 22: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II22

Maximales MatchingBeispiel: Eine Gruppe von Erwachsenen und eine Gruppe von

Kindern besuchen Disneyland. Auf der Achterbahn darf ein Kind jeweils nur in Begleitung eines Erwachsenen fahren. Nur Erwachsene/Kinder, die sich kennen, sollen zusammen fahren. Wieviele Kinder können maximal eine Fahrt mitmachen?

Def.: Ein bipartiter Graph ist ein Graph, dessen Knotenmenge V in zwei disjunkte Teilmengen V1 und V2 aufgeteilt ist, und dessen Kanten jeweils einen Knoten aus V1 mit einem aus V2 verbinden.Ein Matching ist eine Teilmenge der Kanten, so daß jeder Knoten in V in höchstens einer Kante vorkommt. Ein Matching M ist maximal, wenn es kein Matching M' gibt mit |M| < |M'|.

Beispiel: Erwachsene bilden V1, Kinder V2, Kanten beschreiben, wer wen kennt.

Page 23: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II23

Maximales Matching kann auf maximalen Fluß zurückgeführt werden:

1) Quelle und Senke hinzufügen.2) Kanten von V1 nach V2 richten. 3) Jeder Knoten in V1 erhält eingehende Kante von der Quelle.4) Jeder Knoten in V2 erhält ausgehende Kante zur Senke.5) Alle Kanten erhalten Kapazität c(e) = 1.

Jetzt kann Ford-Fulkerson-Algorithmus angewendet werden.

Page 24: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II24

Aufspannende Bäume: Kruskal-Algorithmus

Ein weiteres Beispiel, wo Matroide in natürlicher Weise verwendet werden können, stammt aus dem Bereich der Graphentheorie.

Sei G = ( V, E ) ein gegebener ungerichteter, zusammenhängender Graph.

Einem solchen Graphen kann man ein Matroid zuordnen, das wir Graph-Matroid nennen, wie folgt:

Die Grundmenge ist die Menge aller Kanten E; und als Teilmengensystem U über E nehmen wir alle solche Kantenmengen, die keinen Kreis enthalten. Dieses Teilmengensystem ist tatsächlich ein Matroid, denn seien A und B zwei zyklenfreie Teilmengen von E mit |A| < |B|.

Page 25: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II25

Sowohl A als auch B zerlegen die zugrundeliegendeKnotenmenge V in disjunkte Knotenbereiche:

zwei Knoten gehören zum selben Bereich, wenn sie durch einen Weg in A (bzw. in B) miteinander verbunden sind.

Sei V = V1 V2 ... Vk die durch A induzierte Zerlegung.

Jede Kante in B verbindet entweder zwei Knoten im selben Bereich Vi oder in zwei verschiedenen Bereichen Vi und Vj.

In B können höchstens i (|Vi| - 1 ) = |A| viele Kanten vom ersten Typ vorkommen, da B zyklenfrei ist. Da |B| > |A| , muss es also mindestens eine Kante in B - A geben, die zwei verschiedene Bereiche verbindet. Eine solche Kante kann zu A hinzugefügt werden, ohne das ein Zyklus entsteht. Also haben wir es mit einem Matroid zu tun.

Page 26: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II26

Nächste Annahme, es sei eine Gewichtsfunktion w : E

gegeben, also eine Gewichtung der Kanten des zugrunde-liegenden Graphen.

Der kanonische Greedy-Algorithmus berechnet eine maximale Menge von Kanten mit maximalem Gewicht ( oder minimalem Gewicht - je nachdem, ob wir die Kanten absteigend oder aufsteigend anordnen). Da die Kantenmenge maximal ist, besteht diese nur noch aus einer Zusammenhangs-komponente, das heißt, das Ergebnis ist ein sogenannter aufspannender Baum des Graphen G. Also ein zusammenhängender Teilgraph, auf dem alle Knoten vorkommen, und der keinen Zyklus enthält.

Dieser Algorithmus (normalerweise in der Variante, dass ein aufspannender Baum mit minimalem Gewicht gefunden wird) heißt auch Kruskal-Algorithmus.

Page 27: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II27

Beispiel: Gegeben sei folgender kanten-bewerteter Graph:

5

6

8

3

4

6 6

5

24

75

2

3

Page 28: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II28

Der Kruskal-Algorithmus wählt nun- nach aufsteigenden Kantengewicht - Kante für Kante aus - solange diese Kante keinen Kreis schließt. Das Ergebnis ist folgender aufspannender Baum mit minimalem Kantengewicht, nämlich 2 + 2 + 3 + 3 + 4 + 5 + 5 = 24 (gestrichelt dargestellt).

5

6

8

3

4

6 6

5

24

75

2

3

Page 29: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II29

Sofern man nach absteigendem Kantengewicht die Kanten

5

6

8

3

4

6 6

5

24

75

2

3

auswählt, erhält man einen aufspannenden Baum mit maximalem Kantengewicht, nämlich

8 + 7 + 6 + 6 + 6 + 5 + 5 = 43 (wieder gestrichelt gezeichnet).

Page 30: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II30

Kürzeste Wege: Dijkstra-AlgorithmusGegeben sei wieder ein kanten-bewerteter Graph,

G = (V, E) und w : E + , wobei ein Knoten u V besonders ausgezeichnet ist.

Gesucht sind alle kürzesten Wege von u aus zu jedem beliebigem Knoten v V.

Der Algorithmus von Dijkstra löst dieses Problem wie folgt: Hierbei ist W eine Liste der noch zu sondierenden Knoten

(am Anfang ist W = V , am Ende ist W = 0 ) ;

F ist eine Auswahl an Kanten, welche die kürzesten Wege von u aus zu allen anderen Knoten ausmachen;

l (v) ist die kürzestmögliche Weglänge von u nach v und

k( v ) ist die optimale zu v führende Kante.

Page 31: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II31

Dijkstra-Algorithmus

for ( v V ) l (v) =w ( { u, v } ) , { u, v } E,

, sonst{ W = V ; F = 0 ; l (u) = 0 ; }

for ( i = 1 ; i = n - 1 ; i++ )

{ Finde einen Knoten v W mit l (v) minimal ;

W = W - { v } ;

if ( v u ) F = F { k (v) } ;

for ( alle Nachbarn v‘ von v W )

{ if ( l(v) + w ( { v, v‘ }) < l ( v‘ ) )

{ l ( v‘) = l (v) + w ( { v,v‘ }) ;

k ( v‘) = { v, v‘ } ;

} } }

Page 32: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II32

Beispielgraph (wie oben)

v

z

yxu

w

s t

5

6

8

3

4

6 6

5

24

75

2

3

u ist Startknoten

Page 33: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II33

Vom Startknoten u aus entwickelt der Dijkstra-Algorithmusdie folgenden (gestrichelten ) Pfade (dies sind die Kanten

in F).

Hierbei werden die Knoten in folgender Reihenfolge

aus W entfernt: u, x, v, w, y, s, z, t .

v

z

yxu

w

s t

5

6

8

3

4

6 6

5

24

75

2

3

Page 34: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II34

Diese Pfade bilden wieder einen aufspannenden Baum, der allerdings nicht minimales Gewicht hat; was stattdessen minimiert wird, sind die Wegstrecken von u aus gesehen.

Was die Komplexität des Dijkstra-Algorithmus bestrifft, so sieht man, dass eine äußere Schleife durchlaufen werden muss; diese liefert den Faktor O(|V|).

Im Inneren dieser Schleife ist aber eine weitere, die für das Auffinden des Minimums zuständig ist.

( Komplexität O(|V|)).

Das Aufsuchen aller Nachbarn von v kann mit O(|V|) abgeschätzt werden.

Daher ist die Komplexität des Dijkstra-Algorithmus beschränkt durch O(|V|2).

Page 35: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II35

Die Korrektheit des Dijkstra-Algorithmus‘ kann man sichdurch Aufzeigen der entsprechenden Matroid-Struktur klarmachen, und somit auf die Korrektheit des kanonischen Greedy-Algorithmus‘ für Matroide zurückführen. Man wählt dieses Mal als Grundmenge die Menge aller zyklenfreien Pfade vom Startknoten u aus.

Das Teilmengensystem U über dieser Grundmenge besteht aus allen solchen Pfadmengen, die auf verschiedene Endknoten führen.

Man sieht leicht ein, dass diese Struktur ein Matroid ist, denn wenn A und B Pfadmengen aus U sind mit |A < |B| , dann gibt es in A genau |A| verschiedene Endknoten und in B befindet sich mindestens ein Pfad mit einem weiteren Endknoten, der in A nicht vorkommt.

Daher kann A um diesen Pfad erweitert werden.

Page 36: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II36

Notwendig ist noch eine geeignete Gewichtsfunktion w‘auf der Grundmenge, also auf den von u ausgehenden Pfaden.

Sei p ein solcher Pfad.

Dann setzen wir w‘( p ) = w( k )k liegt auf p

Man überzeugt sich leicht, dass der kanonische Greedy-Algorithmus für dieses Matroid und diese Gewichtsfunktion w‘ im Ablauf und im erzeugten Ergebnis exakt mit dem Dijkstra-Algorithmus übereinstimmt.

Der Dijkstra-Algorithmus ist nur effizienter formuliert; man muss nicht alle zyklenfreien Pfade, die von u ausgehen, erzeugen und nach aufsteigenden w‘-Werten sortieren, wie dies beim kanonischen Greedy-Algorithmus vorgesehen ist.

Page 37: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II37

Im Beispiel oben wählt der kanonische Greedy-Algorithmus

der Reihe nach folgende Pfade:

Pfad p w‘(p)

u 0

u -- x 2

u -- v 3

u -- x -- w 5

u -- x -- y 7

u -- x -- s 7

u -- z 8

u -- x -- s -- t 9

Page 38: G.Heyer Algorithmen und Datenstrukturen II 1 Graphalgorithmen ( elementare A. ) Graphen sind zur Repräsentation von Problemen vielseitig verwendbar, etwa

G.Heyer Algorithmen und Datenstrukturen II38

Nachbemerkung:Zum Schluss kann man noch anmerken, dass man den Dijkstra-Algorithmus durchaus auch als einen einfachen dynamischen-Programmier-Algorithmus ansehen kann, denn es wird die zunächst leere ( eindimensionale) Tabelle

der l-Werte aufgebaut, die die kürzesten Weglängen angibt.

In jedem Erweiterungsschritt wird auf die bereits berechneten l-Werte zurückgegriffen.

Es gilt auch das Bellmannsche Optimierungsprinzip:

Die kürzeste Wegstrecke von u nach v erhält man, indem man denjenigen Vorgänger v‘ von v auswählt, der den

Wert l (v‘) + w ({ v‘ , v }) minimiert. Dieses Vorgehen entspricht also dem dynamischen Programmier-Paradigma.