Algorithmen und Datenstrukturen

[Link]. Marc Fischlin, SS 2023

06
Graph Algorithms

13. Oktober 2010 | [Link] Fischlin | Kryptosicherheit | 1

 Graphen

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 2

(Endliche) Gerichtete Graphen Ein (endlicher) gerichteter
Graph 𝑮 = (𝑽, 𝑬) besteht aus
Zyklen wie
1 15642 1 (1) einer (endlichen)
möglich
KnotenmengeO 𝑉 („vertices“)
Schleife
(2) einer (endlichen)
2 5
Kantenmenge& 𝐸 ⊆𝑉×𝑉
(„edges“)

(𝑢, 𝑣) ∈ 𝐸: Kante von Knoten 𝑢 zu 𝑣

3 4 6
(keine Mehrfachkanten
isolierter zwischen Knoten)
Knoten *
im Unterschied zu Bäumen
𝑉 = {1,2,3,4,5,6} -
Anordnung der Knoten
𝐸 = { 1,4 , 1,5 , 2,1 , 2,2 , 4,2 , 5,6 , 6,4 } in der Darstellung-
irrelevant
-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 3

Ungerichtete Graphen Ein (endlicher)
ungerichteter Graph 𝑮 =
(𝑽, 𝑬) besteht aus
1
(1) einer (endlichen)
Knotenmenge 𝑉
(„vertices“)
2 5
(2) einer (endlichen)
Kantenmenge 𝐸 ⊆ 𝑉 × 𝑉
(„edges“), so dass
3 4 6 𝒖, 𝒗 ∈ 𝑬 ⟺ 𝒗, 𝒖 ∈ 𝑬

Alternative Darstellung:
𝑢, 𝑣
𝑉 = {1,2,3,4,5,6} statt statt
𝐸 = { 1,4 , 1,5 , 1,2 , 2,2 , 2,4 , 4,6 , {5,6}} 𝑢, 𝑣 , (𝑣, 𝑢)

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 4

Pfadfinder Knoten 𝑣 ist von Knoten 𝑢
im Graphen 𝐺 = (𝑉, 𝐸) erreichbar,
wenn es Pfad (𝑤 , … , 𝑤 ) ∈ 𝑉 gibt,
1
so dass (𝑤 , 𝑤 ) ∈ 𝐸 für 𝑖 = 1, 2, … , 𝑘 − 1
und 𝑤 = 𝑢 und 𝑤 = 𝑣.

Insbesondere ist 𝑢 immer von 𝑢

2 5 per „leerem Pfad“ (𝑘 = 1) erreichbar.

O
Länge des Pfades = 𝑘 − 1 = Anzahl Kanten
3 4 6

(𝑤 , … , 𝑤 ) ist ein kürzester Pfad von 𝑢 nach 𝑣,

wenn es keinen kürzeren Pfad gibt.

𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑢, 𝑣) = Länge eines kürzesten Pfades von 𝑢 nach 𝑣

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 5
Zusammenhänge
zusammenhängend
1
Ungerichteter Graph
ist zusammenhängend,
2 5
wenn jeder Knoten von jedem
anderen Knoten aus erreichbar ist

4 6

Gerichteter Graph
1 ist stark zusammenhängend,
wenn jeder Knoten von jedem
2 5 anderen Knoten aus
(gemäß Kantenrichtung)
erreichbar ist
nicht stark
4 6 zusammenhängend,
da kein Pfad 51

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 6

Graphen und Bäume Achtung: Diese (Graphen-)Bäume
haben keine Ordnung auf den Kindern!
-

1 1

2 5 5 2

als (Graphen-)Bäume
=

3 4 6 4 6 3

Graph 𝐺 = 𝑉, 𝐸 ist ein Baum, wenn O 𝑉 leer ist oder

es einen Knoten r ∈ 𝑽 („Wurzel“) gibt, so dass jeder Knoten Ov von der
Wurzel aus per eindeutigem Pfad erreichbar ist.

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 7

Subgraphen Beachte: 𝐺‘ muss selbst wieder ein Graph
des gleichen Typs (gerichtet oder ungerichtet) sein!

1 1

2 5 2 5

3 4 6 3 4 6

(Gerichteter oder ungerichteter) Graph 𝐺′ = (𝑉′, 𝐸′) ist Subgraph

(oder Untergraph oder Teilgraph)
des (gerichteten oder ungerichteten) Graphen 𝐺 = (𝑉, 𝐸),
wenn 𝑉′ ⊆ 𝑉 und E′ ⊆ 𝐸.
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 8
Darstellung von Graphen (I)
Als Adjazenzmatrix:
1 wenn Kante von i zu j
1
𝐴 𝑖, 𝑗 = { 0 wenn keine Kante
1 23ry 6

0 0 0 1 1 0
I 1 1 0 0 0 0
2 5

i
𝐴= 0 0 0 0 0 0
0 1 0 0 0 0
0 0 0 0 0 1
6 0 0 0 1 0 0
3 4 6
bei ungerichteten Graphen ist
Matrix (spiegel-)symmetrisch
zur Hauptdiagonalen

𝑉 = {1,2,3,4,5,6}
𝐸 = { 1,4 , 1,5 , 2,1 , 2,2 , 4,2 , 5,6 , 6,4 } Speicherbedarf = Θ(|𝑉| )

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 9

Matrix  Eigenschaft (I)
( )
Der Eintrag 𝑎 , in der 𝑖-ten Zeile und 𝑗-ten Spalte der 𝑚-ten Potenz 𝐴
der Adjazenzmatrix 𝐴 eines Graphen gibt die Anzahl der Wege an,
die von Knoten 𝑖 zu Knoten 𝑗 entlang von genau 𝑚 Kanten führen (𝑚 ≥ 0).

Per Induktion (Basisfall 𝑚 = 0):

1 0 0 0 0 0 Nur für 𝑖 = 𝑗 gibt es „den“

-

0 1 0 0 0 0 Weg von Knoten 𝑖 zu Knoten 𝑗

-

0 0 1 0 0 0 mit genau 0 Kanten

𝐴 =𝐼= -

0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 10

Matrix  Eigenschaft (II)
( )
Der Eintrag 𝑎 , in der 𝑖-ten Zeile und 𝑗-ten Spalte der 𝑚-ten Potenz 𝐴
der Adjazenzmatrix 𝐴 eines Graphen gibt die Anzahl der Wege an,
die von Knoten 𝑖 zu Knoten 𝑗 entlang von genau 𝑚 Kanten führen (𝑚 ≥ 0).

Per Induktion (Schritt 𝑚 → 𝑚 + 1):

Jeder Weg mit 𝑚 + 1 Kanten von 𝑖 zu 𝑗 führt

𝑚 Kanten entlang 𝑚 Kanten zu einem Knoten 𝑘
v
und dann mit einer Kante weiter zu 𝑗

i v j

v 1 Kante

Dies sind auch alle Wege der Länge 𝑚 + 1

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 11
Matrix  Eigenschaft (III)
( )
Der Eintrag 𝑎 , in der 𝑖-ten Zeile und 𝑗-ten Spalte der 𝑚-ten Potenz 𝐴
der Adjazenzmatrix 𝐴 eines Graphen gibt die Anzahl der Wege an,
die von Knoten 𝑖 zu Knoten 𝑗 entlang von genau 𝑚 Kanten führen (𝑚 ≥ 0).

Per Induktion (Schritt 𝑚 → 𝑚 + 1):

( ) ( )
𝑖-te Zeile, 𝑗-te Spalte von 𝐴 : 𝑎, = 𝑎, 𝑎 ,

𝐴 = 𝐴 𝐴
𝑎 ,
𝑎 ,
( ) ( ) ( )
𝑎, 𝑎, … 𝑎,
=
⋮

𝑎 ,

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 12

Matrix  Eigenschaft (IV)
( )
Der Eintrag 𝑎 , in der 𝑖-ten Zeile und 𝑗-ten Spalte der 𝑚-ten Potenz 𝐴
der Adjazenzmatrix 𝐴 eines Graphen gibt die Anzahl der Wege an,
die von Knoten 𝑖 zu Knoten 𝑗 entlang von genau 𝑚 Kanten führen (𝑚 ≥ 0).

Per Induktion (Schritt 𝑚 → 𝑚 + 1):

( ) ( )
𝑖-te Zeile, 𝑗-te Spalte von 𝐴 : 𝑎, = 𝑎, 𝑎 ,

Anzahl der Wege von 𝑖 nach 𝑘

entlang 𝑚 Kanten (Induktionsvoraussetzung)

1, wenn es eine Kante von 𝑘 zu 𝑗 gibt, 0 sonst

Eintrag beschreibt genau Anzahl der Wege

von 𝑖 über alle 𝑘 mit jeweils 𝑚 Kanten und einer Kante von 𝑘 zu 𝑗
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 13
Darstellung von Graphen (II)
Adjazenzliste:
Als Array mit verketteten Listen
1 (sortiert oder unsortiert)

1 4 5
2 1 2
2 5
3

4 2
5 6
3 4 6 6 4

Speicherbedarf = Θ( 𝑉 + |𝐸|)
𝑉 = {1,2,3,4,5,6}
𝐸 = { 1,4 , 1,5 , 2,1 , 2,2 , 4,2 , 5,6 , 6,4 }

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 14

Gewichtete Graphen Ein gewichteter gerichteter
-

Graph 𝑮 = (𝑽, 𝑬) besitzt

-

zusätzlich Funktion
1
w 1,2 =5 𝑤 1,5 = −3 𝑤: 𝐸 → ℝ

Bei gewichteten ungerichteten

2 5 Graphen gilt zusätzlich
−1 𝑤 𝑢, 𝑣 = 𝑤 𝑣, 𝑢
2.9
17 13.2 für alle 𝑢, 𝑣 ∈ 𝐸.
3
3 4 6

Beispiel:
Knoten = Städte Speicher zusätzlich zu Kante
Kanten = Zugverbindungen (𝑢, 𝑣) auch Wert 𝑤((𝑢, 𝑣))
Gewicht = Entfernung
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 15
 Für die Adjazenzmatrix 𝐴 eines Graphen beschreibt
der Eintrag 𝑖, 𝑗 in 𝐴 = 𝐴 𝐴 ⋯ 𝐴 die Anzahl der Wege
mit 𝑛 Kanten von Knoten 𝑖 nach 𝑗 im Graphen.

Wie können Sie feststellen, ob es in einem (gerichteten)

Graphen einen Weg von einem Knoten 𝑢 zu einem
Knoten 𝑣 gibt?

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 16

 Breadth-First Search (BFS)
&
Breite Zuerst suchen

kürzesten
Weg
in
den

ungewichteten Graph finden

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 17

Idee
Besuche zuerst alle unmittelbaren Nachbarn, dann deren Nachbarn usw.
-

2 3
2 2
2
2
2 1 2
2

0
2 2
2
2

2
2
2 2

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 18

Anwendungen
Besuche zuerst alle unmittelbaren Nachbarn, dann deren Nachbarn usw.

2 3
2 2
2
Web Crawling
2
2 1 Kontakte in OSN
2
2
Broadcasting
0
2 2
2
2 Garbage Collection

…
2
2
2 2

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 19

 dist =Distanz von s
BFS: Algorithmus pred =Vorgängerknoten
BFS(G,s) //G=(V,E), s=source node in V

1 FOREACH u in V–{s} DO
2 [Link]=WHITE; &
[Link]=+∞; [Link]=NIL;
3 [Link]=GRAY; [Link]=0; [Link]=NIL;
4 newQueue(Q);
WHITE =Knoten noch nicht besucht
5 enqueue(Q,s);
GRAY=in Queue für nächsten Schritt
6 WHILE !isEmpty(Q) DO BLACK =fertig
-

7 u=dequeue(Q); -

8 FOREACH v in adj(G,u) DO
9 IF [Link]==WHITE THEN
10 [Link]=GRAY; [Link]=[Link]+1; [Link]=u;
11 enqueue(Q,v);
12 [Link]=BLACK;

adj(G,u) = Liste aller Knoten 𝑣 ∈ 𝑉 mit (𝑢, 𝑣) ∈ 𝐸

(Reihenfolge irrelevant)
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 20
BFS: Algorithmus (Beispiel I)
BFS(G,s) //G=(V,E), s=source node in V
…
6 WHILE !isEmpty(Q) DO
7 u=dequeue(Q);
#1211(
8 FOREACH v in adj(G,u) DO
9 IF [Link]==WHITE THEN
10 [Link]=GRAY; [Link]=[Link]+1; [Link]=u;
11 enqueue(Q,v);
12 [Link]=BLACK;
0/NIL

O
s=1 Q=(1) Q=(4 5)
1 1 1/1
7-12

↓
2 5 2 5
+∞/NIL

3 4 6 3 4 6

+∞/NIL 1/1
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 21
BFS: Algorithmus (Beispiel II)
BFS(G,s) //G=(V,E), s=source node in V
…
6 WHILE !isEmpty(Q) DO
7 u=dequeue(Q);
#12161
(
8 FOREACH v in adj(G,u) DO
9 IF [Link]==WHITE THEN
10 [Link]=GRAY; [Link]=[Link]+1; [Link]=u;
11 enqueue(Q,v);
12 [Link]=BLACK;
Q=(4 5) Q=(5 2)
+∞/NIL 1 2/4 1
7-12
2 5 2 5
1/1 1/1

3 4 6 3 4 6

1/1 1/1
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 22
 BFS >
-

Stecks

BFS: Algorithmus (Beispiel III) K quewes

BFS(G,s) //G=(V,E), s=source node in V

***
…
6 WHILE !isEmpty(Q) DO ) (
7 u=dequeue(Q);
- -

8 FOREACH v in adj(G,u) DO
9 IF [Link]==WHITE THEN
10 [Link]=GRAY; [Link]=[Link]+1; [Link]=u;
11 enqueue(Q,v);
12 [Link]=BLACK;
Q=(5 2) Q=(2 6)
2/4 1 2/4 1
7-12
2 5 2 5
1/1 1/1

3 4 6 3 4 -O6

1/1 +∞/NIL 1/1 2/5

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 23

BFS: Algorithmus (Beispiel IV)
BFS(G,s) //G=(V,E), s=source node in V
…
6 WHILE !isEmpty(Q) DO
7 u=dequeue(Q);
8 FOREACH v in adj(G,u) DO
9 IF [Link]==WHITE THEN
10 [Link]=GRAY; [Link]=[Link]+1; [Link]=u;
11 enqueue(Q,v);
12 [Link]=BLACK;
0/NIL
Q=(2 6) Q=()
2/4 1 2/4 1
7-12
2 5 2 5
1/1 1/1

O
2x
3 4 6 3 4 6

1/1 2/5 +∞/NIL 1/1 2/5

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 24

 wer st case

BFS: Algorithmus - Laufzeit Laufzeit = 𝑂(|𝑉| + |𝐸|)

BFS(G,s) //G=(V,E), s=source node in V
Schleife mit 𝑂(|𝑉|) vielen Iterationen
1 FOREACH u in V–{s} DO
2 [Link]=WHITE; [Link]=+∞; [Link]=NIL;
3 [Link]=GRAY; [Link]=0; [Link]=NIL;
4 newQueue(Q);
5 enqueue(Q,s); Jeder Knoten wird maximal einmal
6 WHILE !isEmpty(Q) DO in Q aufgenommen (s oder WHITE)
7 u=dequeue(Q); (bzw. gar nicht, wenn nicht erreichbar)

8 FOREACH v in adj(G,u) DO
9 IF [Link]==WHITE THEN
10 [Link]=GRAY; [Link]=[Link]+1; [Link]=u;
11 enqueue(Q,v);
12 [Link]=BLACK;

Insgesamt werden maximal ∑ ∈ O

|𝑎𝑑𝑗(𝐺, 𝑢) | = 𝑂( 𝐸 ) Kanten betrachtet

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 25

Korrektheit (I) Teil 1: dist=Länge des kürzesten Pfades
Teil 2: Pfad kann abgelesen werden

Sei 𝐺 = (𝑉, 𝐸) gerichteter oder ungerichteter Graph mit

Knoten s ∈ 𝑉. Dann gilt nach Terminierung von BFS(G,s)
für jeden von s aus erreichbaren Knoten v, dass
𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(s,v) =[Link].
Für v≠s ist ein kürzester Pfad durch einen kürzesten Pfad
von s nach [Link] und der Kante ([Link],v) gegeben.
1 2 3
Intuition für Korrektheit dist:
s
s
Im ersten Schritt werden genau die
s s
Knoten besucht, die von s aus über
s eine Kante erreicht werden können;
s diese Knoten erhalten dist=1

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 26

Korrektheit (II)

Sei 𝐺 = (𝑉, 𝐸) gerichteter oder ungerichteter Graph mit

Knoten s ∈ 𝑉. Dann gilt nach Terminierung von BFS(G,s)
für jeden von s aus erreichbaren Knoten v, dass
𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(s,v) =[Link].
Für v≠s ist ein kürzester Pfad durch einen kürzesten Pfad
von s nach [Link] und der Kante ([Link],v) gegeben.
1 2 3
Intuition für Korrektheit dist:
s
s
Im zweiten Schritt werden nur die
s s
Knoten besucht die in zwei oder mehr
s
Schritten von s aus erreichbar sind;
s diese erhalten dist=2 usw.

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 27

Korrektheit (III)

Sei 𝐺 = (𝑉, 𝐸) gerichteter oder ungerichteter Graph mit

Knoten s ∈ 𝑉. Dann gilt nach Terminierung von BFS(G,s)
für jeden von s aus erreichbaren Knoten v, dass
𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(s,v) =[Link].
Für v≠s ist ein kürzester Pfad durch einen kürzesten Pfad
von s nach [Link] und der Kante ([Link],v) gegeben.

Korrektheit kürzester Pfad:

Für u=[Link] ist, da v von u aus per Kante (u,v) ∈ 𝐸 besucht wurde,
der Pfad von s nach u und dann zu v ein Pfad der Länge

1 + sℎ𝑜𝑟𝑡𝑒𝑠𝑡 s,u = 1 + [Link] = [Link] = sℎ𝑜𝑟𝑡𝑒𝑠𝑡 s,v

gemäß gemäß gemäß
Teil 1 Algorithmus Teil 1
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 28
Kürzeste Pfade ausgeben Laufzeit* = 𝑂 𝑉
*ohne BFS
PRINT-PATH(G,s,v)
//assumes that BFS(G,s) has already been executed

1 IF v==s THEN
2 PRINT s
3 ELSE
4 IF [Link]==NIL THEN
5 PRINT ‘no path from s to v‘
6 ELSE
7 PRINT-PATH(G,s,[Link]);
8 PRINT v;

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 29

Abgeleiteter BFS-Baum (I) 𝐬
𝐺𝐩𝐫𝐞𝐝

E
0/NIL 1
2/4 1

2 5 5
4
1/1

3 4 6
2 6
+∞/NIL 1/1 2/5

𝐬 𝐬 𝐬
Definiere Subgraph 𝐺𝐩𝐫𝐞𝐝 = (𝑉𝐩𝐫𝐞𝐝 , 𝐸𝐩𝐫𝐞𝐝 ) von 𝐺 durch:
𝐬
𝑉𝐩𝐫𝐞𝐝 = v ∈ 𝑉 [Link] ≠ NIL} ∪ {s}
𝐬 𝐬
𝐸𝐩𝐫𝐞𝐝 = [Link],v v ∈ 𝑉𝐩𝐫𝐞𝐝 − s }
(und v,[Link] für ungerichtete Graphen)

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 30

