2.6.1 Deﬁnition und Darstellung 2.6.2 Ausspähen von ......• Auf dem Weg von u nach v durch T gibt es eine Kante (x,y) die den Schnitt kreuzt 14 u x y v A T Der Weg existiert,

Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer

2.6 Graphen

2.6.1 Definition und Darstellung 2.6.2 Ausspähen von Graphen 2.6.3 Minimal spannende Bäume 2.6.4 Kürzeste Pfade 2.6.5 Maximaler Fluss

1


2.6.3 Minimal spannende Bäume

2.6.3.1 Generischer Algorithmus 2.6.3.2 Prims Algorithmus 2.6.3.3 Kruskals Algorithmus

2


Minimal Spannende Bäume

•  Gegeben sei ein zusammenhängender, ungerichteter, gewichteter Graph G=(V,E) mit Gewichtsfunktion w:E→R.

•  Gesucht ist ein Spannbaum S⊆E der minimiert, der sogenannte MST.

3


Minimal Spannende Bäume

4

5

1

7

3

Kein Baum!

5

1

7

3

Nicht spannend!

5

1

7

3

Nicht minimal!

5

1

7

3

MST


Generischer Algorithmus

•  Greedy-Strategie: Füge nach und nach Kanten zu einer anfangs leeren Kantenmenge A hinzu, und zwar unter Beachtung der folgenden Invariante: •  A ist Teilmenge eines MST (∗)

5



•  Sei A eine Menge von Kanten, die die Invariante (∗) erfüllt. Eine Kante e heißt sicher für A, falls A∪{e} ebenfalls die Invariante (∗) erfüllt.

6



•  GENERICMST( G, w ) A ← ∅ while A ist kein MST do suche eine sichere Kante e für A A ←A ∪{e} return A

7



•  Ein Schnitt eines ungerichteten Graphen G=(V,E) ist eine Menge S⊆V

•  Eine Kante (u,v) kreuzt den Schnitt S falls einer ihrer Endpunkte in S und der andere Endpunkt in V−S liegt.

8



9

kreuzende Kanten



•  Ein Schnitt respektiert A, falls keine Kante aus A den Schnitt kreuzt.

•  Eine kreuzende Kante heißt leicht, falls ihr Gewicht minimal unter allen kreuzenden Kanten ist.

10



11

leichte Kante

3 9



•  Satz: A erfülle die Invariante (∗). S sei ein Schnitt der A respektiert und (u,v) eine leichte Kante, die S kreuzt. Dann ist (u,v) sicher für A.

12



•  Sei T ein MST der A enthält, aber nicht (u,v)

13

u

x

y

v

A T

Würde er (u,v) enthalten, so wären wir schon fertig!



•  Sei T ein MST der A enthält, aber nicht (u,v) •  Auf dem Weg von u nach v durch T gibt es eine

Kante (x,y) die den Schnitt kreuzt

14

u

x

y

v

A T

Der Weg existiert, da T ein spannend ist. Er ist eindeutig, da T ein Baum ist.




Kante (x,y) die den Schnitt kreuzt •  T’ = T − {(x,y)} ∪ {(u,v)} ist ein MST, denn

w(T’) = w(T) − w(x,y) + w(u,v) ≤ w(T)

15

u

x

y

v

A T’




Kante (x,y) die den Schnitt kreuzt •  T’ = T − {(x,y)} ∪ {(u,v)} ist ein MST •  Wegen A ⊆ T und (x,y) ∉ A folgt A ∪ {(u,v)} ⊆ T’,

also ist (u,v) sicher für A

16

u

x

y

v

A∪{(u,v)} T’




17


Prims Algorithmus

•  Die Kanten in A bilden einen Baum. Jeder Knoten u erhält einen Zeiger p[u] auf seinen Vater im MST.

•  Der A respektierende Schnitt S ist gegeben durch S = { u : (u,v) ∈ A }

18


Prims Algorithmus

•  Knoten u außerhalb von S erhalten einen Schlüssel, der das minimale Gewicht einer Kante angibt, die u mit S verbindet (∞∞ falls es solch eine Kante nicht gibt)

19

3

∞

3

9 S

V−S

5


Prims Algorithmus

20

∞

0 ∞

∞

∞

∞

∞

∞

∞

4

8 7

9 14

10

2

7 6

1

2

8

11 4


Prims Algorithmus

21

4

0 ∞

8

∞

∞

∞

∞

∞

4

8 7

9 14

10

2

7 6

1

2

8

11 4


Prims Algorithmus

22

4

0 ∞

8

8

∞

∞

∞

∞

4

8 7

9 14

10

2

7 6

1

2

8

11 4


Prims Algorithmus

23

4

0 2

8

8

7

∞