Abgeleiteter BFS-Baum (II) 𝐬
𝐺𝐩𝐫𝐞𝐝
0/NIL 1
2/4 1

2 5 5
4
1/1

3 4 6
2 6
+∞/NIL 1/1 2/5

𝐬 𝐬 𝐬
Definiere
𝐬 Subgraph
𝐺𝐩𝐫𝐞𝐝 ist BFS-Baum zu 𝐺 𝐩𝐫𝐞𝐝
𝐺, = (𝑉𝐩𝐫𝐞𝐝 𝐩𝐫𝐞𝐝 ) von 𝐺 durch:
, 𝐸
d.h. enthält𝐬 alle von s aus erreichbaren Knoten in 𝐺 und
𝑉𝐩𝐫𝐞𝐝 = v ∈ 𝑉𝐬 [Link] ≠ NIL} ∪ {s}
für jeden𝐸Knoten
𝐬
= ∈ 𝑉𝐩𝐫𝐞𝐝 existiert
[Link],v v ∈genau
𝑉 𝐬 einsPfad
− } von s
𝐬 𝐩𝐫𝐞𝐝 𝐩𝐫𝐞𝐝
in 𝐺𝐩𝐫𝐞𝐝 , der auch ein kürzester Pfad von s zu v in 𝐺 ist.
(und v,[Link] für ungerichtete Graphen)

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 31

 Überlegen Sie sich, wie Sie mittels BFS in einem Labyrinth der
-

folgenden Form den kürzesten Weg von Start (S) zu Ziel (Z) -

finden können. Welche Laufzeit hat Ihr Verfahren?

-
0

T Z

- & S

↓
↓

Hinweis: Sie sind selbst nicht im Labyrinth, sondern „schauen von oben darauf“
-
-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 32

 Depth-First Search (DFS)

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 33

Idee Besuche zuerst alle noch nicht besuchten Nachfolgeknoten
-

(„Laufe so weit wie möglich weg von aktuellem Knoten“)

-

2
2
2
2 1
2
2
2 3
2
s
2 2
2 Anfang 2

2
2 usw.
2 2

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 34

 Laufzeit = 𝑂(|𝑉| + |𝐸|)
DFS: Algorithmus
DFS(G) //G=(V,E)

1 FOREACH 0
u in V DO
time globale Variable =

2 [Link]=WHITE;
3 [Link]=NIL;
4 time=0;
DFS-VISIT(G,u) 5 FOREACH u in V DO
6 IF [Link]==WHITE THEN
1 time=time+1; 7 DFS-VISIT(G,u)
2 [Link]=time;
3 [Link]=GRAY;
4 FOREACH v in adj(G,u) DO
5 IF [Link]==WHITE THEN
6 [Link]=u;
disc = discovery time
7 DFS-VISIT(G,v);
finish=finish time
8 [Link]=BLACK;
9 time=time+1;
10 [Link]=time;
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 35
DFS: Beispiel (I) -
Ordnung auf Knotenlisten gemäß Knotennummern

DFS(G) //G=(V,E)
Aufrufs-Stack: DFS-VISIT(G,1)
-


1 FOREACH u in V DO
2 [Link]=WHITE;
3 [Link]=NIL;
4 time=0;
O
DFS-VISIT(G,u) time=0
5
6
gebrate
FOREACH u in V DO Y
IF T
[Link]==WHITE THEN
1 time=time+1; 7 -DFS-VISIT(G,u)
-
2 * [Link]=time;
−/−/NIL
3 [Link]=GRAY; ↓ -

−/−/NIL
4 FOREACH O & DO
v in adj(G,u) −/−/NIL -1

D
⑨
5 IF [Link]==WHITE THEN
2 5
6 ⑧
[Link]=u; 8

7 & DFS-VISIT(G,v);
8 [Link]=BLACK; 3 6
4
9 time=time+1;
10 [Link]=time; −/−/NIL −/−/NIL −/−/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 36

 Ordnung auf Knotenlisten gemäß Knotennummern
DFS: Beispiel (II)
DFS(G) //G=(V,E)

T
Aufrufs-Stack: DFS-VISIT(G,1)
 DFS-VISIT(G,4)
1 FOREACH u in V DO
2 [Link]=WHITE;
3 [Link]=NIL;
4 time=0;
DFS-VISIT(G,u) time=0
time=1
5 FOREACH u in V DO
6 IF [Link]==WHITE THEN
1 time=time+1; 7 DFS-VISIT(G,u)
2 [Link]=time;
−/−/NIL
1/−/NIL
3 [Link]=GRAY;
1 −/−/NIL
4 FOREACH v in adj(G,u) DO −/−/NIL

5 IF [Link]==WHITE THEN
2 5
6 [Link]=u;
7 DFS-VISIT(G,v);
8 [Link]=BLACK; 3 6
4
9 time=time+1;
10 [Link]=time; −/−/NIL −/−/NIL
−/−/1 −/−/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 37

 Ordnung auf Knotenlisten gemäß Knotennummern
DFS: Beispiel (II)
DFS(G) //G=(V,E)

⑳
Aufrufs-Stack: DFS-VISIT(G,1)
 DFS-VISIT(G,4)
DFS-VISIT(G,2)
1 FOREACH u in V DO
2 [Link]=WHITE;
3 [Link]=NIL;
4 time=0;
DFS-VISIT(G,u) time=1
time=2 5 FOREACH u in V DO
6 IF [Link]==WHITE THEN
1 time=time+1; 7 DFS-VISIT(G,u)
2 [Link]=time;
−/−/NIL
1/−/NIL
3 [Link]=GRAY;
1 −/−/NIL
4 FOREACH v in adj(G,u) DO
8 −/−/NIL
−/−/4

5 IF [Link]==WHITE THEN
2 5
6 [Link]=u;
7 & DFS-VISIT(G,v);

8 ⑤ [Link]=BLACK;
*
- 3 4 6
9 time=time+1; 7
⑧ -

10 ⑧[Link]=time; −/−/NIL −/−/NIL

−/−/1
2/−/1 −/−/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 38

 Ordnung auf Knotenlisten gemäß Knotennummern
DFS: Beispiel (III)
DFS(G) //G=(V,E)
Aufrufs-Stack: DFS-VISIT(G,1)
 DFS-VISIT(G,4)
DFS-VISIT(G,2)
1 FOREACH u in V DO
2 [Link]=WHITE;
3 [Link]=NIL;
4 time=0;
DFS-VISIT(G,u) time=2
time=3
5 FOREACH u in V DO
6 IF [Link]==WHITE THEN
1 time=time+1; 7 DFS-VISIT(G,u)
2 [Link]=time;
−/−/NIL
1/−/NIL
3 [Link]=GRAY;
3/−/4 1 −/−/NIL
4 FOREACH v in adj(G,u) DO −/−/NIL
−/−/4

5 IF [Link]==WHITE THEN
2 5
6 [Link]=u;
7 DFS-VISIT(G,v);
8 [Link]=BLACK; 3 6
4
9 time=time+1;
10 [Link]=time; −/−/NIL −/−/NIL
−/−/1
2/−/1 −/−/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 39

 Ordnung auf Knotenlisten gemäß Knotennummern
DFS: Beispiel (IV)
DFS(G) //G=(V,E)
Aufrufs-Stack: DFS-VISIT(G,1)
 DFS-VISIT(G,4)
DFS-VISIT(G,2)
1 FOREACH u in V DO
2 [Link]=WHITE;
3 [Link]=NIL;
4 time=0;
DFS-VISIT(G,u) time=3
time=4 5 FOREACH u in V DO
6 IF [Link]==WHITE THEN
1 time=time+1; 7 DFS-VISIT(G,u)
2 [Link]=time;
−/−/NIL
1/−/NIL
3 [Link]=GRAY;
3/−/4
3/4/4 1 −/−/NIL
4 FOREACH v in adj(G,u) DO −/−/NIL
−/−/4

5 IF [Link]==WHITE THEN
2 5
6 [Link]=u;
7 DFS-VISIT(G,v);
8 [Link]=BLACK; 3 6
4
9 time=time+1;
10 [Link]=time; −/−/NIL −/−/NIL
−/−/1
2/−/1 −/−/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 40

 Ordnung auf Knotenlisten gemäß Knotennummern
DFS: Beispiel (V)
DFS(G) //G=(V,E)
Aufrufs-Stack: DFS-VISIT(G,1)
 DFS-VISIT(G,4)
DFS-VISIT(G,5)
1 FOREACH u in V DO
2 [Link]=WHITE;
3 [Link]=NIL;
4 time=0;
DFS-VISIT(G,u) time=3
time=4 5 FOREACH u in V DO
6 IF [Link]==WHITE THEN
1 time=time+1; 7 DFS-VISIT(G,u)
2 [Link]=time;
−/−/NIL
1/−/NIL
3 [Link]=GRAY;
3/−/4
3/4/4 1 −/−/4
−/−/NIL
4 FOREACH v in adj(G,u) DO −/−/NIL
−/−/4

5 IF [Link]==WHITE THEN
2 5
6 [Link]=u;
7 DFS-VISIT(G,v);
8 [Link]=BLACK; 3 6
4
9 time=time+1;
10 [Link]=time; −/−/NIL −/−/NIL
−/−/1
2/−/1 −/−/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 41

 Ordnung auf Knotenlisten gemäß Knotennummern
DFS: Beispiel (VI)
DFS(G) //G=(V,E)
Aufrufs-Stack: DFS-VISIT(G,1)
 DFS-VISIT(G,4)
DFS-VISIT(G,5)
1 FOREACH u in V DO
DFS-VISIT(G,6) 2 [Link]=WHITE;
3 [Link]=NIL;
4 time=0;
DFS-VISIT(G,u) time=4
time=5 5 FOREACH u in V DO
6 IF [Link]==WHITE THEN
1 time=time+1; 7 DFS-VISIT(G,u)
2 [Link]=time;
−/−/NIL
1/−/NIL
3 [Link]=GRAY;
5/−/4
−/−/4
−/−/NIL
4 FOREACH v in adj(G,u) DO 3/−/4
3/4/4
−/−/NIL
−/−/4 1
5 IF [Link]==WHITE THEN
2 5
6 [Link]=u;
7 DFS-VISIT(G,v);
8 [Link]=BLACK; 3 6
4
9 time=time+1;
10 [Link]=time; −/−/NIL −/−/NIL
−/−/1
2/−/1 −/−/NIL
−/−/5

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 42

 Ordnung auf Knotenlisten gemäß Knotennummern
DFS: Beispiel (VII)
DFS(G) //G=(V,E)
Aufrufs-Stack: DFS-VISIT(G,1)
 DFS-VISIT(G,4)
DFS-VISIT(G,5)
1 FOREACH u in V DO
DFS-VISIT(G,6) 2 [Link]=WHITE;
3 [Link]=NIL;
4 time=0;
DFS-VISIT(G,u) time=5
time=6 5 FOREACH u in V DO
6 IF [Link]==WHITE THEN
1 time=time+1; 7 DFS-VISIT(G,u)
2 [Link]=time;
−/−/NIL
1/−/NIL
3 [Link]=GRAY;
5/−/4
−/−/4
−/−/NIL
4 FOREACH v in adj(G,u) DO 3/−/4
3/4/4
−/−/NIL
−/−/4 1
5 IF [Link]==WHITE THEN
2 5
6 [Link]=u;
7 DFS-VISIT(G,v);
8 [Link]=BLACK; 3 6
4
9 time=time+1;
10 [Link]=time; −/−/NIL −/−/NIL
−/−/1
2/−/1 −/−/NIL
−/−/5
6/−/5

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 43

 Ordnung auf Knotenlisten gemäß Knotennummern
DFS: Beispiel (VIII)
DFS(G) //G=(V,E)
Aufrufs-Stack: DFS-VISIT(G,1)
 DFS-VISIT(G,4)
DFS-VISIT(G,5)
1 FOREACH u in V DO
DFS-VISIT(G,6) 2 [Link]=WHITE;
3 [Link]=NIL;
4 time=0;
DFS-VISIT(G,u) time=6
time=7 5 FOREACH u in V DO
6 IF [Link]==WHITE THEN
1 time=time+1; 7 DFS-VISIT(G,u)
2 [Link]=time;
−/−/NIL
1/−/NIL
3 [Link]=GRAY;
5/−/4
−/−/4
−/−/NIL
4 FOREACH v in adj(G,u) DO 3/−/4
3/4/4
−/−/NIL
−/−/4 1
5 IF [Link]==WHITE THEN
2 5
6 [Link]=u;
7 DFS-VISIT(G,v);
8 [Link]=BLACK; 3 6
4
9 time=time+1;
10 [Link]=time; −/−/NIL −/−/NIL
−/−/1
2/−/1 −/−/NIL
−/−/5
6/−/5
6/7/5

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 44

 Ordnung auf Knotenlisten gemäß Knotennummern
DFS: Beispiel (IX)
DFS(G) //G=(V,E)
Aufrufs-Stack: DFS-VISIT(G,1)
 DFS-VISIT(G,4)
DFS-VISIT(G,5)
1 FOREACH u in V DO
2 [Link]=WHITE;
3 [Link]=NIL;
4 time=0;
DFS-VISIT(G,u) time=7
time=8 5 FOREACH u in V DO
6 IF [Link]==WHITE THEN
1 time=time+1; 7 DFS-VISIT(G,u)
2 [Link]=time;
−/−/NIL
1/−/NIL
3 [Link]=GRAY;
5/−/4
5/8/4
−/−/4
−/−/NIL
4 FOREACH v in adj(G,u) DO 3/−/4
3/4/4
−/−/NIL
−/−/4 1
5 IF [Link]==WHITE THEN
2 5
6 [Link]=u;
7 DFS-VISIT(G,v);
8 [Link]=BLACK; 3 6
4
9 time=time+1;
10 [Link]=time; −/−/NIL −/−/NIL
−/−/1
2/−/1 −/−/NIL
−/−/5
6/−/5
6/7/5

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 45

 Ordnung auf Knotenlisten gemäß Knotennummern
DFS: Beispiel (X)
DFS(G) //G=(V,E)
Aufrufs-Stack: DFS-VISIT(G,1)
 DFS-VISIT(G,4)
1 FOREACH u in V DO
2 [Link]=WHITE;
3 [Link]=NIL;
4 time=0;
DFS-VISIT(G,u) time=8
time=9 5 FOREACH u in V DO
6 IF [Link]==WHITE THEN
1 time=time+1; 7 DFS-VISIT(G,u)
2 [Link]=time;
−/−/NIL
1/−/NIL
3 [Link]=GRAY;
5/−/4
5/8/4
−/−/4
−/−/NIL
4 FOREACH v in adj(G,u) DO 3/−/4
3/4/4
−/−/NIL
−/−/4 1
5 IF [Link]==WHITE THEN
2 5
6 [Link]=u;
7 DFS-VISIT(G,v);
8 [Link]=BLACK; 3 6
4
9 time=time+1;
10 [Link]=time; −/−/NIL −/−/NIL
−/−/1
2/−/1
2/9/1 −/−/NIL
−/−/5
6/−/5
6/7/5

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 46

 Ordnung auf Knotenlisten gemäß Knotennummern
DFS: Beispiel (X)
DFS(G) //G=(V,E)
Aufrufs-Stack: DFS-VISIT(G,1)

1 FOREACH u in V DO
2 [Link]=WHITE;
3 [Link]=NIL;
4 time=0;
DFS-VISIT(G,u) time=9
time=10 5 FOREACH u in V DO
6 IF [Link]==WHITE THEN
1 time=time+1; 7 DFS-VISIT(G,u)
2 [Link]=time;
−/−/NIL
1/−/NIL
1/10/NIL
3 [Link]=GRAY;
5/−/4
5/8/4
−/−/4
−/−/NIL
4 FOREACH v in adj(G,u) DO 3/−/4
3/4/4
−/−/NIL
−/−/4 1
5 IF [Link]==WHITE THEN
2 5
6 [Link]=u;
7 DFS-VISIT(G,v);
8 [Link]=BLACK; 3 6
4
9 time=time+1;
10 [Link]=time; −/−/NIL −/−/NIL
−/−/1
2/−/1
2/9/1 −/−/NIL
−/−/5
6/−/5
6/7/5

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 47

 Ordnung auf Knotenlisten gemäß Knotennummern
DFS: Beispiel (XI)
DFS(G) //G=(V,E)
Aufrufs-Stack: DFS-VISIT(G,3)

1 FOREACH u in V DO
2 [Link]=WHITE;
3 [Link]=NIL;
4 time=0;
DFS-VISIT(G,u) time=10
time=12 5 FOREACH u in V DO
6 IF [Link]==WHITE THEN
1 time=time+1; 7 DFS-VISIT(G,u)
2 [Link]=time;
−/−/NIL
1/−/NIL
1/10/NIL
3 [Link]=GRAY;
5/−/4
5/8/4
−/−/4
−/−/NIL
4 FOREACH v in adj(G,u) DO 3/−/4
3/4/4
−/−/NIL
−/−/4 1
5 IF [Link]==WHITE THEN
2 5
6 [Link]=u;
7 DFS-VISIT(G,v);
8 [Link]=BLACK; 3 6
4
9 time=time+1;
10 [Link]=time; 11/12/NIL
−/−/NIL −/−/NIL
−/−/1
2/−/1
2/9/1 −/−/NIL
−/−/5
6/−/5
6/7/5

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 48

DFS-Wald = Menge von DFS-Bäumen
−/−/NIL
1/−/NIL
1/10/NIL
5/−/4
5/8/4
−/−/4
−/−/NIL 1 3
3/−/4
3/4/4
−/−/NIL
−/−/4 1

2 5
4

3 4 6
11/12/NIL
−/−/NIL −/−/NIL
−/−/1
2/−/1
2/9/1 −/−/NIL
−/−/5
6/−/5
6/7/5 2 5

Subgraph 𝐺𝐩𝐫𝐞𝐝 = (𝑉, 𝐸𝐩𝐫𝐞𝐝 ) von 𝐺 : 6

𝐸𝐩𝐫𝐞𝐝 = [Link],v v ∈ 𝑉 , [Link]NIL }

DFS-Baum gibt nicht
* unbedingt kürzesten
-

(und v,[Link] für ungerichtete Graphen) -

Weg wieder:
-

156 vs. 1456

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 49

Kante zeigen Zeichne restlichen Kanten aus 𝐺 auch in 𝐺𝐩𝐫𝐞𝐝 ein

−/−/NIL
1/−/NIL
1/10/NIL
5/−/4
5/8/4
−/−/4
−/−/NIL Rückwärtskante 1 3
3/−/4
3/4/4
−/−/NIL
−/−/4 1
(back edge)
2 5
4 Vorwärtskante
(forward edge)
3 4 6
11/12/NIL
−/−/NIL −/−/NIL
−/−/1
2/−/1
2/9/1 −/−/NIL
−/−/5
6/−/5
6/7/5 Schleife= 2 5
back edge Baumkante
Kreuzkante (tree edge)
Charakterisierung der (cross edge)
Kanten in 𝐺 mittels DFS 6

Baumkanten: alle Kanten in 𝐺𝐩𝐫𝐞𝐝

Vorwärtskanten: alle Kanten in 𝐺 zu Nachkommen in 𝐺𝐩𝐫𝐞𝐝 , die nicht Baumkante
Rückwärtskanten: alle Kanten in 𝐺 zu Vorfahren in 𝐺𝐩𝐫𝐞𝐝 , die nicht Baumkante
Kreuzkanten: alle anderen Kanten in 𝐺 (inkl. Schleifen)

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 50

Kantenart erkennen (I)
Sei (u, v) gerade betrachte Kante im DFS-Algorithmus. Dann ist (u, v)…

…eine Baumkante, wenn [Link]==WHITE

5/−/4
−/−/4
−/−/NIL
Beispiel: 56 3/−/4
3/4/4
−/−/NIL
−/−/4 1

2 5
da v noch nicht besucht wurde
und [Link]=u gesetzt wird
und dann ([Link],v)=(u,v) 3 4 6
als Kante in 𝐺𝐩𝐫𝐞𝐝 auftaucht
−/−/NIL −/−/NIL
−/−/1
2/−/1 −/−/NIL
−/−/5

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 51

 der
We wohn
Kantenart erkennen (II) werte er
de bet
ausgeht Zeigt
Sei (u, v) gerade betrachte Kante im DFS-Algorithmus. Dann ist (u, v)…

…eine Baumkante, wenn [Link]==WHITE

…eine Rückwärtskante, wenn [Link]==GRAY

−/−/NIL
1/−/NIL

1 −/−/NIL
Beispiel: 21 3/−/4
−/−/NIL
−/−/4

2 5
da die Kette von
grauen Knoten
auch im DFS-Baum 3 4 6
eine Kette bilden
−/−/NIL −/−/NIL
−/−/1
2/−/1 −/−/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 52

Kantenart erkennen (III)
Sei (u, v) gerade betrachte Kante im DFS-Algorithmus. Dann ist (u, v)…

…eine Baumkante, wenn [Link]==WHITE

…eine Rückwärtskante, wenn [Link]==GRAY

…eine Vorwärtskante, wenn [Link]==BLACK und [Link]<[Link]

DFS-Stacks verwendet
bei
,

Da ren brote werden

die Später "discovered" gefunder
- früher schwarz −/−/NIL
1/−/NIL

T
.

ange e Beispiel: 15 3/−/4

3/4/4
−/−/NIL
−/−/4 1 5/−/4
5/8/4
−/−/4
−/−/NIL

-
da [Link]<[Link] wurde v erst schwarz,
als u schon grau war;
2 5

aber u ist noch nicht abgeschlossen,

also wurde v von einem 3 6
4
echten Nachkomme von u besucht,
da u vorher zu einem weißen Knoten überging −/−/NIL −/−/NIL
−/−/5
6/−/5

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 53

Kantenart erkennen (IV)
Sei (u, v) gerade betrachte Kante im DFS-Algorithmus. Dann ist (u, v)…

…eine Baumkante, wenn [Link]==WHITE

…eine Rückwärtskante, wenn [Link]==GRAY

…eine Vorwärtskante, wenn [Link]==BLACK und [Link]<[Link]

…eine Kreuzkante, wenn [Link]==BLACK und [Link]<[Link]

−/−/NIL
1/−/NIL
5/−/4
5/8/4
−/−/4
−/−/NIL
3/−/4
3/4/4
−/−/NIL
−/−/4 1
Beispiel: 62
2 5
bilden per Definition
die restlichen Kanten
3 4 6
−/−/NIL −/−/NIL
−/−/5
6/−/5

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 54

Kantenarten in ungerichteten Graphen (I)

In einem ungerichteten GraphenO

𝐺 entstehen
…eine
durchBaumkante,
DFS nur - wennund
Baum- Rückwärtskanten.
[Link]==WHITE

Zur Erinnerung: Vorwärts- und Kreuzkanten haben [Link]==BLACK

-

[Link]: [Link]<[Link]
u v Hätte nur passieren können, als v von u
aus durch anderen Pfad bereits erreicht
und v in dem Moment grau wurde:
Sei u gerade aktiv (grau).
Betrachtete neue Kante {u,v}
u v
kann nur Vorwärts- oder
Kreuzkante werden, wenn
v schon abgeschlossen
(schwarz). Dann wäre aber Kante {v,u} bereits
bei v Rückwärtskante geworden.
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 55
Kantenarten in ungerichteten Graphen (II)

In einem ungerichteten Graphen 𝐺 entstehen

…eine
durchBaumkante, wennund
DFS nur Baum- Rückwärtskanten.
[Link]==WHITE

Zur Erinnerung: Vorwärts- und Kreuzkanten haben [Link]==BLACK

[Link]: [Link]>[Link]
u v Hätte nur passieren können, wenn u grau
geworden wäre, als v schon aktiv (grau) war:

Sei u gerade aktiv (grau).

u v u v
Betrachtete neue Kante {u,v}
kann nur Vorwärts- oder
Kreuzkante werden, wenn
v schon abgeschlossen direkt: indirekt:
(schwarz). u noch weiß und {v,u} u wird grau und {u,v}
bereits Baumkante. bereits Rückwärtskante.
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 56
 v Color-BRACK V dise Ladise

>
.

-
.

Geben Sie die-

Kreuzkanten in folgendem Graphen an,
wenn die DFS die Knoten gemäß Ordnungsnummer besucht:

1 Kind
Zuerst schwerf
1 2 3 ,

bevor 2

auf Greg gesetzt

D V CitL (v d ,K .
4 Bambert mind

& kan
.
Do

Ron
nount
ans

Geben Sie eine andere Ordnung für den Durchlauf des DFS an,
.

- O
bei der keine Kreuzkanten entstehen.

#
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 57
 Anwendungen DFS:
Topologisches Sortieren und
Starke Zusammenhangskomponenten

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 58

Job Scheduling Kante: Job X muss vor Job Y beendet sein

Job E

Job A Job G

Job D Job H

Job B
Job I

Job C Job F

In welcher Reihenfolge sollen die Jobs bearbeitet werden?

-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 59

Anwendungen Job Scheduling
Quelle: [Link]

edit : main.o kbd.o command.o display.o \

insert.o search.o files.o utils.o
cc -o edit main.o kbd.o display.o \
insert.o search.o files.o utils.o

main.o : main.c defs.h

cc -c main.c
kbd.o : kbd.c defs.h command.h
cc -c kbd.c
…

Spreadsheets (Formeln aktualisieren) makefile (Dateien compilieren)

Quelle: (Berechnung als

-

[Link] Computation Graph)

-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 60

Abstrakte Modellierung 4 3

Topologische Sortierung nur für

„directed acyclic graph“ (dag): 1 2

gerichteter
-
Graph ohne Zyklen 5

Topologische Sortierung einesOdag 𝐺 = (𝑉, 𝐸):

Knoten in linearer Ordnung, so dass für alle Knoten 𝑢, 𝑣 ∈ 𝑉 gilt,
-
-
dass 𝑢 vor 𝑣 in der Ordnung kommt, wenn 𝑢, 𝑣 ∈ 𝐸.
- - -

1 4 5 2 3

Sortierung nicht eindeutig,

-

„Kanten gehen immer nur nach rechts“ z.B. hier 2 und 3 vertauschbar
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 61
Topologisches Sortieren mittels DFS

TOPOLOGICAL-SORT(G) // G=(V,E) dag

1 newLinkedList(L);
2 --
run DFS(G) but, each time a node is finished,
-
insert in front of L
3 return [Link]
Laufzeit = 𝑂(|𝑉| + |𝐸|)

da Einfügen
in Liste vorne
in Zeit 𝑂(1)

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 62

Topologisches Sortieren: Korrektheit (I)

TOPOLOGICAL-SORT(G) // G=(V,E) dag

1 newLinkedList(L);
2 run DFS(G) but, each time a node is finished,
insert in front of L
3 return [Link]

Korrektheit:

Es genügt zu zeigen, dass jede von DFS inspizierte Kante (u,v) ∈ 𝐸 erfüllt:
[Link]<[Link], so dass u zeitlich nach v in Liste eingefügt wird
und daher positionell vor v in Liste zu finden ist
[Link]: v bereits grau
Würde Rückwärtskante erzeugen,
u v
d.h. der Graph hätte einen Zyklus (Widerspruch).

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 63

Topologisches Sortieren: Korrektheit (II)

TOPOLOGICAL-SORT(G) // G=(V,E) dag

1 newLinkedList(L);
2 run DFS(G) but, each time a node is finished,
insert in front of L
3 return [Link]

Korrektheit:

Es genügt zu zeigen, dass jede von DFS inspizierte Kante (u,v) ∈ 𝐸 erfüllt:
[Link]<[Link], so dass u zeitlich nach v in Liste eingefügt wird
und daher positionell vor v in Liste zu finden ist
[Link]: v noch weiß
Erzeugt Baumkante, also wird v Nachfahre von u
u v und [Link]<[Link], da Aufrufs-Stack
nicht zu u zurückkehrt, bevor v abgeschlossen.
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 64
Topologisches Sortieren: Korrektheit (III)

TOPOLOGICAL-SORT(G) // G=(V,E) dag

1 newLinkedList(L);
2 run DFS(G) but, each time a node is finished,
insert in front of L
3 return [Link]

Korrektheit:

Es genügt zu zeigen, dass jede von DFS inspizierte Kante (u,v) ∈ 𝐸 erfüllt:
[Link]<[Link], so dass u zeitlich nach v in Liste eingefügt wird
und daher positionell vor v in Liste zu finden ist
[Link]: v schwarz
Dann [Link] bereits gesetzt,
u v während [Link] erst später gesetzt wird,
also [Link]<[Link].
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 65
 Wie können Sie bei der topologischen Sortierung
mittels DFS fast ohne zusätzlichen Aufwand erkennen,
ob ihr Graph einen Zyklus hat?

Betrachten Sie folgendes Verfahren für topologisches Sortieren,

wenn die Anzahl eingehender Kanten jeweils bekannt ist.
Argumentieren Sie, dass das Verfahren korrekt ist:

Kahn1962(G) //G=(V,E) dag, inbound[u]=#edges to u

1 WHILE !isEmpty(V) DO
2 pick vertex u with inbound[u]==0
3 add u at the end of a list L
4 inbound[v]=inbound[v]-1 for each v with (u,v) in E
5 remove u from V and all (u,*) from E

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 66

Starke Zusammenhangskomponenten

Eine starke Zusammenhangskomponente eines gerichteten -

Graphen 𝐺 = 𝑉, 𝐸 ist eine Knotenmenge 𝐶 ⊆ 𝑉, so dass

-

ent
(a) es zwischen je zwei Knoten 𝑢, 𝑣 ∈ 𝐶 einen Pfad vonO
-
𝑢 nach 𝑣 gibt, und
(b) es keine Menge& 𝐷 ⊆ 𝑉 mit C ⊊ 𝐷 gibt, für die (a) auch gilt
- -

(𝐶 ist maximal).
größe unge gibt

1 2 3

Anwendung: Model Checking für

Korrektheitsnachweis von Systemen
4 5 6

Graph kann mehrere

7 8 9 starke Zusammenhangskomponenten
(strongly connected components, SCCs) haben

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 67

Eigenschaften
Starte zusarenhangskomponenten
𝐶
u v * Verschiedene-SCCs 𝐶, 𝐷 sind disjunkt, -

sonst gäbe es 𝑣 ∈ 𝐶 ∩ 𝐷 und

für beliebige 𝑢 ∈ 𝐶 und 𝑤 ∈ 𝐷 auch einen
Pfad von 𝑢 nach 𝑤 über 𝑣 (und umgekehrt),
w somit wären 𝐶 und 𝐷 identisch.
𝐷

𝐶 𝐷
Wenn es für verschiedene SCCs 𝐶, 𝐷 mit
u w
𝑢, 𝑣 ∈ 𝐶 und 𝑤, 𝑥 ∈ 𝐷 einen Pfad 𝑢𝑤 gibt,
dann kann es keinen Pfad 𝑥𝑣 geben,
-

sonst wären 𝐶 und 𝐷 identisch.

-

v x
* „Zwei SCCs sind
- -
nur in eine Richtung verbunden.“*
-
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 68
SCC Algorithmus: Ansatz
Depth fist scan
* Algorithmus von Kosaraju
-

Lasse zweimal DFS laufen: -

 einmal auf Graph& 𝐺 (4)

 einmal-auf transponiertem Graphen 𝐺 = 𝑉, 𝐸 :

𝐸 = 𝑣, 𝑢 𝑢, 𝑣 ∈ 𝐸 }
„drehe Kanten in G um“

𝐺 𝐺
1 2 3 1 2 3

4 5 6 4 5 6

7 8 9 7 8 9

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 69

SCCs im transponierten Graphen

--
SCCs in 𝐺 und 𝐺 bleiben identisch
(in beiden Fällen gibt es in jeder SCC
einen Weg von jedem Knoten zum anderen Knoten)

-
nur Übergänge zwischen SCCs drehen sich um O
𝐺 𝐺
1 2 3 1 2 3

4 5 6 4 5 6

7 8 9 7 8 9

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 70

SCC Algorithmus
Laufzeit = 𝑂(|𝑉| + |𝐸|)
SCC(G) // G=(V,E) directed graph

1 run DFS(G)
2 compute GT
3 run DFS(GT) but visit vertices in main loop
in descending finish time from 1
4 output each DFS tree in 3 as one SCC

DFS(G) //G=(V,E)

1 FOREACH u in V DO
2 [Link]=WHITE;
3 [Link]=NIL;
4 time=0;
5 FOREACH u in V DO
6 IF [Link]==WHITE THEN
7 DFS-VISIT(G,u)

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 71

SCC Algorithmus: Idee (I)
SCC(G) // G=(V,E) directed graph

1 run DFS(G)
2 compute GT
3 run DFS(GT) but visit vertices in main loop
in descending finish time from 1
4 output each DFS tree in 3 as one SCC

1 run DFS(G)

Knoten mit höchster

finish time liegt Bild nimmt zusammenhängenden Graphen an,
funktioniert aber auch allgemein, dann nacheinander
in dieser SCC für die zusammenhängenden Subgraphen

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 72

SCC Algorithmus: Idee (II)
SCC(G) // G=(V,E) directed graph

1 run DFS(G)
2 compute GT
3 run DFS(GT) but visit vertices in main loop
in descending finish time from 1
4 output each DFS tree in 3 as one SCC

2 compute GT

SCCs bleiben erhalten

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 73

 SCC Algorithmus: Idee (III)
SCC(G) // G=(V,E) directed graph

1 run DFS(G)
2 compute GT
3 run DFS(GT) but visit vertices in main loop
in descending finish time from 1
4 output each DFS tree in 3 as one SCC

3 run DFS(GT) …
9 
DFS-
Suche
9 

Besucht alle Knoten der SCC Diesen DFS-Baum

und kehrt dann zu Hauptschleife (und damit die SCC)
DFS zurück, da kein Übergang geben wir in Schritt 4 aus
zum nächsten SCC
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 74
SCC Algorithmus: Idee (IV)
SCC(G) // G=(V,E) directed graph

1 run DFS(G)
2 compute GT
3 run DFS(GT) but visit vertices in main loop
in descending finish time from 1
4 output each DFS tree in 3 as one SCC