∞

4

4

8 7

9 14

10

2

7 6

1

2

8

11 4


Prims Algorithmus

24

4

0 2

7

8

7

6

∞

4

4

8 7

9 14

10

2

7 6

1

2

8

11 4


Prims Algorithmus

25

4

0 2

7

8

7

2

10

4

4

8 7

9 14

10

2

7 6

1

2

8

11 4


Prims Algorithmus

26

4

0 2

1

8

7

2

10

4

4

8 7

9 14

10

2

7 6

1

2

8

11 4


Prims Algorithmus

27

4

0 2

1

8

7

2

10

4

4

8 7

9 14

10

2

7 6

1

2

8

11 4


Prims Algorithmus

28

4

0 2

1

8

7

2

9

4

4

8 7

9 14

10

2

7 6

1

2

8

11 4


Prims Algorithmus

29

4

0 2

1

8

7

2

9

4

4

8 7

9 14

10

2

7 6

1

2

8

11 4


Prims Algorithmus

•  PRIM(G,w,r) for each u ∈ V do key[u] ← ∞ p[u] ← NIL key[r] ← 0 Q ← V while Q not empty do u ← ExtractMinimum(Q) for each v ∈ Adj[u] do if v ∈ Q and w(u,v) < key[v] then p[v] ← u key[v] ← w(u,v)

30


Prims Algorithmus


31

O(V)


Prims Algorithmus

32

O(V) Heap Aufbau!



Prims Algorithmus

33

V Läufe



Prims Algorithmus

34

O(log V)

Entfernen eines Elements aus dem Heap



Prims Algorithmus

35

O(E)

Durchläufe insgesamt



Prims Algorithmus

36

O(log V)

Heap muss aktualisiert werden



Prims Algorithmus

37

O(V×log V + E×log V)

O(V)



Prims Algorithmus

•  Nach der Ausführung von Prim(G,w,r) ist der MST gegeben durch A = { (u,p[u]) : u ∈ V − {r} }

•  Implementierung von Prims Algorithmus z.B. mit binärem Heap

38


Prims Algorithmus

•  Implementiert man Prims Algorithmus mittels eines binären Heaps, so ist der Aufwand

O(E×log V) •  Implementiert man Prims Algorithmus

mittels eines Fibonacci-Heaps, so ist der Aufwand

O(E+V×log V)

39




40


Kruskals Algorithmus

•  Die Kanten in A bilden einen Wald. Jeder Knoten u in A erhält einen Zeiger p[u] auf seinen Vater im MST.

•  Der A respektierende Schnitt S ist gegeben durch S = { u : (u,v) ∈ A }

•  In jedem Schritt wird die Kante mit kleinstem Gewicht gesucht, die zwei Bäume aus A verbindet. Diese Kante wird zu A hinzugefügt.

41



42

4

8 7

9 14

10

2

7 6

1

2

8

11 4



43

4

8 7

9 14

10

2

7 6

1

2

8

11 4



44

4

8 7

9 14

10

2

7 6

1

2

8

11 4



45

4

8 7

9 14

10

2

7 6

1

2

8

11 4



46

4

8 7

9 14

10

2

7 6

1

2

8

11 4



47

4

8 7

9 14

10

2

7 6

1

2

8

11 4



48

4

8 7

9 14

10

2

7 6

1

2

8

11 4



49

4

8 7

9 14

10

2

7 6

1

2

8

11 4



50

4

8 7

9 14

10

2

7 6

1

2

8

11 4



•  Kruskal(G,w) A ← ∅ for all v ∈ V do MakeSet(v) sort E into non-decreasing order for each (u,v) ∈ E do if Find(u) ≠ Find(v) then A ← A ∪ {(u,v)} Union(u,v) return A

51



•  Kruskal(G,w) A ← ∅ for all v ∈ V do MakeSet(v) sort E into non-decreasing order for each (u,v) ∈ E do if Find(u) ≠ Find(v) then A ← A ∪ {(u,v)} Union(u,v) return A

52

O(E×log E)

V × MakeSet()

O(E) × Find(), Union()



•  Aufwand – Sortieren: O(E×log E) = O(E×log V) – Union-Find •  V × MakeSet() •  O(E) × FindSet(), Union() ➡ O((V+E)×a(V)) = O(E×logV)

➡ Gesamtaufwand: O(E×log V)

53

E < V2 → log E = O(log V)





54

E > V−1 und a(V) = O(log V)

Aufwand für Union-Find





55

Documents

2.6.1 Deﬁnition und Darstellung 2.6.2 Ausspähen von ......• Auf dem Weg von u nach v durch T gibt es eine Kante (x,y) die den Schnitt kreuzt 14 u x y v A T Der Weg existiert,