3 run DFS(GT) …
9 
DFS-
Suche
9 
9  9 
9 
verbleibender Knoten mit Besucht alle Knoten der SCC
nächsthöheren und kehrt dann zu Hauptschleife usw.
finish time liegt DFS zurück, da kein Übergang
in dieser SCC zum nächsten SCC
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 75
SCC Algorithmus: Beispiel (I)
SCC(G) // G=(V,E) directed graph

1 run DFS(G)
2 compute GT
3 run DFS(GT) but visit vertices in main loop
in descending finish time from 1
4 output each DFS tree in 3 as one SCC
15
18 1 2 3 6

17 4 5 6 5 finish time
14

12
11 7 8 9
13
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 76
 -(
1/

11/
67891011 12

-
% 1
-

--T

1415161718
-

-X
*
4 ->

#se
>
-
>
-

..
2
7
.
1
we
SCC Algorithmus: Beispiel (II)
SCC(G) // G=(V,E) directed graph

1 run DFS(G)
2 compute GT
3 run DFS(GT) but visit vertices in main loop
in descending finish time from O
-
1
4 output each DFS tree in 3 as one SCC

⑳
15
umgedrehte Kanten 18 1 2 3 6

17
⑨ 4 5
14
6 5

O ②
12
11
O 7 8 9
13
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 77
Algorithmendesign

alle bekannten SCC-Algorithmen

-

sind DFS-basiert
-

Kosaraju 1978
Sharir 1981
Tarjan 1972

Kosarajus Tarjans Pfad-basierter

Algorithmus Algorithmus Algorithmus
(hier betrachtet)

zwei jeweils nur eine DFS-Ausführung,

DFS-Ausführungen speichern sich mehr Informationen „unterwegs“

asymptotisch alle gleich schnell, aber Tarjans und pfad-basierter Algorithmus schneller in Praxis
-
-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 78

 Minimale Spannbäume

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 79

Minimaler Spannbaum (MST)
Für einen zusammenhängenden, ungerichteten, gewichteten Graphen -

𝑤 ist der Subgraph 𝑇 = (𝑉, 𝐸 ) von&

𝐺 = (𝑉, 𝐸) mit Gewichten O 𝐺 ein -

Spannbaum („spanning tree“), wenn 𝑇 azyklisch ist und alle Knoten

- -

verbindet. spanbaum
Der Spannbaum istO
-

minimal, wenn
-panbaum
𝑤 𝑇 = 𝑤( 𝑢, 𝑣 ) ·

Azyklisch
{ , }∈
alle knoten
minimal für alle Spannbäume vonO
𝐺 ist. verbindet
·

+
2
1 2 3
Spannbaum des Graphen
-

4 7 5 (durch breite
11
Kanten gekennzeichnet)
1
3 4

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 80

Gewichtsvergleich
…
Der Spannbaum ist minimal, wenn rechter Spannbaum ist
minimal, da jeder Spannbaum,
-

𝑤 𝑇 = 𝑤( 𝑢, 𝑣 )
-

der Gewicht 00
7 oder 11 enthält,
{ , }∈ -

ein größeres Gesamtgewicht hat.

minimal für alle Spannbäume von 𝐺 ist.
-

O
𝑤 𝑇 = 2 + 3 + 7 + 11 = 23
- -
𝑤 𝑇′ = 4 + 2 + 3 + 1 = 10

2 2
1 2 3 1 2 3

4 7 5 4 7 5
11 11

1 1
3 4 3 4

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 81

Anwendung: Broadcast in Netzwerken
Broadcast:
1-Gbit/s verteile Nachricht an alle Switches
10-Mbit/s

verhindere „Broadcast Storm“:

-

Nachricht würde stets

-

-
zyklisch weiterverteilt

100-Mbit/s

Spanning Tree Protocol (IEEE 802.1D):

Wähle „Root Bridge“ als Wurzel des Spannbaums

- -

Gewicht abhängig von Geschwindigkeit und Entfernung von Root Bridge

-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 82

Allgemeiner MST-Algorithmus: Idee
genericMST(G,w) // G=(V,E) undirected, connected graph - -

w weight function -

1 A=∅
2 WHILE A does not form a spanning tree for G DO =

3 find safe edge {u,v} for A

4 A = A ∪{{u,v}}
5 return A

-
A Teilmenge der Kanten eines MST & Kante {u,v} ist sicher („safe“) für A,
-

wenn A ∪{{u,v}} noch Teilmenge eines MST ist

- -

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 83

Allgemeiner MST-Algorithmus
genericMST(G,w) // G=(V,E) undirected, connected graph
w weight function
1 A=∅
2 WHILE A does not form a spanning tree for G DO
3 find safe edge {u,v} for A
4 A = A ∪{{u,v}}
5 return A

Terminierung:
Da wir zeigen werden, dass es in jeder Iteration eine sichere Kante für
A gibt (sofern A noch kein Spannbaum), terminiert die Schleife nach
=>
-

maximal |𝐸| Iterationen.

-

Korrektheit:
Da in jeder Iteration nur sichere Kanten hinzugefügt werden
(für die A ∪{{u,v}} noch Teilmenge eines MST ist),
ist am Ende der WHILE-Schleife A ein MST.

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 84

Terminologie
𝑉−𝑆
2
1 2 3
𝑆 bölmeh
↑
7 5 Schnitt (𝑺, 𝑽 − 𝑺) partitioniert
4 11 -

Knoten des Graphen in zwei Mengen

1
3 4 {𝒖, 𝒗} überbrückt Schnitt (𝑺, 𝑽 − 𝑺),
wenn 𝑢 ∈ 𝑆 und 𝑣 ∈ 𝑉 − 𝑆

- Kanten {2,5}, {2,4}

überbrücken Schnitt
Schnitt (𝑺, 𝑽 − 𝑺) respektiert A⊆ 𝑬,
wenn keine Kante {𝑢, 𝑣} aus A
den Schnitt überbrückt

- {𝒖, 𝒗} leichte Kante für (𝑺, 𝑽 − 𝑺),

A (grau markierte Kanten)
von Schnitt respektiert
-

- Kante {2,5} ist leicht - wenn w( 𝑢, 𝑣 ) minimal für alle den

-

für Schnitt -
Schnitt überbrückenden Kanten

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 85

Leicht = sicher
𝑉−𝑆 {u,v} sicher für A, wenn
2 A ∪{{u,v}} Teilmenge eines MST
1 2 𝑆
3

7 5 Schnitt (𝑺, 𝑽 − 𝑺) partitioniert

4 11
Knoten des Graphen in zwei Mengen
1
3 4 {𝒖, 𝒗} überbrückt Schnitt (𝑺, 𝑽 − 𝑺),
wenn 𝑢 ∈ 𝑆 und 𝑣 ∈ 𝑉 − 𝑆

Schnitt (𝑺, 𝑽 − 𝑺) respektiert A⊆ 𝑬,

Sei A Teilmenge eines MST, wenn keine Kante {𝑢, 𝑣} aus A
(𝑺,𝑽−𝑺) Schnitt, der A respektiert, den Schnitt überbrückt
und {𝑢, 𝑣} eine leichte Kante,
die den Schnitt überbrückt. {𝒖, 𝒗} leichte Kante für (𝑺, 𝑽 − 𝑺),
Dann ist {𝑢, 𝑣} sicher für A. wenn w( 𝑢, 𝑣 ) minimal für alle den
Schnitt überbrückenden Kanten

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 86

Leicht = sicher: Beweis (I)
{u,v} sicher für A, wenn
Sei 𝑇 ein MST, der A enthält. A ∪{{u,v}} Teilmenge eines MST
Wenn {𝑢, 𝑣} in 𝑇, dann fertig.

Schnitt (𝑺, 𝑽 − 𝑺) partitioniert

Wenn {𝑢, 𝑣} nicht in 𝑇, dann
Knoten des Graphen in zwei Mengen
konstruieren wir MST 𝑈, der
A ∪{{u,v}} enthält, folglich
ist {𝑢, 𝑣} trotzdem sicher für A. {𝒖, 𝒗} überbrückt Schnitt (𝑺, 𝑽 − 𝑺),
wenn 𝑢 ∈ 𝑆 und 𝑣 ∈ 𝑉 − 𝑆

Schnitt (𝑺, 𝑽 − 𝑺) respektiert A⊆ 𝑬,

Sei A Teilmenge eines MST, wenn keine Kante {𝑢, 𝑣} aus A
(𝑺,𝑽−𝑺) Schnitt, der A respektiert, den Schnitt überbrückt
und {𝑢, 𝑣} eine leichte Kante,
die den Schnitt überbrückt. {𝒖, 𝒗} leichte Kante für (𝑺, 𝑽 − 𝑺),
Dann ist {𝑢, 𝑣} sicher für A. wenn w( 𝑢, 𝑣 ) minimal für alle den
Schnitt überbrückenden Kanten

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 87

Leicht = sicher: Beweis (II)
MST 𝑇 muss eine andere überbrückende
x y Kante {𝑥, 𝑦} für den Pfad von 𝑢 nach 𝑣
enthalten, damit alle Knoten erreichbar sind.

Da der Schnitt A respektiert, ist diese

Kante {𝑥, 𝑦} nicht in A enthalten.
u v

𝑉−𝑆 𝑆 Setze 𝑈 = 𝑇 − 𝑥, 𝑦 ∪ {𝑢, 𝑣}

𝑈 ist Spannbaum, da
Sei A Teilmenge eines MST, jeder Knoten erreichbar ist:
(𝑺,𝑽−𝑺) Schnitt, der A respektiert, Nimm statt „Brücke“ {𝑥, 𝑦} den Pfad
und {𝑢, 𝑣} eine leichte Kante, 𝑥 nach 𝑢, dann {𝑢, 𝑣}, dann 𝑣 nach 𝑦.
die den Schnitt überbrückt.
Dann ist {𝑢, 𝑣} sicher für A.

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 88

Leicht = sicher: Beweis (III)
MST 𝑇 muss eine andere überbrückende
x y Kante {𝑥, 𝑦} für den Pfad von 𝑢 nach 𝑣
enthalten, damit alle Knoten erreichbar sind.

Da der Schnitt A respektiert, ist diese

Kante {𝑥, 𝑦} nicht in A enthalten.
u v

𝑉−𝑆 𝑆 Setze 𝑈 = 𝑇 − 𝑥, 𝑦 ∪ {𝑢, 𝑣}

𝑈 ist minimal, da für leichte Kante

Sei A Teilmenge eines MST, {𝑢, 𝑣} gilt: 𝑤 𝑢, 𝑣 ≤ 𝑤 𝑥, 𝑦 und
(𝑺,𝑽−𝑺) Schnitt, der A respektiert,
und {𝑢, 𝑣} eine leichte Kante, 𝑤 𝑈 = 𝑤 𝑇 − 𝑤 𝑥, 𝑦 + 𝑤 𝑢, 𝑣
die den Schnitt überbrückt. ≤𝑤 𝑇
Dann ist {𝑢, 𝑣} sicher für A.

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 89

Algorithmendesign

„Leicht=sicher“
legt Greedy-Strategie
für konkrete Implementierung
nahe
Jarnik 1930
Kruskal 1956 Prim 1957
Dijkstra 1959

Algorithmus Algorithmus
von Kruskal von Prim

lässt parallel mehrere konstruiert einen MST

Unterbäume eines MST wachsen Knoten für Knoten

Bemerkung: beide Algorithmen funktionieren -

X auch für negative Kantengewichte

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 90

 UNION(G,u,v) setzt 𝑠𝑒𝑡(𝑤) = 𝑠𝑒𝑡(𝑢) ∪ 𝑠𝑒𝑡(𝑣)
Algorithmus von Kruskal für alle Knoten w ∈ 𝑠𝑒𝑡(𝑢) ∪ 𝑠𝑒𝑡(𝑣)
MST-Kruskal(G,w) // G=(V,E) undirected, connected graph
w weight function
1 A=∅
2 FOREACH v in V DO set(v)={v};
3 Sort edges according to weight in nondecreasing order
4 FOREACH {u,v} in E according to order DO
5 IF set(u)!=set(v) THEN
6 A = A ∪{{u,v}} wenn set(u)==set(v),
7 UNION(G,u,v); dann wären Knoten schon
8 return A verbunden und {u,v} erzeugte Zyklus

2
Zu jedem Knoten& 𝑣 sei 𝑠𝑒𝑡(𝑣) Menge
1 2 3 von mit 𝑣 durch A verbundenen Knoten.
Zu Beginn ist 𝑠𝑒𝑡(𝑣) = {𝑣}.
4 7 5
11
𝑠𝑒𝑡(𝑢), 𝑠𝑒𝑡(𝑣) sind disjunkt oder identisch
1
3 4
Im Beispiel 𝑠𝑒𝑡 1 = 1,2 , 𝑠𝑒𝑡(4) = {4,5}.
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 91
Algorithmus von Kruskal: Korrektheit
MST-Kruskal(G,w) // G=(V,E) undirected, connected graph
w weight function
1 A=∅
2 FOREACH v in V DO set(v)={v};
3 Sort edges according to weight in nondecreasing order
4 FOREACH {u,v} in E according to order DO
5 IF set(u)!=set(v) THEN
6 A = A ∪{{u,v}}
7 UNION(G,u,v);
8 return A

2
Jede ausgewählte Kante {𝑢, 𝑣} mit
1 2 3 𝑠𝑒𝑡 𝑢 ≠ 𝑠𝑒𝑡 𝑣 ist leicht für Schnitt
𝑠𝑒𝑡 𝑢 , 𝑉 − 𝑠𝑒𝑡 𝑢 .
4 7 5
11
Schnitt respektiert A.
1
3 4 Somit Kante auch sicher für A.

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 92

Algorithmus von Kruskal: Beispiel (I)
MST-Kruskal(G,w) // G=(V,E) undirected, connected graph
w weight function
1 A=∅
2 FOREACH v in V DO set(v)={v};
3 Sort edges according to weight in nondecreasing order
4 FOREACH {u,v} in E according to order DO
5 IF set(u)!=set(v) THEN
6 A = A ∪{{u,v}}
7 UNION(G,u,v);
8 return A {2} {3}
5
2 3
-1 9 4
{4}

{1} 1 7 7 {7} 4

Initialisierung (1-3) 8 11 0
6 5
{6} -2 {5}

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 93

Algorithmus von Kruskal: Beispiel (II)
MST-Kruskal(G,w) // G=(V,E) undirected, connected graph
w weight function
1 A=∅
2 FOREACH v in V DO set(v)={v};
3 Sort edges according to weight in nondecreasing order
4 FOREACH {u,v} in E according to order DO
5 IF set(u)!=set(v) THEN
3456
6 A = A ∪{{u,v}}

"y
7 UNION(G,u,v);
123456
8 return A {2} {3}
5
2 =3

15 -1 4
I {4}
↑
9
,
1456
-
S
{1} 1 7 7 {7} 4 7456
Schritte 4-8:
Kante {5,6} aufnehmen 8 11 D0
&
3456
6 5
OS
{5,6}
{6} arb
S
-2
O
no
{5,6}
{5}

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 94

eigeneauch
un
verbunde
T
456
karten
kleiste
zofe
Algorithmus von Kruskal: Beispiel (III)
MST-Kruskal(G,w) // G=(V,E) undirected, connected graph
w weight function
1 A=∅
2 FOREACH v in V DO set(v)={v};
3 Sort edges according to weight in nondecreasing order
4 FOREACH {u,v} in E according to order DO
5 IF set(u)!=set(v) THEN
6 A = A ∪{{u,v}}
7 UNION(G,u,v);
8 return A {1,2}
{2} {3}
5
2 3
-1 9 4
{4}

{1}
{1,2} 1 7 7 {7} 4
Schritte 4-8:
8 11 0
Kante {1,2} aufnehmen
6 5
{5,6}
{6} -2 {5,6}
{5}

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 95

Algorithmus von Kruskal: Beispiel (IV)
MST-Kruskal(G,w) // G=(V,E) undirected, connected graph
w weight function
1 A=∅
2 FOREACH v in V DO set(v)={v};
3 Sort edges according to weight in nondecreasing order
4 FOREACH {u,v} in E according to order DO
5 IF set(u)!=set(v) THEN
6 A = A ∪{{u,v}}
7 UNION(G,u,v);
8 return A {1,2}
{2} {3}
5
2 3
-1 9 4
{4}
{4,5,6}

{1}
{1,2} 1 7 7 {7} 4
Schritte 4-8:
8 11 0
Kante {4,5} aufnehmen
6 5
{5,6}
{6}
{4,5,6} -2 {4,5,6}
{5,6}
{5}

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 96

Algorithmus von Kruskal: Beispiel (V)
MST-Kruskal(G,w) // G=(V,E) undirected, connected graph
w weight function
1 A=∅
2 FOREACH v in V DO set(v)={v};
3 Sort edges according to weight in nondecreasing order
4 FOREACH {u,v} in E according to order DO
5 IF set(u)!=set(v) THEN
6 A = A ∪{{u,v}}
7 UNION(G,u,v);
8 return A {1,2}
{2} {3,4,5,6}
{3}
5
2 3
-1 9 4 {3,4,5,6}
{4}
{4,5,6}

{1}
{1,2} 1 7 7 {7} 4
Schritte 4-8:
8 11 0
Kante {3,4} aufnehmen
6 5
{5,6}
{3,4,5,6}
{6}
{4,5,6} -2 {4,5,6}
{5,6}
{5}
{3,4,5,6}

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 97

Algorithmus von Kruskal: Beispiel (VI)
MST-Kruskal(G,w) // G=(V,E) undirected, connected graph
w weight function
1 A=∅
2 FOREACH v in V DO set(v)={v};
3 Sort edges according to weight in nondecreasing order
4 FOREACH {u,v} in E according to order DO
5 IF set(u)!=set(v) THEN
6 A = A ∪{{u,v}}
7 UNION(G,u,v);
{1,…,6}
{1,2}
{2} {1,…,6}
{3,4,5,6}
{3}
8 return A
5
2 3
-1 9 4 {1,…,6}
{3,4,5,6}
{4}
{4,5,6}

{1}
{1,…,6}
{1,2} 1 7 7 {7} 4
Schritte 4-8:
8 11 0
Kante {2,3} aufnehmen
6 5
{1,…,6}
{5,6}
{3,4,5,6}
{6}
{4,5,6} -2 {4,5,6}
{5,6}
{5}
{3,4,5,6}
{1,…,6}

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 98

Algorithmus von Kruskal: Beispiel (VII)
MST-Kruskal(G,w) // G=(V,E) undirected, connected graph
w weight function
1 A=∅
2 FOREACH v in V DO set(v)={v};
3 Sort edges according to weight in nondecreasing order
4 FOREACH {u,v} in E according to order DO
5 IF set(u)!=set(v) THEN
6 A = A ∪{{u,v}}
7 UNION(G,u,v);
{1,…,6}
{1,2}
{2} {1,…,6}
{3,4,5,6}
{3}
8 return A
5
2 3
-1 9 4 {1,…,6}
{3,4,5,6}
{4}
{4,5,6}

{1}
{1,…,6}
{1,2} 1 7 7 {7} 4
Schritte 4-8:
8 11 0
Kante {2,6} nicht aufnehmen,
da 𝑠𝑒𝑡(2) = 𝑠𝑒𝑡(6) = {1, … , 6} 6 5
{1,…,6}
{5,6}
{3,4,5,6}
{6}
{4,5,6} -2 {4,5,6}
{5,6}
{5}
{3,4,5,6}
{1,…,6}

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 99

Algorithmus von Kruskal: Beispiel (VIII)
MST-Kruskal(G,w) // G=(V,E) undirected, connected graph
w weight function
1 A=∅
2 FOREACH v in V DO set(v)={v};
3 Sort edges according to weight in nondecreasing order
4 FOREACH {u,v} in E according to order DO
5 IF set(u)!=set(v) THEN
6 A = A ∪{{u,v}}
7 UNION(G,u,v);
{1,…,6}
{1,2}
{2} {1,…,6}
{3,4,5,6}
{3}
8 return A
5
2 3
-1 9 4 {1,…,6}
{3,4,5,6}
{4}
{4,5,6}

{1}
{1,…,6}
{1,2} 1 7 7 {7} 4
Schritte 4-8:
8 11 0
Kante {1,6} nicht aufnehmen,
da 𝑠𝑒𝑡(1) = 𝑠𝑒𝑡(6) = {1, … , 6} 6 5
{1,…,6}
{5,6}
{3,4,5,6}
{6}
{4,5,6} -2 {4,5,6}
{5,6}
{5}
{3,4,5,6}
{1,…,6}

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 100

Algorithmus von Kruskal: Beispiel (IX)
MST-Kruskal(G,w) // G=(V,E) undirected, connected graph
w weight function
1 A=∅
2 FOREACH v in V DO set(v)={v};
3 Sort edges according to weight in nondecreasing order
4 FOREACH {u,v} in E according to order DO
5 IF set(u)!=set(v) THEN
6 A = A ∪{{u,v}}
7 UNION(G,u,v); {1,…,7} {1,…,7}
{1,…,6}
{1,2}
{2} {1,…,6}
{3,4,5,6}
{3}
8 return A
5
2 3
-1 9 4 {1,…,6}
{1,…,7}
{3,4,5,6}
{4}
{4,5,6}

{1,…,7}
{1}
{1,…,6}
{1,2} 1 7 7 {1,…,7}
{7} 4
Schritte 4-8:
8 11 0
Kante {3,7} aufnehmen
6 5
{1,…,7}
{1,…,6}
{5,6}
{3,4,5,6}
{6}
{4,5,6} -2 {4,5,6}
{5,6}
{5}
{1,…,7}
{3,4,5,6}
{1,…,6}

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 101

Algorithmus von Kruskal: Beispiel (X)
MST-Kruskal(G,w) // G=(V,E) undirected, connected graph
w weight function
1 A=∅
2 FOREACH v in V DO set(v)={v};
3 Sort edges according to weight in nondecreasing order
4 FOREACH {u,v} in E according to order DO > alle Karten durchlafen -

5 IF set(u)!=set(v) THEN
6 A = A ∪{{u,v}}
7 UNION(G,u,v); {1,…,7} {1,…,7}
{1,…,6}
{1,2}
{2} {1,…,6}
{3,4,5,6}
{3}
8 return A
5
2 3
-1 9 4 {1,…,6}
{1,…,7}
{3,4,5,6}
{4}
{4,5,6}

{1,…,7}
{1}
{1,…,6}
{1,2} 1 7 7 {1,…,7} 4
Schritte 4-8:
8 11 0
Kante {6,7} nicht aufnehmen,
da 𝑠𝑒𝑡(6) = 𝑠𝑒𝑡(7) = {1, … , 7} 6 5
{1,…,7}
{1,…,6}
{5,6}
{3,4,5,6}
{6}
{4,5,6} -2 {4,5,6}
{5,6}
{5}
{1,…,7}
{3,4,5,6}
{1,…,6}

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 102

Algorithmus von Kruskal: Beispiel (XI)
MST-Kruskal(G,w) // G=(V,E) undirected, connected graph
w weight function
1 A=∅
2 FOREACH v in V DO set(v)={v};
3 Sort edges according to weight in nondecreasing order
4 FOREACH {u,v} in E according to order DO
5 IF set(u)!=set(v) THEN
6 A = A ∪{{u,v}}
7 UNION(G,u,v); {1,…,7} {1,…,7}
{1,…,6}
{1,2}
{2} {1,…,6}
{3,4,5,6}
{3}
8 return A
5
2 3
-1 9 4 {1,…,6}
{1,…,7}
{3,4,5,6}
{4}
{4,5,6}

{1,…,7}
{1}
{1,…,6}
{1,2} 1 7 7 {1,…,7}
{7} 4

8 11 0
𝑤 𝑇 = −1 + 5 + 4 + 0 − 2 + 9 = 15
6 5
{1,…,7}
{1,…,6}
{5,6}
{3,4,5,6}
{6}
{4,5,6} -2 {4,5,6}
{5,6}
{5}
{1,…,7}
{3,4,5,6}
{1,…,6}

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 103

Algorithmus von Kruskal: Laufzeit
MST-Kruskal(G,w) // G=(V,E) undirected, connected graph
w weight function
1 A=∅
2 FOREACH v in V DO set(v)={v};
3 Sort edges according to weight in nondecreasing order
4 FOREACH {u,v} in E according to order DO
5 IF set(u)!=set(v) THEN
6 A = A ∪{{u,v}}
7 UNION(G,u,v);
8 return A
-
Laufzeit = 𝑂(|𝐸| log |𝐸|)

(mit vielen Optimierungen)

Laufzeit = 𝑂(|𝐸| log |𝑉|)

da V − 1 ≤ 𝐸 ≤ |𝑉| und
somit log 𝐸 = 𝜃(log |𝑉|)

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 104

 Überlegen Sie sich anhand eines Beispielgraphen, dass
ein MST zwar das Gesamtgewicht reduziert, aber nicht immer
kurze Wege (#Kanten) garantiert.

Angenommen, Sie haben bereits einen MST berechnet, und

reduzieren nachträglich das Gewicht einer Kante des MSTs.
Wie ändert sich Ihr MST?

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 105

Algorithmus von Prim
O // r root in V, MST given through [Link] values
MST-Prim(G,w,r)

1 FOREACH v in V DO {[Link]=∞; [Link]=NIL;}

2 [Link]=-∞; Q=V;
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //smallest key value
5 FOREACH v in adj(u) DO
6 IF v∈Q and w({u,v})<[Link] THEN
7 [Link]=w({u,v});
8 [Link]=u;

Idee: Algorithmus fügt, -

beginnend mit Auswahl der nächsten Kante
A gemäß&
-

Wurzelknoten, immer leichte Kante zu -

key-Wert, der stets
zusammenhängender Menge hinzu
-
aktualisiert wird

A implizit definiert durch

A = { {v,[Link]} | v ∈ 𝑉 − ({𝑟} ∪ 𝑄) }

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 106

Algorithmus von Prim: Beispiel (I)
MST-Prim(G,w,r) // r root in V, MST given through [Link] values

1 FOREACH v in V DO {[Link]=∞; [Link]=NIL;}

2 [Link]=-∞; Q=V;
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //smallest key value
5 FOREACH v in adj(u) DO
6 IF v∈Q and w({u,v})<[Link] THEN
7 [Link]=w({u,v});
∞, NIL ∞, NIL
8 [Link]=u;
5
2 3
-1 9 4
Initialisierung (1-2) ∞, NIL ∞, NIL

Shoot
r=6
1 7 7 ∞, NIL 4

8 11 0
𝑄 = {1,2,3,4,5,6,7}
6 5
-2
A= v,[Link] v ∈ 𝑉 − 𝑟 ∪𝑄 −∞, NIL ∞, NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 107
Algorithmus von Prim: Beispiel (II)
MST-Prim(G,w,r) // r root in V, MST given through [Link] values

1 FOREACH v in V DO {[Link]=∞; [Link]=NIL;}

2 [Link]=-∞; Q=V;
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //smallest key value
5 FOREACH v in adj(u) DO
6 IF v∈Q and w({u,v})<[Link] THEN
7 [Link]=w({u,v});
∞, 6
7,NIL ∞, NIL
8 [Link]=u;
5
2 3
-1 9 4
Schritte 3-8: 6
8, NIL
∞, ∞, NIL
u=r=6 extrahieren
1 7 7 6
11,NIL
∞, 4

8 11 0
𝑄
𝑄== {1,2,3,4,5,6,7}
{1,2,3,4,5,7}
6 5
A= v,[Link] v ∈ 𝑉 − 𝑟 ∪𝑄 −∞, NIL O
-2
6
−2,NIL
∞,
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 108
Algorithmus von Prim: Beispiel (III)
MST-Prim(G,w,r) // r root in V, MST given through [Link] values

1 FOREACH v in V DO {[Link]=∞; [Link]=NIL;}

2 [Link]=-∞; Q=V;
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //smallest key value
5 FOREACH v in adj(u) DO
6 IF v∈Q and w({u,v})<[Link] THEN
7 [Link]=w({u,v});
∞, 6
7,NIL ∞, NIL
8 [Link]=u;
5
2 3
-1 9 4
Schritte 3-8: 6
8, NIL
∞, 0, 5NIL
∞,
u=5 extrahieren
1 7 7 6
11,NIL
∞, 4

11
𝑄
𝑄𝑄=
=={1,2,3,4,5,6,7}
{1,2,3,4,5,7}
{1,2,3,4,7} 8
O
0
6 5
-2
A= v,[Link] v ∈ 𝑉 − 𝑟 ∪𝑄 −∞, NIL ∞, 6
−2,NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 109
Algorithmus von Prim: Beispiel (IV)
MST-Prim(G,w,r) // r root in V, MST given through [Link] values

1 FOREACH v in V DO {[Link]=∞; [Link]=NIL;}

2 [Link]=-∞; Q=V;
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //smallest key value
5 FOREACH v in adj(u) DO
6 IF v∈Q and w({u,v})<[Link] THEN
7 [Link]=w({u,v});
6
7,NIL
∞, 4, 4
∞, NIL
8 [Link]=u;
5
2 3
Schritte 3-8: 6
8, NIL
∞,
-1 9 G
4
0, 5NIL
∞,
u=4 extrahieren
1 7 7 6
11,NIL
∞, 4

8 11 0
𝑄 𝑄
===
𝑄𝑄= {1,2,3,7}
{1,2,3,4,5,6,7}
{1,2,3,4,5,7}
{1,2,3,4,7}
6 5
-2
A= v,[Link] v ∈ 𝑉 − 𝑟 ∪𝑄 −∞, NIL ∞, 6
−2,NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 110
Algorithmus von Prim: Beispiel (V)
MST-Prim(G,w,r) // r root in V, MST given through [Link] values

1 FOREACH v in V DO {[Link]=∞; [Link]=NIL;}

2 [Link]=-∞; Q=V;
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //smallest key value
5 FOREACH v in adj(u) DO
6 IF v∈Q and w({u,v})<[Link] THEN
7 [Link]=w({u,v});
8 [Link]=u;
∞, 3
6
5,NIL
7, O
4, 4
∞, NIL

2 &
5
3
-1 9 4
Schritte 3-8: 6
8, NIL
∞, &
0, 5NIL
∞,
u=3 extrahieren
1 7 7 11, 36
9, NIL
∞, 4

8 11 0
𝑄 𝑄
𝑄𝑄===
=𝑄 ={1,2,3,7}
{1,2,7}
{1,2,3,4,5,6,7}
{1,2,3,4,5,7}
{1,2,3,4,7}
6 5
-2
A= v,[Link] v ∈ 𝑉 − 𝑟 ∪𝑄 −∞, NIL O
∞, 6
−2,NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 111
Algorithmus von Prim: Beispiel (VI)
MST-Prim(G,w,r) // r root in V, MST given through [Link] values

1 FOREACH v in V DO {[Link]=∞; [Link]=NIL;}

2 [Link]=-∞; Q=V;
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //smallest key value
5 FOREACH v in adj(u) DO
6 IF v∈Q and w({u,v})<[Link] THEN
7 [Link]=w({u,v}); 3
∞, 6
5,NIL
7, 4, 4
∞, NIL
8 [Link]=u;
5
2 3
-1 9 4
Schritte 3-8: −1,
∞, 62
8, NIL 0, 5NIL
∞,
u=2 extrahieren
1 7 7 11, 36
9, NIL
∞, 4

8 11 0
𝑄 𝑄
𝑄𝑄= =
=𝑄
=𝑄 ={1,2,3,7}
= {1,7}
{1,2,7}
{1,2,3,4,5,6,7}
{1,2,3,4,5,7}
{1,2,3,4,7}
6 5
-2
A= v,[Link] v ∈ 𝑉 − 𝑟 ∪𝑄 −∞, NIL ∞, 6
−2,NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 112
Algorithmus von Prim: Beispiel (VII)
MST-Prim(G,w,r) // r root in V, MST given through [Link] values

1 FOREACH v in V DO {[Link]=∞; [Link]=NIL;}

2 [Link]=-∞; Q=V;
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //smallest key value
&
5 FOREACH v in adj(u) DO
6
7
·
IF v∈Q and w({u,v})<[Link] THEN
[Link]=w({u,v});
-

3
6
5,NIL
7,
∞,
8 [Link]=u;
4, 4
∞, NIL
5
2 3
-1 9 4
Schritte 3-8: −1,
∞, 62
8, NIL 0, 5NIL
∞,
u=1 extrahieren
1 7 7 11, 36
9, NIL
∞, 4

8 11 0
𝑄 𝑄
=𝑄
𝑄𝑄= =
=𝑄𝑄={1,2,3,7}
=
={1,2,7}
{1,7}
{7}
{1,2,3,4,5,6,7}
{1,2,3,4,5,7}
{1,2,3,4,7}
6 5
-2
A= v,[Link] v ∈ 𝑉 − 𝑟 ∪𝑄 −∞, NIL ∞, 6
−2,NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 113
Algorithmus von Prim: Beispiel (VIII)
MST-Prim(G,w,r) // r root in V, MST given through [Link] values

1 FOREACH v in V DO {[Link]=∞; [Link]=NIL;}

2 [Link]=-∞; Q=V;
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //smallest key value
5 FOREACH v in adj(u) DO
6 IF v∈Q and w({u,v})<[Link] THEN
7 [Link]=w({u,v}); 3
∞, 6
5,NIL
7, 4, 4
∞, NIL
8 [Link]=u;
5
2 3
-1 9 4
Schritte 3-8: −1,
8,
∞, 62
NIL 0, 5NIL
∞,
u=7 extrahieren
1 7 7 11, 36
9, NIL
∞, 4

8 11 0
𝑄 𝑄
=𝑄
𝑄𝑄= =
=𝑄 𝑄
𝑄
={1,2,3,7}
==
= {}
{1,7}
{7}
{1,2,7}
{1,2,3,4,5,6,7}
{1,2,3,4,5,7}
{1,2,3,4,7}
6 5
-2
A= v,[Link] v ∈ 𝑉 − 𝑟 ∪𝑄 −∞, NIL ∞, 6
−2,NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 114
Algorithmus von Prim: Korrektheit
MST-Prim(G,w,r) // r root in V, MST given through [Link] values

1 FOREACH v in V DO {[Link]=∞; [Link]=NIL;}

2 [Link]=-∞; Q=V;
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //smallest key value
5 FOREACH v in adj(u) DO
6 IF v∈Q and w({u,v})<[Link] THEN
7 [Link]=w({u,v});
8 [Link]=u;

Kanten in A laufen nur Alle Knoten v ∈ 𝑄 enthalten als Wert

zwischen den bereits [Link] immer das kleinste Kantengewicht
aufgesammelten Knoten in 𝑉 − 𝑄 zu einem bereits aufgesammelten
Knoten [Link] in 𝑉 − 𝑄

Folglich respektiert der Daher beschreibt der in Schritt 4

Schnitt (𝑄, 𝑉 − 𝑄) die Menge A ausgewählte Knoten u eine
überbrückende, leichte Kante(u,[Link])

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 115

Algorithmus von Prim: Laufzeit
MST-Prim(G,w,r) // r root in V, MST given through [Link] values

1 FOREACH v in V DO {[Link]=∞; [Link]=NIL;}

2 [Link]=-∞; Q=V;
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //smallest key value
5 FOREACH v in adj(u) DO
6 IF v∈Q and w({u,v})<[Link] THEN
7 [Link]=w({u,v});
8 [Link]=u;
Laufzeit = 𝑂( 𝐸 + |𝑉| log |𝑉|)

(mit vielen Optimierungen,

speziell Fibonacci-Heaps)

zum Vergleich: Kruskal

𝑂 𝐸 log 𝑉 = 𝑂 𝐸 log 𝐸

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 116

 Kürzeste Wege
in (gerichteten) Graphen

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 117

Single-Source Shortest Path (SSSP)
Finde von QuelleOs aus
jeweils den (gemäß Kantengewichten) kürzesten Pfad zu allen anderen Knoten
-

2
Länge eines Pfades
- m

2 𝑝 = (𝑣 , … , 𝑣 ) ∈ 𝑉
von 𝑢 = 𝑣 zu 𝑣 = 𝑣 :
Länge=8
7 2
𝑤 𝑝 =∑ 𝑤(( 𝑣 , 𝑣 ))
2 1
2
Länge=6
3 s
2
2 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑢, 𝑣) =
Länge=7 4
-2 min{𝑤(𝑝) ∶ 𝑝 Pfad von 𝑢 nach 𝑣 }

2 2
3
{ ∞
wenn 𝑣 erreichbar von 𝑢
sonst

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 118

 SSSP vs. BFS, DFS, MST
- MST
Breath Depth
First
(für ungerichteten Graphen)
Fist search minimiert Gesamtgewicht
BFS + DFS: keine Kantengewichte
- 𝑤 𝑇 = ∑ 𝑤( 𝑢, 𝑣 )
des Baumes
BFS findet kürzeste „Kantenwege“,
aber nicht kürzeste „Gewichtswege“:
-

- 5
1 2

2
2 5 10 5

1 3
9 4 3
5
Umsteigebraten
-welgen
Kürzester „Kantenweg“ 1 nach 3 = 13 Kürzester Weg 14 mit Gewicht
Kürzester „Gewichtsweg“ = 123
-

10 im MST nicht enthalten

-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 119

Negative Schwingungen

5 5
1 2 3

Zyklus mit Gesamtlänge = 5

Wiederholtes Durchlaufen des Zyklus

ergäbe beliebig kleine Gesamtlänge
-

Negative Kantengewichte sind erlaubt,

aber keine (erreichbaren) Zyklen mit negativem Gesamtgewicht!
-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 120

 Zyklen?

5 5
1 2 3

0

Kürzeste Pfade können keine Zyklen
-

mit positivem Gesamtgewicht enthalten

-

(sonst ohne Zyklus kürzerer Pfad)

-

+Annahme über
nicht-negative Zyklen
*
Kürzeste Pfade enthalten höchstens (eliminierbare) Zyklen mit Gewicht 0
-

Es gibt stets einen kürzesten Pfad mit Kantenlänge  |𝑽| − 𝟏

-
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 121
Kürzeste Teilpfade

𝑠 𝑥 𝑧

Kürzester Pfad von 08

𝑠 nach 𝑧 durch Knoten 𝑥 -

Teilpfad 𝒔 → 𝒙 eines kürzesten Pfades 𝒔 → 𝒙 → 𝒛

ist auch stets kürzester Pfad von 𝒔 nach 𝒙
-

(sonst gäbe es kürzeren Pfad von 𝑠 nach 𝑧)

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 122

Algorithmen für SSSP

Gemeinsame Idee:
„Lockerung“ / Relaxation

Bellmann 1958 Dijkstra 1959

Ford 1962 Lawler 1976

Algorithmus Algorithmus Algorithmus

von Bellman-Ford für dags von Dijkstra

Laufzeit
Laufzeit = 𝑂( 𝑉 𝐸) Laufzeit = 𝑂( 𝑉 + 𝐸 ) = 𝑂( 𝑉 log |𝑉| + 𝐸 )

funktioniert nur für

funktioniert -

funktioniert nur für dags nicht-negative

allgemein -

↓ Kantengewichte
directed -

(auch ungerichtete Graphen) acyclich (auch ungerichtete Graphen)

grap us
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 123
Relax!
Zu Beginn
Idee: verringere aktuelle Distanz von Knoten 𝑣, Distanz = ∞
für alle Knoten  s
-

wenn durch Kante (𝑢, 𝑣) kürzere Distanz erreichbar: -

>
-
relax(G,u,v,w) ditraliste
, auper

1
-Zir) Quelle
IF [Link] > [Link] + w((u,v)) THEN
+
>
- bei Gleichheit Quese S
nidisiere
,
-

2 [Link]=[Link] + w((u,v));
-

3 [Link]=u;

dist=7 dist=13 dist=7 dist=12

5 5
1 2 relax 1 2

5 5
1 2 relax 1 2
keine
dist=7 dist=11 dist=7 dist=11
A
ktudisitry
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 124
Bellman-Ford-Algorithmus initSSSP(G,s,w)

Bellman-Ford-SSSP(G,s,w) 1 FOREACH v in V DO
laten 2 [Link]=∞;
alle
1 initSSSP(G,s,w); * Distance nochen - 3 [Link]=NIL;
FOR i=1 TO |V|-1 DO Vergänge auf
-

2 4 [Link]=0;
: 11
3 FOREACH (u,v) in E DO seres
Z

4 relax(G,u,v,w); > Distant aktualisie prüft zusätzlich,

-

5 FOREACH (u,v) in E DO ob „negativer Zyklus“

6 IF [Link] > [Link]+w((u,v)) THEN erreichbar (=false)
7 return false; ↓
Ausgabe
8 return true; Laufzeit = 𝜃(|𝐸| |𝑉|)
Berechnet
zu
de
tel
wegen geschachtelter nebenbei -E
alle fase
Auss
FOR-Schleifen in 2 und 3 Distanzen ver
.

allen Ersten
zur Quelle

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 125

 Bellman-Ford: Idee / Korrektheit (I)
Betrachte Wirkung
Bellman-Ford-SSSP(G,s,w) auf kürzesten Pfad
-

von s nach z
-

1 initSSSP(G,s,w);
2 FOR i=1 TO |V|-1 DO Erste Iteration der
3 FOREACH (u,v) in E DO FOR-Schleife in 2
4 relax(G,u,v,w);
erfasst (mindestens)
5 FOREACH (u,v) in E DO
6 IF [Link] > [Link]+w((u,v)) THEN den ersten Schritt
7 return false; von s zum
8 return true; nächsten Knoten

dist=2
Andere Relaxation-
2 -1
3 1 Schritte (auch später)
s z können dies
dist=0 nicht „zerstören“,
da sonst
Wenn keine „negativen Zyklen“, gibt es kürzerer Pfad
kürzesten Pfad der Kantenlänge  𝑉 − 1 ohne Schleifen
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 126
 Bellman-Ford: Idee / Korrektheit (II)
Betrachte Wirkung
Bellman-Ford-SSSP(G,s,w) auf kürzesten Pfad
von s nach z
1 initSSSP(G,s,w);
2 FOR i=1 TO |V|-1 DO Zweite Iteration der
3 FOREACH (u,v) in E DO FOR-Schleife in 2
4 relax(G,u,v,w);
erfasst (mindestens)
5 FOREACH (u,v) in E DO
6 IF [Link] > [Link]+w((u,v)) THEN den zweiten Schritt
7 return false; von s zum
8 return true; zweiten Knoten

dist=2 dist=1
2 -1
3 1
s z

dist=0

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 127

 Bellman-Ford: Idee / Korrektheit (III)
Betrachte Wirkung
Bellman-Ford-SSSP(G,s,w) auf kürzesten Pfad
von s nach z
1 initSSSP(G,s,w);
2 FOR i=1 TO |V|-1 DO Dritte Iteration der
3 FOREACH (u,v) in E DO FOR-Schleife in 2
4 relax(G,u,v,w);
erfasst (mindestens)
5 FOREACH (u,v) in E DO
6 IF [Link] > [Link]+w((u,v)) THEN den dritten Schritt
7 return false; von s zum
8 return true; dritten Knoten

dist=2 dist=1 usw.

2 -1
3 1
s z

dist=0
dist=4

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 128

 Bellman-Ford: Idee / Korrektheit (IV)
Bellman-Ford-SSSP(G,s,w) Genau dann,
wenn es keinen Pfad
1 initSSSP(G,s,w);
von s zu einem
2 FOR i=1 TO |V|-1 DO
3 FOREACH (u,v) in E DO Knoten u gibt, dann
4 relax(G,u,v,w); bleibt [Link]=∞
5 FOREACH (u,v) in E DO
6 IF [Link] > [Link]+w((u,v)) THEN
7 return false; Am Ende steht
8 return true; in jedem Knoten
[Link]=𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑢)
dist=2 dist=1
-1 und
2 3
s 1 z
[Link] zeigt
dist=0 auf Vorgängerknoten
dist=4
in kürzestem Pfad

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 129

Bellman-Ford: Idee / Korrektheit (V)
Bellman-Ford-SSSP(G,s,w) Prüfschritte 5-7
1 initSSSP(G,s,w);
2 FOR i=1 TO |V|-1 DO
Fall 1:
3 FOREACH (u,v) in E DO Wenn keine
4 relax(G,u,v,w); „negativen Zyklen“
5 FOREACH (u,v) in E DO erreichbar, dann auch
6 IF [Link] > [Link]+w((u,v)) THEN keine Rückgabe false
7 return false;
8 return true;

Wenn (u,v) Kante ist, dann ist

[Link] = 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑣) Gilt auch im Fall

 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑢) + w((u,v)) 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑢) = ∞;
 [Link] + w((u,v)) der Fall [𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑣) = ∞
und 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑠, 𝑢 < ∞]
und folglich Bedingung in 6 nie erfüllt. ist nicht möglich.
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 130
Bellman-Ford: Idee / Korrektheit (VI)
Bellman-Ford-SSSP(G,s,w) Prüfschritte 5-7
1 initSSSP(G,s,w);
2 FOR i=1 TO |V|-1 DO
Fall 2:
3 FOREACH (u,v) in E DO Wenn „negative
4 relax(G,u,v,w); Zyklen“ erreichbar,
5 FOREACH (u,v) in E DO dann Rückgabe
6 IF [Link] > [Link]+w((u,v)) THEN false
7 return false;
8 return true;
𝑣 =𝑣
Sei 𝑐 = (𝑣 , … , 𝑣 ) ∈ 𝑉 „negativer Zyklus“ mit 𝑤 𝑐 = ∑ 𝑤(( 𝑣 , 𝑣 )) < 0

Verfahren gäbe nur true, wenn 𝑣 .dist  𝑣 .dist + 𝑤((𝑣 , 𝑣 )) für 𝑖 = 1, … 𝑘

Dann wäre wegen 𝑤 𝑐 < 0 und 𝑣 = 𝑣 und 𝑣 . dist<∞ für erreichbare Knoten:
∑ 𝑣 . dist  ∑ 𝑣 . dist + ∑𝒌𝒊 𝟏 𝑤((𝑣 , 𝑣 ))
< ∑ 𝑣 . dist = ∑ 𝑣 . dist Widerspruch.
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 131
Bellman-Ford: Beispiel (I)
Bellman-Ford-SSSP(G,s,w)

1 initSSSP(G,s,w);
2 FOR i=1 TO |V|-1 DO
3 FOREACH (u,v) in E DO
4 relax(G,u,v,w);
5 FOREACH (u,v) in E DO
6 IF [Link] > [Link]+w((u,v)) THEN
7 return false;
8 return true;

Initialisierung -3 ∞/NIL
für O
s=1 in 1 ∞/NIL
0
6 2 3 3
Anfang =
1 1
>
-
1 1 7 4 4
-3
-
0/NIL
2 6
∞/NIL
5
2 ∞/NIL

5
∞/NIL ∞/NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 132
Bellman-Ford: Beispiel (II)
Bellman-Ford-SSSP(G,s,w) Kanten in FOREACH in 3 -

gemäß lexikographischer
1 initSSSP(G,s,w); -

Ordnung: (1,2), (1,6), (2,3), …

2 FOR i=1 TO |V|-1 DO
3 FOREACH (u,v) in E DO
4 relax(G,u,v,w);
5 FOREACH (u,v) in E DO
6 IF [Link] > [Link]+w((u,v)) THEN
7 return false;
8 return true;

FOR-Schleife 2 (i=1) -3 𝟔/2

∞/NIL
𝟔/1
∞/NIL
relax(1,2) 0
relax(1,6) 6 2 3 3
1
relax(2,3)
1 1 7 4 4
relax(2,7)
relax(3,1) 0/NIL -3 ∞/NIL
𝟕/2 2 𝟗/3
∞/NIL
relax(3,4) 2 6 5
relax(5,4) 5
5 Mit I
- .
= 𝟐/1
∞/NIL ∞/NIL
das
2) 5 prid Mil.
=

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 133

Bellman-Ford: Beispiel (III)
Bellman-Ford-SSSP(G,s,w)

1 initSSSP(G,s,w);
2 FOR i=1 TO |V|-1 DO
3 FOREACH (u,v) in E DO
4 relax(G,u,v,w);
5 FOREACH (u,v) in E DO
6 IF [Link] > [Link]+w((u,v)) THEN
7 return false;
8 return true;

FOR-Schleife 2 (i=1) -3 𝟑/7

𝟔/2
∞/NIL
𝟔/1
∞/NIL
𝟑/6
relax(6,2) 0
relax(6,5) 6 2 3 3
1
relax(6,7)
1 1 7 4 4
relax(7,3)
0/NIL -3 ∞/NIL
−𝟏/6
𝟕/2 2 𝟗/3
∞/NIL
2 6 5
5
𝟐/1
∞/NIL 𝟕/6
∞/NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 134
Bellman-Ford: Beispiel (IV)
Bellman-Ford-SSSP(G,s,w)
Keine Änderungen
-

1 initSSSP(G,s,w); mehr in den

-

2 FOR i=1 TO |V|-1 DO folgenden Iterationen

-

3 FOREACH (u,v) in E DO
4 relax(G,u,v,w);
5 FOREACH (u,v) in E DO Algorithmus gibt
6 IF [Link] > [Link]+w((u,v)) THEN true zurück
7 return false;
8 return true;

FOR-Schleife 2 (i=2) -3 𝟑/7

𝟔/2
∞/NIL
𝟔/1
∞/NIL
𝟑/6
relax(1,2) 0
relax(1,6) 6 2 3 3
1
relax(2,3)
1 1 7 4 4
relax(2,7)
relax(3,1) 0/NIL -3 ∞/NIL
−𝟏/6
𝟕/2 𝟔/3
2 𝟗/3
∞/NIL
relax(3,4) 2 6 5
relax(5,4) 5
𝟐/1
∞/NIL 𝟕/6
∞/NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 135
Bellman-Ford: Beispiel (V)
Bellman-Ford-SSSP(G,s,w)

1 initSSSP(G,s,w); Kürzester Weg

2 FOR i=1 TO |V|-1 DO z.B. von 1 zu 3
3 FOREACH (u,v) in E DO
4 relax(G,u,v,w); durch
5 FOREACH (u,v) in E DO Vorgängerwerte
6 IF [Link] > [Link]+w((u,v)) THEN gegeben
7 return false;
8 return true;

-3 𝟑/7
𝟔/2
∞/NIL
𝟔/1
∞/NIL
𝟑/6
0
6 2 3 3
1
1 1 7 4 4
0/NIL -3 ∞/NIL
−𝟏/6
𝟕/2 𝟔/3
2 𝟗/3
∞/NIL
2 6 5
5
𝟐/1
∞/NIL 𝟕/6
∞/NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 136
SSSP mittels Topologischer Sortierung
6
4 3
3 11
1
dag 6
mit Gewichten 1 2

-2 4
5

Topologisches Sortieren

6 11
3 -2 4 1
1 4 5 2 3
6

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 137

SSSP-Algorithmus für Dags
TopoSort-SSSP(G,s,w) // G dag

1 initSSSP(G,s,w);
2 execute topological sorting
3 FOREACH u in V in topological order DO
4 FOREACH v in adj(u) DO
5 relax(G,u,v,w);

6 11
3 -2 4 1
1 4 5 2 3
6

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 138

SSSP-Algorithmus für Dags: Beispiel (I)
TopoSort-SSSP(G,s,w) // G dag
) ist went
1 initSSSP(G,s,w); eindeutig
2 execute topological sorting
3 FOREACH u in V in topological order DO
4 FOREACH v in adj(u) DO
5 relax(G,u,v,w);

Initialisierung für s=1 in 1

und Sortieren in 2

6 11
3 -2 4 1
1 4 5 2 3
6
0/NIL ∞/NIL ∞/NIL ∞/NIL ∞/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 139

SSSP-Algorithmus für Dags: Beispiel (II)
TopoSort-SSSP(G,s,w) // G dag

1 initSSSP(G,s,w);
2 execute topological sorting
3 FOREACH u in V in topological order DO
4 FOREACH v in adj(u) DO
5 relax(G,u,v,w);

3 FOREACH (u=1)

6 11
3 -2 4 1
1 4 5 2 3
6
0/NIL ∞/NIL
𝟑/1 ∞/NIL ∞/NIL
𝟔/1 𝟏𝟏/1
∞/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 140

SSSP-Algorithmus für Dags: Beispiel (III)
TopoSort-SSSP(G,s,w) // G dag

1 initSSSP(G,s,w);
2 execute topological sorting
3 FOREACH u in V in topological order DO
4 FOREACH v in adj(u) DO
5 relax(G,u,v,w);

3 FOREACH (u=4)

6 11
3 -2 4 1
1 4 5 2 3
6
0/NIL ∞/NIL
𝟑/1 ∞/NIL
𝟏/4 ∞/NIL
𝟔/1 𝟏𝟏/1
𝟗/4
∞/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 141

SSSP-Algorithmus für Dags: Beispiel (IV)
TopoSort-SSSP(G,s,w) // G dag

1 initSSSP(G,s,w);
2 execute topological sorting
3 FOREACH u in V in topological order DO
4 FOREACH v in adj(u) DO
5 relax(G,u,v,w);

3 FOREACH (u=5)

6 11
3 -2 4 1
1 4 5 2 3
6
0/NIL ∞/NIL
𝟑/1 ∞/NIL
𝟏/4 ∞/NIL
𝟔/1
𝟓/5 𝟏𝟏/1
𝟗/4
∞/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 142

SSSP-Algorithmus für Dags: Beispiel (V)
TopoSort-SSSP(G,s,w) // G dag

1 initSSSP(G,s,w);
2 execute topological sorting
3 FOREACH u in V in topological order DO
4 FOREACH v in adj(u) DO
5 relax(G,u,v,w);

3 FOREACH (u=2)

6 11
3 -2 4 1
1 4 5 2 3
6
0/NIL ∞/NIL
𝟑/1 ∞/NIL
𝟏/4 ∞/NIL
𝟔/1
𝟓/5 𝟔/2
𝟏𝟏/1
𝟗/4
∞/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 143

SSSP-Algorithmus für Dags: Korrektheit+Laufzeit
TopoSort-SSSP(G,s,w) // G dag Korrektheit:
Kanten auf einem
1 initSSSP(G,s,w); kürzesten Pfad
2 execute topological sorting werden nacheinander
3 FOREACH u in V in topological order DO „gelockert“
4 FOREACH v in adj(u) DO
5 relax(G,u,v,w);
(vgl. Bellman-Ford)
Laufzeit = 𝜃( 𝐸 + |𝑉|)

6 11
3 -2 4 1
1 4 5 2 3
6
0/NIL ∞/NIL
𝟑/1 ∞/NIL
𝟏/4 ∞/NIL
𝟔/1
𝟓/5 𝟔/2

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 144

 Überlegen Sie sich, wie Sie mit Hilfe des
Bellman-Ford-Algorithmus alle Knoten identifizieren
können, die auf einem „negativen Zyklus“ liegen.

Angenommen, Sie beschreiben ein Job-Scheduling-Problem

per Dag, wobei jeder Job eine gewisse Zeit benötigt,
bevor er beendet ist. Wie können Sie 11
mit Hilfe des Dag-SSSP-Algorithmus 6
bestimmen, wie lange ihr D C
Projekt insgesamt braucht?

A B
3
4
E
2
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 145
Dijkstra-Algorithmus

D
Dijkstra-SSSP(G,s,w) Voraussetzung: alle
𝒘( 𝒖, 𝒗 ) ≥ 𝟎 laten habe
1 initSSSP(G,s,w); Positive für alle Kanten
2 Q=V; //let S=V-Q Sericht
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //wrt. dist (mittels Fibonacci-Heaps)
5 FOREACH v in adj(u) DO
6 relax(G,u,v,w); Laufzeit = 𝜃(|𝑉| log |𝑉| + |𝐸|)

MST-Prim(G,w,r)

1 FOREACH v in V DO {[Link]=∞; [Link]=NIL;}

2 [Link]=-∞; Q=V;
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q);
5 FOREACH v in adj(u) DO
6 IF v∈Q and w({u,v})<[Link] THEN

[ Ähnlichkeit zu
Prims Algorithmus
7
8
[Link]=w({u,v});
[Link]=u;

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 146

Dijkstra-Algorithmus: Beispiel (I)
Dijkstra-SSSP(G,s,w) Voraussetzung:
𝒘( 𝒖, 𝒗 ) ≥ 𝟎
1 initSSSP(G,s,w); für alle Kanten
2 Q=V; //let S=V-Q
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //wrt. dist
5 FOREACH v in adj(u) DO
6 relax(G,u,v,w);

Initialisierung 3 ∞/NIL
in Schritt 1 ∞/NIL
0
6 2 3 3
1
1 1 4
0/NIL 3
∞/NIL
2 6 5 2
5
∞/NIL ∞/NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 147
Dijkstra-Algorithmus: Beispiel (II)
Dijkstra-SSSP(G,s,w) Voraussetzung:
𝒘( 𝒖, 𝒗 ) ≥ 𝟎
1 initSSSP(G,s,w); für alle Kanten
2 Q=V; //let S=V-Q
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //wrt. dist
5 FOREACH v in adj(u) DO
6 relax(G,u,v,w);

3 WHILE (u=1) 3 ∞/NIL

𝟔/1
∞/NIL
relax(1,2) 0
6 2 3 3
relax(1,6) 1
1 1 4
3
0/NIL
0
2 6 5 2
∞/NIL

5
üsiz
𝟐/1
∞/NIL ∞/NIL
ola ,
sea
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 148
Dijkstra-Algorithmus: Beispiel (III)
Dijkstra-SSSP(G,s,w) Voraussetzung:
𝒘( 𝒖, 𝒗 ) ≥ 𝟎
1 initSSSP(G,s,w); für alle Kanten
2 Q=V; //let S=V-Q
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //wrt. dist
5 FOREACH v in adj(u) DO
6 relax(G,u,v,w);

3 WHILE (u=6) 3 𝟓/6

∞/NIL
𝟑/6
𝟔/1
∞/NIL
relax(6,2) 0
6 2 3 3
relax(6,3) 1
relax(6,5) 1 4
1
0/NIL 3
∞/NIL
2 6 5 2
5
𝟐/1
∞/NIL 𝟕/6
∞/NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 149
Dijkstra-Algorithmus: Beispiel (IV)
Dijkstra-SSSP(G,s,w) Voraussetzung:
𝒘( 𝒖, 𝒗 ) ≥ 𝟎
1 initSSSP(G,s,w); für alle Kanten
2 Q=V; //let S=V-Q
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //wrt. dist
5 FOREACH v in adj(u) DO
6 relax(G,u,v,w);

3 WHILE (u=2) 3 𝟑/2

𝟓/6
∞/NIL
𝟑/6
𝟔/1
∞/NIL
relax(2,3) 0
6 2 3 3
relax(2,5) 1
1 1 4
0/NIL 3
∞/NIL
2 6 5 2
5
𝟐/1
∞/NIL 𝟕/6
𝟒/2
∞/NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 150
Dijkstra-Algorithmus: Beispiel (V)
Dijkstra-SSSP(G,s,w) Voraussetzung:
𝒘( 𝒖, 𝒗 ) ≥ 𝟎
1 initSSSP(G,s,w); für alle Kanten
2 Q=V; //let S=V-Q
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //wrt. dist
5 FOREACH v in adj(u) DO
6 relax(G,u,v,w);

3 WHILE (u=3) 3 𝟑/2

𝟓/6
∞/NIL
𝟑/6
𝟔/1
∞/NIL
relax(3,1) 0
6 2 3 3
relax(3,4) 1
1 1 4
0/NIL 3
∞/NIL
𝟔/3
2 6 5 2
5
𝟐/1
∞/NIL 𝟕/6
𝟒/2
∞/NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 151
Dijkstra-Algorithmus: Beispiel (VI)
Dijkstra-SSSP(G,s,w) Voraussetzung:
𝒘( 𝒖, 𝒗 ) ≥ 𝟎
1 initSSSP(G,s,w); für alle Kanten
2 Q=V; //let S=V-Q
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //wrt. dist
5 FOREACH v in adj(u) DO
6 relax(G,u,v,w);

3 WHILE (u=5) 3 𝟑/2

𝟓/6
∞/NIL
𝟑/6
𝟔/1
∞/NIL
0
6 2 3 3
1
1 1 4
0/NIL 3
∞/NIL
𝟔/3
2 6 5 2
5
𝟐/1
∞/NIL 𝟕/6
𝟒/2
∞/NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 152
Dijkstra-Algorithmus: Beispiel (VII)
Dijkstra-SSSP(G,s,w) Voraussetzung:
𝒘( 𝒖, 𝒗 ) ≥ 𝟎
1 initSSSP(G,s,w); für alle Kanten
2 Q=V; //let S=V-Q
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //wrt. dist
5 FOREACH v in adj(u) DO
6 relax(G,u,v,w);

3 WHILE (u=4) 3 𝟑/2

𝟓/6
∞/NIL
𝟑/6
𝟔/1
∞/NIL
relax(4,5) 0
6 2 3 3
1
1 1 4
0/NIL 3
∞/NIL
𝟔/3
2 6 5 2
5
𝟐/1
∞/NIL 𝟕/6
𝟒/2
∞/NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 153
Dijkstra-Algorithmus: Beispiel (VIII)
Dijkstra-SSSP(G,s,w) Voraussetzung:
𝒘( 𝒖, 𝒗 ) ≥ 𝟎
1 initSSSP(G,s,w); für alle Kanten
2 Q=V; //let S=V-Q
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //wrt. dist
5 FOREACH v in adj(u) DO
6 relax(G,u,v,w);

3 𝟑/2
𝟓/6
∞/NIL
𝟑/6
𝟔/1
∞/NIL
0
6 2 3 3
1
1 1 4
Beispiel: 0/NIL 3
∞/NIL
𝟔/3
kürzester 2 6 5 2
Weg 14 5
𝟐/1
∞/NIL 𝟕/6
𝟒/2
∞/NIL
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 154
Dijkstra-Algorithmus: Korrektheit (I)
Dijkstra-SSSP(G,s,w) Für jeden betrachteten
Knoten u in der
1 initSSSP(G,s,w); WHILE-Schleife gilt:
2 Q=V; //let S=V-Q [Link]= 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑢)
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //wrt. dist
5 FOREACH v in adj(u) DO Angenommen, u wäre erster
6 relax(G,u,v,w); Knoten, bei dem nicht der Fall

Insbesondere us und S  

u
da [Link]=0 korrekt
s
Betrachte kürzesten Pfad su
mit „erstem“ Knoten y nicht in S,
y und Vorgängerknoten x in S.
x

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 155

Dijkstra-Algorithmus: Korrektheit (II)
Dijkstra-SSSP(G,s,w) Für jeden betrachteten
Knoten u in der
1 initSSSP(G,s,w); WHILE-Schleife gilt:
2 Q=V; //let S=V-Q [Link]= 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑢)
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //wrt. dist
5 FOREACH v in adj(u) DO Angenommen, u wäre erster
6 relax(G,u,v,w); Knoten, bei dem nicht der Fall

Es gilt [Link]= 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑥),

s u da u der erste Knoten ist, bei dem
diese Gleichung nicht gilt

y Da Kante (x,y) in dem Moment,

x als x zu 𝑆 hinzugefügt wurde,
S 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑦) auch „relaxed“ wurde,
𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑥) gilt auch [Link]= 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑦)
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 156
Dijkstra-Algorithmus: Korrektheit (III)
Dijkstra-SSSP(G,s,w) Für jeden betrachteten
Knoten u in der
1 initSSSP(G,s,w); WHILE-Schleife gilt:
2 Q=V; //let S=V-Q [Link]= 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑢)
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //wrt. dist
5 FOREACH v in adj(u) DO Angenommen, u wäre erster
6 relax(G,u,v,w); Knoten, bei dem nicht der Fall

nicht-
Da nur positive
negative
Kantengewichte gilt
s u
𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑠, 𝑦  𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑢),

y und damit
x

S 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑦) [Link] = 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑠, 𝑦

𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑥)  𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑠, 𝑢 ≤ [Link]
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 157
Dijkstra-Algorithmus: Korrektheit (IV)
Dijkstra-SSSP(G,s,w) Für jeden betrachteten
Knoten u in der
1 initSSSP(G,s,w); WHILE-Schleife gilt:
2 Q=V; //let S=V-Q [Link]= 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑢)
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //wrt. dist
5 FOREACH v in adj(u) DO Angenommen, u wäre erster
6 relax(G,u,v,w); Knoten, bei dem nicht der Fall

Da nur positive
Andererseits
Kantengewichte
wurde gilt
s u
u vor y für S
𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑠, 𝑦  𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠,
ausgewählt, also 𝑢),

y [Link] damit
≤ [Link] und
x

S 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑦) [Link] = 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑠, 𝑦

𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑥)  𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑠, 𝑢 ≤ [Link]
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 158
Dijkstra-Algorithmus: Korrektheit (V)
Dijkstra-SSSP(G,s,w) Für jeden betrachteten
Knoten u in der
1 initSSSP(G,s,w); WHILE-Schleife gilt:
2 Q=V; //let S=V-Q [Link]= 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑢)
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); //wrt. dist
5 FOREACH v in adj(u) DO Angenommen, u wäre erster
6 relax(G,u,v,w); Knoten, bei dem nicht der Fall

Folglich
Da nur positive
Andererseits
Kantengewichte
wurde gilt
s u
[Link] u=vor y für S𝑠, 𝑦
𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡
𝑠, 𝑦 𝑠, 𝑢𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠,
ausgewählt,
= 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡
𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡 [Link],
=also 𝑢),da

y [Link] damit
≤ [Link] und
x

S 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑦) [Link] = 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑠, 𝑦

𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(𝑠, 𝑥)  𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑠, 𝑢 ≤ [Link]
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 159
Dijkstra-Algorithmus und negative Kantengewichte (I)
Dijkstra-SSSP(G,s,w)
kürzeste Weg 15 via
1 initSSSP(G,s,w); 1 2  4  3  5
2 Q=V; //let S=V-Q mit Gewicht 6+2-5+0=3
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); Dijkstra-Algorithmus für s=1
5 FOREACH v in adj(u) DO
gibt aber 15 an
6 relax(G,u,v,w);

1
2 3
6
-5
2
1 4

0
5
5

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 160

Dijkstra-Algorithmus und negative Kantengewichte (II)
Dijkstra-SSSP(G,s,w)
kürzeste Weg 15 via
1 initSSSP(G,s,w); 1 2  4  3  5
2 Q=V; //let S=V-Q mit Gewicht 6+2-5+0=3
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); Dijkstra-Algorithmus für s=1
5 FOREACH v in adj(u) DO
gibt aber 15 an
6 relax(G,u,v,w);

∞/NIL 1
Initialisierung 2 3 ∞/NIL
in Schritt 1
6
-5
2
0/NIL 1 4
∞/NIL 0
5
5
∞/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 161

Dijkstra-Algorithmus und negative Kantengewichte (III)
Dijkstra-SSSP(G,s,w)
kürzeste Weg 15 via
1 initSSSP(G,s,w); 1 2  4  3  5
2 Q=V; //let S=V-Q mit Gewicht 6+2-5+0=3
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); Dijkstra-Algorithmus für s=1
5 FOREACH v in adj(u) DO
gibt aber 15 an
6 relax(G,u,v,w);

∞/NIL
𝟔/1 1
3 WHILE (u=1) 2 3 ∞/NIL

6
-5
2
0/NIL 1 4
∞/NIL 0
5
5
𝟓/1
∞/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 162

Dijkstra-Algorithmus und negative Kantengewichte (IV)
Dijkstra-SSSP(G,s,w)
kürzeste Weg 15 via
1 initSSSP(G,s,w); 1 2  4  3  5
2 Q=V; //let S=V-Q mit Gewicht 6+2-5+0=3
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); Dijkstra-Algorithmus für s=1
5 FOREACH v in adj(u) DO
gibt aber 15 an
6 relax(G,u,v,w);

∞/NIL
𝟔/1 1
3 WHILE (u=5) 2 3 ∞/NIL

6
-5
2
0/NIL 1 4
∞/NIL 0
5
5
𝟓/1
∞/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 163

Dijkstra-Algorithmus und negative Kantengewichte (V)
Dijkstra-SSSP(G,s,w)
kürzeste Weg 15 via
1 initSSSP(G,s,w); 1 2  4  3  5
2 Q=V; //let S=V-Q mit Gewicht 6+2-5+0=3
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); Dijkstra-Algorithmus für s=1
5 FOREACH v in adj(u) DO
gibt aber 15 an
6 relax(G,u,v,w);

∞/NIL
𝟔/1 1
3 WHILE (u=2) 2 3 ∞/NIL
𝟕/2

6
-5
2
0/NIL 1 4
∞/NIL
𝟖/2 0
5
5
𝟓/1
∞/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 164

Dijkstra-Algorithmus und negative Kantengewichte (VI)
Dijkstra-SSSP(G,s,w)
kürzeste Weg 15 via
1 initSSSP(G,s,w); 1 2  4  3  5
2 Q=V; //let S=V-Q mit Gewicht 6+2-5+0=3
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); Dijkstra-Algorithmus für s=1
5 FOREACH v in adj(u) DO
gibt aber 15 an
6 relax(G,u,v,w);

∞/NIL
𝟔/1 1
3 WHILE (u=3) 2 3 ∞/NIL
𝟕/2

6 Der im Augenblick
-5
2 nicht erfasste Weg
von 13 über 4
0/NIL 1 4
wird später zum
∞/NIL
𝟖/2 0 kürzeren Weg
5
5
𝟓/1  wird nicht „relaxed“
∞/NIL

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 165

Dijkstra-Algorithmus und negative Kantengewichte (VII)
Dijkstra-SSSP(G,s,w)
kürzeste Weg 15 via
1 initSSSP(G,s,w); 1 2  4  3  5
2 Q=V; //let S=V-Q mit Gewicht 6+2-5+0=3
3 WHILE !isEmpty(Q) DO
4 u=EXTRACT-MIN(Q); Dijkstra-Algorithmus für s=1
5 FOREACH v in adj(u) DO
gibt aber 15 an
6 relax(G,u,v,w);

∞/NIL
𝟔/1 1
3 WHILE (u=4) 2 3 ∞/NIL
𝟕/2
𝟑/4

6
-5
2
0/NIL 1 4
∞/NIL
𝟖/2 0
5
5
𝟓/1
∞/NIL Algorithmus terminiert.

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 166

Kantengewichte nicht-negativ machen?

Versuch: Addiere absoluten Wert der kleinsten Kante zu allen Werten

-5 0
1 2 1 2
+5
1 2 6 7
3 3

kürzester Weg 13: kürzester Weg 13:

über 2, mit Gewicht -3 direkt, mit Gewicht 6 (bzw. 6-5=1)

Problem: man addiert den Wert so oft, wie #Kanten auf dem kürzesten Weg
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 167
A*-Algorithmus (I) Hart, Nilsson, Raphael (1968)

Spezialfall: suche kürzesten Weg von s zu einem Ziel t

-

Dijkstra-SSSP(G,s,w)

1 initSSSP(G,s,w);
2 Q=V; //let S=V-Q
3 WHILE !isEmpty(Q) DO Dijkstras Algorithmus sucht lokal
-

4 u=EXTRACT-MIN(Q); vom gegenwärtigen Punkt aus

-
5 FOREACH v in adj(u) DO günstigsten nächsten Schritt,
6 relax(G,u,v,w); -

ignoriert aber Zielrichtung

-

15
s t
2 3 2 8 2
4 3 2 1 5 6

7 5 2 0 8
Algorithmus sucht erst
-

in falscher Richtung
-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 168

A*-Algorithmus (II) (nicht-negative Kantengewichte)

Idee: füge Heuristik hinzu, die „vom Ziel her denkt“

A*(G,s,t,w)
1 init(G,s,t,w);
2 Q=V; //let S=V-Q jeder Knoten u bekommt
=

3 WHILE !isEmpty(Q) DO zusätzlich Wert [Link] zugewiesen

-

4 u=EXTRACT-MIN(Q); (Beispiel: Abstand Luftlinie vom Ziel)

5 IF u==t THEN break;
6 FOREACH v in adj(u) DO Minimum über
7 relax(G,u,v,w); [Link] + [Link]

15
s t
2 3 2 8 2
4 3 2 1 5 6

9 8 6 5 1 0

5 2 0 8 10
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 169
A*-Algorithmus (III) (nicht-negative Kantengewichte)

A* findet optimale Lösung, wenn gilt:

1. Heuristik überschätzt nie tatsächliche Kosten:

(insb. [Link]==0)
[Link] ≤ 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡(u,t)
und
2. Heuristik ist monoton, d.h. für alle (u,v) 𝜖𝐸 gilt:
[Link] ≤ w(u,v) + [Link]

15
s t
2 3 2 8 2
4 3 2 1 5 6

9 8 6 5 1 0

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 170

A*-Algorithmus (IV) (nicht-negative Kantengewichte)

„Dijkstra ist A* mit Heuristik 0“

„A* mit monotoner Heuristik ist Dijkstra mit

Kantengewichte sind nicht-
Kantengewichten w(u,v)+[Link] negativ wegen Monotonie
und [Link]=[Link]“

A* und Dijsktra wählen dann jeweils gleichen Knoten, da [Link]+[Link]==[Link],

und am Ende [Link]==[Link]
15
7 s t
2 3 2 8 2
4 3 2 1 5 6
3 5 3 4 1
9 8 6 5 1 0

2|8 0|5 8|9

·

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 171

·
 Maximaler Fluss
in Graphen

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 172

Netzwerkflüsse: Idee

Kanten haben
(aktuellen) Flusswert
-

und (maximale) Kapazität

-

2 0/5 -
Jeder Knoten außer s undO
t
3/5 hat gleichen <
2/3
-

1/3 2 eingehenden und [

-

1/6 ausgehenden Fluss

2/7
-

s 3 2/5 t
4/5
2
2/7 3/8 Ziel:
1/2 0/3 Finde maximalen Fluss
-

von s nach t
-

1/3 2

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 173

Netzwerkflüsse Ein Flussnetzwerk ist ein gewichteter, gerichteter
-

Graph 𝐺 = (𝑉, 𝐸) mit Kapazität(-sgewicht) 𝑐, so

-

dass c u, v ≥ 0 für u, v ∈ 𝐸 und c u, v = 0 für -

(u, v) ∉ 𝐸, mit zwei Knoten 𝑠, 𝑡 ∈ 𝑉 (Quelle und

-

Insbesondere Senke), so dass jeder Knoten vonO 𝑠 aus erreichbar

𝐸 ≥ 𝑉 −1 ist und 𝑡 von jedem Knoten aus erreichbar ist.
-

2 0/5
Ein Fluss 𝑓: 𝑉 × 𝑉 → ℝ für
3/5
1/3 2 2/3 ein Flussnetzwerk 𝐺 =
1/6
(𝑉, 𝐸) mit KapazitätO 𝑐 und
-

s 3 2/5 2/7 Quelle 𝑠 und Senke 𝑡 erfüllt

4/5 t
0 ≤ 𝑓(𝑢, 𝑣) ≤ 𝑐(𝑢, 𝑣) für
2 alle 𝑢, 𝑣 ∈ 𝑉, sowie für alle
-

2/7 3/8 𝑢 ∈ 𝑉 − {𝑠, 𝑡}:

=
1/2 0/3
𝑓(𝑢, 𝑣) = 𝑓(𝑣, 𝑢)
1/3 2 ∈ ∈

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 174

Maximale Flüsse
⑧
Der Wert |𝒇| eines Flusses 𝑓: 𝑉 × 𝑉 → ℝ für
ein Flussnetzwerk 𝐺 = (𝑉, 𝐸) mit Kapazität 𝑐
und Quelle 𝑠 und Senke 𝑡 ist
Beispiel: |𝑓| = 6,
aber nicht maximal,
da z.B. noch +1 * 𝑓 = &
𝑓(𝑠, 𝑣) − 𝑓(𝑣, 𝑠)
∈ ∈
über obere Kanten

2 0/5
Ein Fluss 𝑓: 𝑉 × 𝑉 → ℝ für
O
3/5
b 1/3 2 &
2/3
③
ein Flussnetzwerk 𝐺 =
(𝑉, 𝐸) mit Kapazität 𝑐 und
s
O1/6 3 2/7 Quelle 𝑠 und Senke 𝑡 erfüllt
2/5 4/5 t
& 0 ≤ 𝑓(𝑢, 𝑣) ≤ 𝑐(𝑢, 𝑣) für
2 alle 𝑢, 𝑣 ∈ 𝑉, sowie für alle
&2/7 3/8
1/2 0/3
𝑢 ∈ 𝑉 − {𝑠, 𝑡}:
𝑓(𝑢, 𝑣) = 𝑓(𝑣, 𝑢)
1/3 2 ∈ ∈

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 175

Transformationen neuer Knoten
Eliminiere
3
1/6 antiparallele Kanten 1/6 1/6

3 3
2/5 2/5

s1 Vereinige s1
Quellen
3 t1 und Senken ∞ 3 t1 ∞

∞
s2 s s2 t
↓
3 t2
-
Take
∞
3 t2 ∞ ↓
s3 Quelle s3 Fore
Senke

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 176

Ford-Fulkerson-Methode
Idee: Suche
- Pfad von s nachO
t, der noch erweiterbar (bzgl. des Flusses) ist
- >

Aber: Pfad suchen wir im „Restkapazitäts“-Graph 𝐺 ,

die möglichen Zu- und⑤ &
-

der
-
Abflüsse beschreibt

2 0/5
3/5
1/3 2 2/3
1/6
s 3 2/5 2/7
4/5 t
2
2/7 3/8
1/2 0/3

1/3 2

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 177

Reste
-o
„Wieviel eingehenden Fluss über (𝑢, 𝑣)
könnte man noch zu& 𝑣 hinzufügen?“
Restkapazität:
capacity se

𝑐(𝑢, 𝑣) − 𝑓(𝑢, 𝑣) falls (𝑢, 𝑣) ∈ 𝐸

𝑐 𝑢, 𝑣 = 𝑓(𝑣, 𝑢) falls (𝑣, 𝑢) ∈ 𝐸
0 sonst

„Wieviel abgehenden Fluss über 𝑣, 𝑢

könnte man wegnehmen
𝑐 𝑢, 𝑣
< ( n) , =
Efue-
und damit quasi zu 𝑣 hinzufügen?“
=8−3=5
𝑣
3/8 𝑐 𝑢 ,𝑣 = 1
𝑢 1/2

𝑢‘ Bemerkung: nach Voraussetzung nicht

beide Kanten (𝑢, 𝑣), (𝑣, 𝑢) im Netzwerk,
-

-
daher wohldefiniert

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 178

Restkapazitäts-Graph
𝐺 = (𝑉, 𝐸 ) mit 𝐸 = 𝑢, 𝑣 ∈ 𝑉 × 𝑉 𝑐 𝑢, 𝑣 > 0 }
Restkapazität:

𝑐(𝑢, 𝑣) − 𝑓(𝑢, 𝑣) falls (𝑢, 𝑣) ∈ 𝐸

𝑐 𝑢, 𝑣 = 𝑓(𝑣, 𝑢) falls (𝑣, 𝑢) ∈ 𝐸
0 sonst -
Bemerkung:
Im Restkapazitäts-Graph
*
-

sind antiparallele Kanten

geht 0/5
-
ein erlaubt
-

2 2 5

⑮ et Ge 3/5 2
3/4 2 1 3 1 2
6 3
& 6/6
s 3 s 3 9
>
-
9/10 6
O

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 179

Restkapazitäten ausnutzen
𝐺 = (𝑉, 𝐸 ) mit 𝐸 = 𝑢, 𝑣 ∈ 𝑉 × 𝑉 𝑐 𝑢, 𝑣 > 0 }
Restkapazität:

𝑐(𝑢, 𝑣) − 𝑓(𝑢, 𝑣) falls (𝑢, 𝑣) ∈ 𝐸

𝑐 𝑢, 𝑣 = 𝑓(𝑣, 𝑢) falls (𝑣, 𝑢) ∈ 𝐸
0 sonst

+2
+2 0/5
2 2 5
3/5 2
3/4 t 1 3 1 t
3
6/6
s 3 s 3 9
9/10 6

Finde Pfad von -𝑠 zu 𝑡 in 𝐺 und erhöhe (für Kanten in 𝐺) bzw. erniedrige

-

(für Nicht-Kanten) um Minimum 𝑐 𝑢, 𝑣 aller Werte auf dem Pfad in 𝐺

-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 180

Ford-Fulkerson-Algorithmus
Ford-Fulkerson(G,s,t,c)

1 FOREACH e in E DO [Link]=0;
2 WHILE there is path p from s to t in 𝑮𝐟𝐥𝐨𝐰 DO
Z.B. wenn
3 𝒄𝐟𝐥𝐨𝐰 𝒑 = 𝒎𝒊𝒏 𝒄𝐟𝐥𝐨𝐰 𝒖, 𝒗 𝒖, 𝒗 𝒊𝒏 𝒑 }
in jeder Iteration
4 FOREACH e in p DO
der Fluss nur
5 IF e in E THEN um 1/𝑢 = 0.1
6 [Link]=[Link]+ 𝒄𝐟𝐥𝐨𝐰 𝒑 erhöht wird
7 ELSE
8 [Link]=[Link]- 𝒄𝐟𝐥𝐨𝐰 𝒑 Laufzeit = 𝑂(|𝐸| 𝑢 |𝑓 ∗ |)
Pfadsuche z.B. per BFS oder DFS
(wobei 𝑓 ∗ maximaler Fluss
und Fluss um bis zu 1/𝑢 pro Iteration wächst)

Laufzeit = 𝑂(|𝑉| |𝐸| )

(mit Verbesserung
nach Edmonds-Karp)
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 181
Ford-Fulkerson-Algorithmus: Beispiel (I)
auf dem
Ford-Fulkerson(G,s,t,c)
Weg
1 FOREACH e in E DO [Link]=0; Sub trohe
2 WHILE there is path p from s to t in 𝑮𝐟𝐥𝐨𝐰 DO
3 𝒄𝐟𝐥𝐨𝐰 𝒑 = 𝒎𝒊𝒏 𝒄𝐟𝐥𝐨𝐰 𝒖, 𝒗 𝒖, 𝒗 𝒊𝒏 𝒑 }
4 FOREACH e in p DO
5 IF e in E THEN
6 [Link]=[Link]+ 𝒄𝐟𝐥𝐨𝐰 𝒑
7 ELSE Restkapazitäts-
8 [Link]=[Link]- 𝒄𝐟𝐥𝐨𝐰 𝒑 graph

s
+4
0/10 +4 10
0/8 2 2 8 2 2
0/10 10

①
+4 0/4 4
s 0/4 0/6 t s 4 6 t

0/5 0/7 5 7
+4 2 2
0/2 𝒄𝒇𝒍𝒐𝒘 𝒑 =4 2

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 182

Ford-Fulkerson-Algorithmus: Beispiel (II)
Ford-Fulkerson(G,s,t,c)

1 FOREACH e in E DO [Link]=0;
2 WHILE there is path p from s to t in 𝑮𝐟𝐥𝐨𝐰 DO
3 𝒄𝐟𝐥𝐨𝐰 𝒑 = 𝒎𝒊𝒏 𝒄𝐟𝐥𝐨𝐰 𝒖, 𝒗 𝒖, 𝒗 𝒊𝒏 𝒑 }
4 FOREACH e in p DO
5 IF e in E THEN
6 [Link]=[Link]+ 𝒄𝐟𝐥𝐨𝐰 𝒑
7 ELSE Restkapazitäts-
8 [Link]=[Link]- 𝒄𝐟𝐥𝐨𝐰 𝒑 graph

4/10 6
+2
0/8 2 2 8 2 2
4/10 4 6
-2 0/4 4 4
s 4/4 0/6 t s 1 4 t
6

0/7 4 7
4/5
2 +2 2
0/2 𝒄𝒇𝒍𝒐𝒘 𝒑 = 𝟐 2
+2
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 183
Ford-Fulkerson-Algorithmus: Beispiel (III)
Ford-Fulkerson(G,s,t,c)

1 FOREACH e in E DO [Link]=0;
2 WHILE there is path p from s to t in 𝑮𝐟𝐥𝐨𝐰 DO
3 𝒄𝐟𝐥𝐨𝐰 𝒑 = 𝒎𝒊𝒏 𝒄𝐟𝐥𝐨𝐰 𝒖, 𝒗 𝒖, 𝒗 𝒊𝒏 𝒑 }
4 FOREACH e in p DO
5 IF e in E THEN
6 [Link]=[Link]+ 𝒄𝐟𝐥𝐨𝐰 𝒑
7 ELSE Restkapazitäts-
8 [Link]=[Link]- 𝒄𝐟𝐥𝐨𝐰 𝒑 graph
+6 6
+6 4/10 +6
2/8 2 2 6 2 2
4/10 4 6
2
0/4 4 4
s 2/4 0/6 t s 1 2 2 t
6
5
2/7 4
4/5 2
2 2
2/2 𝒄𝒇𝒍𝒐𝒘 𝒑 = 𝟔 2

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 184

Ford-Fulkerson-Algorithmus: Beispiel (IV)
Ford-Fulkerson(G,s,t,c)
Kein Pfad
1 FOREACH e in E DO [Link]=0; mehr im
2 WHILE there is path p from s to t in 𝑮𝐟𝐥𝐨𝐰 DO
Restkapazitäts-
3 𝒄𝐟𝐥𝐨𝐰 𝒑 = 𝒎𝒊𝒏 𝒄𝐟𝐥𝐨𝐰 𝒖, 𝒗 𝒖, 𝒗 𝒊𝒏 𝒑 }
4 FOREACH e in p DO Graph
5 IF e in E THEN
6 [Link]=[Link]+ 𝒄𝐟𝐥𝐨𝐰 𝒑
7 ELSE Restkapazitäts-
8 [Link]=[Link]- 𝒄𝐟𝐥𝐨𝐰 𝒑 graph

10/10 10
8/8 2 2 2 2
10/10 8
0/4 4 10
s 2/4 0/6 t s 1 2 2 t
6
5
2/7 4
4/5 2
2 2
2/2 2

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 185

Max-Flow Min-Cut Theorem (I) Korrektheit des Ford-Fulkerson-Algorithmus

Sei 𝑓: 𝑉 × 𝑉 → ℝ Fluss für ein Flussnetzwerk 𝐺 = (𝑉, 𝐸) mit Kapazität 𝑐

und Quelle 𝑠 und Senke 𝑡. Dann sind äquivalent:

1. 𝑓 ist ein maximaler Fluss für 𝐺

2. Der Restkapazitätsgraph 𝐺 enthält keinen erweiterbaren Pfad
3. |𝑓| = min 𝑐(𝑆, 𝑉 − 𝑆) mit 𝑠∈𝑆 und 𝑡∈𝑉−𝑆

10/10 10
8/8 2 2 2 2
10/10 8
0/4 4 10
s 2/4 0/6 t s 1 2 2 t
6
5
2/7 4
4/5 2
2 2
2/2 2

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 186

Max-Flow Min-Cut Theorem (II)
Sei 𝑓: 𝑉 × 𝑉 → ℝ Fluss für ein Flussnetzwerk 𝐺 = (𝑉, 𝐸) mit Kapazität 𝑐
und Quelle 𝑠 und Senke 𝑡. Dann sind äquivalent:

1. 𝑓 ist ein maximaler Fluss für 𝐺

2. Der Restkapazitätsgraph 𝐺 enthält keinen erweiterbaren Pfad
3. |𝑓| = min 𝑐(𝑆, 𝑉 − 𝑆) mit 𝑠∈𝑆 und 𝑡∈𝑉−𝑆

wobei
10/10
8/8 2 2
10/10 𝑐 𝑆, 𝑉 − 𝑆 = ∑ ∈ ∑ ∈ 𝑐(𝑢, 𝑣)
0/4
s 2/4 0/6 t für 𝑠 ∈ 𝑆 und 𝑡 ∈ 𝑉 − 𝑆 die
Kapazität eines Schnitts (𝑺, 𝑽 − 𝑺)
4/5 2/7 ist.
2
2/2

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 187

Beispielanwendung: Bipartites Matching (I)

Käufer Verkäufer
2 2
bipartiter Graph:
Knotenmenge zerfällt in
2 2 zwei disjunkte Mengen,
so dass Kanten nur
zwischen den Mengen
2 2

maximales bipartites Matching:

2 2
Finde maximale Anzahl
von Kanten, so dass
jeder Käufer genau einem
2 2
Verkäufer zugeordnet wird
könnte Ware vom
Verkäufer kaufen

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 188

Beispielanwendung: Bipartites Matching (II)

2 2 Kapazität = 1
für jede Kante

2 2

Fluss=1 sagt,
s 2 2 t Kante aktiv

2 2
Wert des Flusses
gibt an, wie viele
aktive Kanten aus
2 2
s ausgehen bzw.
wie viele in t ankommen

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 189

 Zeigen Sie, dass der Wert |𝑓| eines Flusses
–definiert als der Netto-Ausfluss der Quelle- auch
das eingehende Netto in der Senke beschreibt.

Angenommen, Sie beschreiben ein Job-Scheduling-Problem

per Dag, wobei jeder Job eine gewisse Zeit benötigt,
bevor er beendet ist. Wie können Sie 11
mit Hilfe des Dag-SSSP-Algorithmus 6
bestimmen, wie lange ihr D C
Projekt insgesamt braucht?

A B
3
4
E
2
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 06 Graph Algorithms | 190