Post on 22-Jan-2021
transcript
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 1
7. Graphenalgorithmen
Grundlagen:1. Paar (V, E) heißt gerichteter Graph G, wobei
V endl. Menge von Knoten undeine endl. Menge von Kanten ist.
Element e = (v,w)heißt Kante von v nach w(„ v w “)v ist Startknoten von ew ist Zielknoten von ew ist Nachbarknoten von v (w ist adjazent zu v)
1E∈
2
43
5
VVE ×⊆
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 2
2. Pfad in G ist Folge (v0, ..., vk) von Knoten mit und (vi, vi+1) für
0≥kE∈ .10 −≤≤ ki
Länge des Pfades ist k.
Falls v0 = vk und so heißt der Pfad Kreis bzw. Zyklus.
Falls für alle so heißt der Pfad einfach.
Falls es Pfad von v nach w in G gibt, so schreibt man
Gerichteter Graph heißt zyklisch, falls er Kreis enthält;sonst azyklisch.
,1≥k
ji vv ≠ ,ji ≠
. * wvG→
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 3
7.1 Darstellung von GraphenAnnahme: V = {1, 2, ..., n}, G = (V, E), n = |V|.
Zwei Darstellungsarten sind üblich:1. Darstellung: Adjazenzmatrix
( ) ∈
=sonst. , 0
falls , 1:
Ei,jaij
Bsp.: 1
24
53
1 2 3 4 5
1 0 0 0 0 12 1 0 0 0 13 0 0 0 0 04 0 0 0 0 05 0 0 1 0 0
( ) ni,j , aA ij ≤≤= 1
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 4
Bei ungerichteten Graphen ist die Adjazenzmatrixsymmetrisch:
1
2
5
{ } ∈
=sonst. , 0
falls , 1:
Ei,jaijhier:4
31 2 3 4 5
1 0 1 0 0 12 1 0 0 0 13 0 0 0 0 14 0 0 0 0 05 1 1 1 0 0
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 5
Platzbedarf: O(n2)ist günstig, falls
Aber: Oft sind Graphen dünn, d.h.
.: 2nEm ≈=
( ). nOm ≈
Bsp.:Zahl der Kanten in Bäumen mit n Knoten ist n – 1.
Planare Graphen: Graph heißt planar, falls er in Ebenegezeichnet werden kann, ohne dass sich Kantenüberkreuzen.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 6
Zwei nicht-planare, ungerichtete Graphen:
K3,3 K5
(„vollständiger“ bipartiterGraph mit 3 und 3 Knoten)
Mitteilung: Ein planarer Graph mit n>2 Knoten enthältmaximal 3n – 6 Kanten.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 7
2. Darstellung: Adjanzenzlisten
Speichere für jeden Knoten v seine „Nachbarn“:
G = (V, E) gerichtet:
( ) ( ){ }( ) ( ){ }EwvVwv
EvwVwv
∈∈=
∈∈=
, OutAdj
, InAdj
G ungerichtet:
( ) { }{ }Ev,w Vwv ∈∈= Adj
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 8
Im vorigen Beispiel (gerichtet):
InAdj: OutAdj:2 51
12345
12345
55
21 3
Platzbedarf: O(n + m)
Nachteil: Zugriffszeit auf Kante abhängig von Listenlänge,d.h. Knotengrad:Eingangsgrad indeg(v) eines KnotenAusgangsgrad outdeg(v) eines Knoten(analog für ungerichtete Graphen).
( ) ( ){ } , , , Evwvwv ∈=( ) ( ){ } , , Ewvwvv ∈=
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 9
Graph G = (V, E) heißt Baum, falls
a) V enthält genau einen Knoten v0 mit indeg(v0) = 0.
b)
c) G ist azyklisch.
{ } ( ) 1indeg :\ 0 =∈∀ vvVv
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 10
7.2 Topologisches Sortieren
Sei G = (V, E) gerichteter Graph.Abbildung num: V {1, ..., n} mit n = |V| heißttopologische Sortierung von G, falls num(v) < num(w)für alle ( ) . , Ewv ∈
Bsp.: 1
2
5
42 1 5 3 4
num: 1 2 3 4 53
es gibt keinetopologischeSortierung!
1 3
2
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 11
Lemma:Gerichteter Graph G = (V, E) besitzt genau danneine topologische Sortierung, wenn G azyklisch ist.
Beweis:
Sei G zyklisch. Dann ist etwa (v0, ..., vk),ein Kreis. Für eine topologische Sortierung mussaber gelten:
num(v0) < num(v1) < ... < num(vk) = num(v0).
Widerspruch!!
:""⇒,1≥k
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 12
:""⇐Sei G azyklisch.
Beh.: G enthält Knoten v mit indeg(v) = 0.
Wir finden solchen Knoten v wie folgt.
Starte mit bel. Knoten w und gehe entlang eingehenderKanten „rückwärts“. Da Graph azyklisch und endlich,wird kein Knoten auf diesem „Rückweg“ zweimal besuchtund daher terminiert dieser Prozess mit einem Knoten vmit indeg(v) = 0.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 13
Jetzt zur topologischen Sortierung:Beweis per Induktion über Knotenzahl:|V| = 1: trivial.
|V| > 1: Wähle (gemäß Beh.) v mit indeg(v) = 0.Entferne v und sortiere den Restgraph G´ topologischinduktiv, d.h.:
Sei num´ : V´ {1, ..., |V´|} top. Sortierung für G´.Dann ergibt sich die top. Sort. num durch
( ) ( )
=≠+
=v. wv ww
wfalls 1, falls 1,num´
num
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 14
Grundalgorithmus für topologisches Sortieren:
count 0;while mit indeg(v) = 0 do
count ++;num(v) count;streiche v und alle von v ausgehenden Kanten aus G;
odif count < |V|
then ausgabe(G zyklisch!)fi
Vv∈∃
Komplexitätsanalyse:Problem: Test auf Existenz eines Knotens v mit indeg(v) = 0.Lösung: Merke alle Knoten mit indeg = 0 in Menge ZERO.
Führe für jeden Knoten Buch über Anzahl jeweilseinmündender Kanten.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 15
Algorithmus TOPSORT:
(1) ZERO Ø;
(2) for all do INDEG[v] 0 od;(3) for all do INDEG[target(e)] ++ od;(4) for all do(5) if INDEG[v] = 0 then ZERO ZERO fi(6) od(7) count 0;
Fortsetzung nächste Folie
Vv∈Ee∈Vv∈
{ }v∪
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 16
(8) while ZERO Ø do(9) wähle und streiche(10) count ++;(11) num[v] count;(12) for all do(13) INDEG[w] – – ;(14) if INDEG[w] = 0 then ZERO ZERO fi(15) od(16) od;(17) if count < |V| then ausgabe(G zyklisch!) fi
{ }w∪
( ) Ewv ∈,
≠; ZERO∈v
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 17
Satz:Topologische Sortierung eines gerichtetenGraphen G = (V, E) kann in Zeit O(n + m)(Linearzeit!) berechnet werden.Hierbei: n = |V|, m = |E|.
Beweis: Die Korrektheit folgt unmittelbar mit dem Lemma.Zur Komplexität: Übungsaufgabe!
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 18
7.3 Kürzeste/Billigste Wege in Graphen
Sei G = (V, E) gerichteter Graph mit Kostenfunktionc: E R, ein sogenanntes Netzwerk.
Sei p = (v0, ..., vk) Pfad von v0 = v nach vk = w.Dann heißt
Kosten des Pfades von v nach w.
dist(v, w) = inf {c(p) | p ist Pfad von v nach w}heißt Entfernung.
( ) ( )∑−
=+=
1
01,:
k
iii vvcpc
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 19
Beispiel:
dist(1,2) = – 1dist(3,1) =dist(3,4) = – , da
Pfad (3,4,(5,6,4)i) Kosten 3 – ihat für alle
∞∞
.0≥i
negativer Zyklus
1
4
5
2
3
6
– 1
2
3
2
3– 6
4
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 20
3 grundsätzliche Problemstellungen:
single pair shortest paths(kürzeste Wege zwischen einem Knotenpaar)
single source shortest paths(kürzeste Wege von einem Knoten aus)
all pairs shortest paths(kürzeste Wege zwischen allen Knotenpaaren)
1
2
3
Bemerkung:Unbekannt, ob leichter/effizienter lösbar als .1 2
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 21
7.3.1 Single Source Shortest Paths
Sei s der „Quellknoten“. G = (V, E).Gesucht für alle Vu∈
( ) ( )∞
=sonst. ,,dist
,in nach vonPfadkein falls ,:
us Gu s
uδ
Lemma:Sei . Dann gilt:
i) gdw. u ist erreichbar aus negativemZyklus, der von s aus erreichbar ist.
ii) billigster einfacher Pfad vons nach u mit Kosten
Vu∈( ) −∞=uδ
( ) ∃⇒∈Ruδ. )(uδ
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 22
Beweis:
i) klar!
Sei und sei p ein kürzester Weg von
s nach u mit c(p) < – c.
Dann muss p Zyklus q enthalten, d.h. p ist nichteinfach. Wäre nun so könnten wirq aus p entfernen und so p verkürzen/verbilligen.
:""⇒
:""⇐
( )∑∈
=Ee
ecc :
( ) ,0≥qc
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 23
ii) Falls so gibt es Pfad von s nach u.
Wir zeigen:
Sei p* billigster einfacher Weg von s nach u.Ist Behauptung falsch, dann gibt es einen nichteinfachenWeg q von s nach u mit c(q) < c(p*).
Durch Entfernen des Zyklus aus q entsteht kürzererWeg q´ und da Zyklus (gemäß i) ) nicht negativ ist, folgtc(q´) ≤ c(q) < c(p*), ein Widerspruch.
( ) , R∈uδ
( ) ( ){}.einfachist und
nach von Pfadist min p
usp p cu =δ
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 24
7.3.1.1 Der geg. Graph G = (V, E) ist azyklisch.
Bsp.:
s
2
3
5
4
62
– 12
3
5
1
2
( ) ( ) ( )( ) { }( )( ) { } 211 1,7 2,5inf6
5,3251,7,1inf4
1,3 2,2 0,
=+++==+=
==−===
δδδ
δδδ s
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 25
Nachfolgender Algorithmus setzt voraus, dass Graphtopologisch sortiert ist, „also“ V = {1, 2, ... , n}.
Algorithmus:
d(s) 0;Pfad(s) s; (* Pfad als Liste repräsentiert *)for all do d(v) od;for v = s + 1 to n do
d(v) min {d(u) + c(u,v) | (u,v) E}(* u* sei hierbei ein optimaler u-Wert *)
Pfad(v) Pfad(u*) ° vod
{ }sVv \∈ ∞
∈
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 26
Satz:Nach Ausführung von obigem Algorithmus gilt
1)2) Pfad(v) ist billigster Weg
von s nach v.3) Algorithmus hat Laufzeit O( n + m), wobei
n = |V| und m = |E|.
( ) ( ) Vvvvd ∈∀= δ( ) ⇒∞<vd
Beweis:Korrektheit ( 1) + 2) ): Induktion über v
v < s: da v von s aus nicht erreichbar.da nach Init. nicht mehr verändert
v = s: Pfad(s) = s ist einziger Weg.
( ) ,∞=vδ( ) ,∞=vd
( ) ( ) .0== vdvδ
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 27
v > s: SeiNach Ind´vor. gilt für schon
und Pfad(u) ist berechnet.
Ist Ø, dann
Ist Ø, so wähle u* mitminimal.
Falls d(u*) = , so auchSonst ergibt sich billigster Weg nach vdurch Konkatenation und
( ) ( ){ }. , :In EvuVuv ∈∈=( )vu In∈
( ) ( )uud δ=
( ) =vIn ( ) ( ) .∞== vvd δ
( ) ≠vIn( ) ( )vucud *,* +
∞ ( ) ( ) == vvd δ .∞
( ) ( ) ( ) ( ).*,* vdvucuv =+= δδ
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 28
Laufzeit:Topologisches Sortieren kostet Zeit O( n + m ).
Initialisierung: O(n)
„Hauptteil“: Komplexität wird i.w. bestimmt durch
also O( n + m ).
( ) , In mvVv
=∑∈
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 29
7.3.1.2 Alle Kantenkosten nichtnegativ (d.h. ),Zyklen erlaubt
0)(, ≥∈∀ ecEe
Dijkstras Algorithmus:Nachfolgend nur Kosten kürzester Pfad berechnet; eigentliche Pfadberechnung analog vorher.
Idee: Für Menge S von Knoten mit bereits bestimmtem kürzesten Pfad muss es Knoten geben, sodass kürzester Wegvon s nach x über die Knoten in S geht und dann noch eineKante aus S nach x.
SVx \∈
Genauer: x ist Knoten, der für alle den Ausdruckminimiert.
Su∈( ) ( )xucu ,+δ
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 30
Nachfolgend:( )
haben in Nachbarn die ,\ ausKnoten der Menge:.δbekanntemmit Knoten der Menge:
SSVSuuS
=′=
Algorithmus:{ } ( )
( )
( ) ( )( )
( ) ; do all for
;, ;do all for;OutAdj
;0 ;
∞←′′∪−∈
←′′∈
←′←←
udSSVuuscud
SusS
sdsS
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 31
( ) ( ){ }{ }
( )
{ }( ) ( ) ( ) ( ){ }
odod
fi ,,min
; then if
do OutAdj all for ;\ ; ;
Wert;- minimalemmit ausKnoten derjenige do o while
uxcxdududuSS
Suxu
xSSxSSxdxd
dSxS
+′←′∪′←′
∉∈
′←′∪←
′←
′′←/≠′
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 32
Beispiel (Dijkstra, Ungerichteter Graph):S = {s, D, C},S´={E, B, A}d(C) = 2,d´(B) = 5,d´(E) = 3,d´(A) = 3
S = {s},S´={C, D, E}d(s) = 0,d´(C) = 2,d´(D) = 1,d´(E) = 5
3 A B
C D
s E
4
1
5
3
1
4
1
3
1
2
2 2 S = {s, D, C, A},S´={E, B}d(A) = 3 d´(B) = 4,d´(E) = 3
S = {s, D},S´={C, E, B}d(D) = 1,d´(C) = 2,d´(E) = 3,d´(B) = 5
0
S = {s, D, C, A, E},S´={B}d(E) = 3 d´(B) = 4,
S = {s, D, C, A, E, B},d(B) = 4,
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 33
Beispiel (Dijkstra, Gerichteter Graph):
sB
A
CF
E
G
H
I
J
D
L
K
1
2 3
1
3
53
2
4
6
7 1
3
63
53
12
4
12
110
2
10
72
1
2
4 4
8
7
1
1
5
1050
∞
10 9 92
85 5 9 12 11 11
9
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 34
Lemma:Sei so gewählt, dass minimal ist.Dann gilt
Sx ′∈ ( )xd ′( ) ( ).xxd δ=′
Beweis:Sei p ein billigster Weg von s nach x derart, dass alle Knoten (bis auf x) in S liegen.
Angenommen, es gäbe einen billigeren Weg q von s nach x.
q muss einen ersten Knoten v in haben und nach Wahl von x ist ( ) ( ).xdvd ′≥′
SV \
Da alle Kanten nichtnegativ sind, gilt aber( ) ( ) ( ) ( ) ( ),pcxdxdvdqc ==′≥′≥
ein Widerspruch.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 35
Zur Laufzeit:Implementiere S und als Bitvektorenund d und als Arrays.
S ′d ′
•Aufwand für „ “:
•n-maliges Minimieren über
( )xu OutAdjallfor ∈
( ) ( ).OutAdj nmOxVx
+=∑∈
( ).²: nOS ′
Insgesamt ergibt sich Laufzeit O(n²+m), für dichte Graphen ausreichend. ( )²nm ≈
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 36
Alternativ:
Speichere in Heap (balancierter Baum), gemäß-Werten geordnet.
Damit Laufzeit O((m+n)log n),da nun Einfügenund Löschen in
Für dünne Graphen ist dies eine Verbesserung.
S ′d ′
( ) kostet. Zeit logje nOS ′
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 37
Satz:Mit Hilfe des Algorithmus von Dijkstra läßt sich dasSingle Source Shortest Path Problem in Laufzeiten ( ) ( )( ) lösen.logbzw. ² nnmOnO +
Mitteilung:Mit Hilfe sogenannter Fibonacci-Heaps läßt sich die Laufzeit des Algorithmus von Dijkstra asymptotischzu O(n log n + m) verbessern.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 38
7.3.1.3 Negative Kantenkosten erlaubt, aber keine negativen Zyklen.
Bellman-Ford-AlgorithmusDas „Entspannen einer Kante (v,w)“ bezeichnen wir mitRelax ((v,w)):
( ) ( ) ( ) ( ){ }wvcvdwdwd ,,min +←
Offensichtlich: Entspannen einer Kante erhöht keinen d-Wert
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 39
Lemma:Falls für alle vor dem Entspannen einer beliebigen Kante (v,w) gilt, dass , dann gilt dies auch hinterher.
Vu∈( ) ( )uud δ≥
Beweis:Jeder Weg von s nach v zusammen mit Kante (v,w)ergibt Weg von s nach w.
( ) ( ) ( )., Deshalb wwvcv δδ ≥+
( ) ( ) ( ) ( )( ) ( ) ( )( ) ( )
, :Weiterhin
wdwwvcvdw
v,wcvdv,wcv
≤⇒+≤⇒
+≤+
δδδ
falls (v,w) „echt“ relaxiert.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 40
Algorithmus:( )
( )
odKanten Entspanne domöglich while
do all for
;0
∞←≠
←
vdsv
sd
„ “
Beobachtung: d(u) wird immer kleiner, unterschreitet aber nie . ( )uδ
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 41
Offen bleibt noch die Frage nach der „Entspannungs-Reihenfolge“,sodass d schnell gegen δ konvergiert.
Lemma:Sei und sei und sei (v, w) die letzte Kanteauf dem billigsten Weg von s nach w.
Dann gilt:Falls (v,w) entspannt wird, nachdem d(v) = δ(v) geworden ist, so ist danach d(w) = δ(w).
Vw∈ ∞<)(wδ
Beweis: Übung!
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 42
Algorithmus:( )
( )
( )( )( );,Relax
do , all for do 1 to 1 for
; do all for
;0
wvEwv
nivd
svsd
∈−←
∞←≠
←
Bem.: im Beispiel spieltdie Reihenfolge der Kantenin der for all-Schleife eineRolle, die Aussagen gelten aber für alle Reihenfolgen
Lemma:Für i=0,..., n-1 gilt:
Nach dem i-ten Durchlauf der for-Schleife ist für alle , für die es einen billigsten Pfad der Länge ivon s nach w gibt.
( ) ( ) δ wwd =Vw∈
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 43
Beweis:Induktion über i:
( ) ( ) gibt.Zykelnegativen keineesda,δ :0 ssdi ==
:1+→ iiSei w der Knoten mit billigstem Weg von s nach w derLänge i+1 und sei (v,w) die letzte Kante auf diesem Weg.
Also gibt es billigsten Weg von s nach v der Länge i undnach Induktionsannahme ist nach dem i-ten Durchlauf der for-Schleife . Im (i+1)-ten Durchlauf wird insbesondere (v,w) entspannt:
( ) ( )vδ=vd
( ) ( ) ( )( )( ) ( )( )( )w
wvcvwvcvdwd
δ,δ,
=+=+=⇒
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 44
Korollar:Nach dem (n-1)-ten Schleifendurchlauf gilt für alle v aus V, dass ( ) ( ).δ vvd =
Beweis:Nach obigem Lemma und der Annahme der Nichtexistenznegativer Zyklen folgt, dass alle billigsten Wege Länge höchstens n-1 haben.
Insgesamt:
Satz:In Laufzeit läßt sich das Single Source Shortest PathProblem lösen, falls der Graph keine negativen Zyklen enthält.
( )mnO ⋅
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 45
Beispiel (Bellmann-Ford, Gerichteter Graph, positive Kanten):
sB
A
CF
E
G
H
I
J
D
L
K
1
2 3
1
3
53
2
4
6
7 1
3
63
53
12
4
12
110
2
10
72
4
1
1
5
50
∞
10 9
85 9 12 11
i = 1, i = 2, i = 3, i = 4, i = 5, i = 6, i = 7, i = 8,
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 46
Beispiel (Bellmann-Ford, Gerichteter Graph, negative Kanten, aber keine negativen Zyklen):
sB
A
CF
E
G
H
I
J
D
L
K
1
2 -3
1
3
53
2
4
6
7 1
3
63
-5-3
12
4
12
17
-1
7
4
1
2
1
-1
1
-5
50
∞
55 4 4 3
i = 1, i = 2, i = 3, i = 4, i = 5, i = 6, i = 7, i = 8,
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 47
Beispiel (Bellmann-Ford, Ungerichteter Graph, positive Kanten):
B
A C
D
1
42
2 1
5
6
4
4 9
6
3
1 6 5
s12 11 100
E
7 6
i = 1, i = 2, i = 3, i = 4, i = 5,
Warum braucht der Algorithmus hier n-1 Iterationen bis zur Konvergenz?Welches wäre der einfachste Graph mit dieser Eigenschaft?
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 48
7.3.1.4: Auch negative Zyklen erlaubt.
Algorithmus:
Führe zuerst die n-1 for-Schleifendurchläufe des Algo-rithmus von Bellman-Ford aus und merke in d1 die so erzielten d-Werte.
Führe n weitere for-Schleifendurchläufe aus und speicheredas Ergebnis in d2.
1
2
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 49
( ) ( ) ( ) ( )( ) ( ) ( ) −∞=⇒<
=⇒=wδ ii)wδ i)
12
112
wdwdwdwdwd
Lemma::gilt Für Vw∈
Beweis: Übung!
Bemerkung:Wenn sich nach nur einem weiteren Durchlauf der for-Schleife nach Abschluss von noch etwas ändert, sogibt es einen negativen Zyklus, sonst aber nicht.
Um aber alle Zyklen entdecken zu können, benötigt man in insgesamt n Durchläufe.
1
2
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 50
7.3.2 All Pairs Shortest Paths (Floyd-Warshall)Annahme: Keine negativen Zyklen.
{ }nV ,...,2,1=
definiere0und ,Für nkVji ≤≤∈( )
sind.Knoteninneredessen ,nach von WegesbilligstendesKosten :,δ
kjijik
≤=
Beispiel:
( )( )( )( )( ) 14,1δ
14,1δ64,1δ
4,1δ4,1δ
4
3
2
1
0
===∞=∞=
2
1
3
2-3
44
5
2
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 51
( )( ) ( )
∞=
∈=
sonst. , . falls , 0
., falls ,,,δ0 ji
EjijicjiAlso:
( ) ( ) .nach von WegesbilligstendesKosten ,δ,δ jijijin ==
Frage: Wie berechnet sich ?δausδ 1k-k
2 Möglichkeiten: Entweder k Teil eines billigeren Weges oder nicht:
i
k
j( )jik- ,δ 1
( )kik- ,δ 1( )jkk- ,δ 1
( ) ( ) ( ) ( ){ }jkkijiji kkkk ,δ,δ ,,δmin,δ 111 −−− +=Also gilt:
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 52
Algorithmus (Floyd-Warshall):
( )( ) ( )
( ) ( ) ( ) ( ){ }
od od
od ,δ,δ,,δ min,δ
do to 1 for do to 1 for
do to 1 forod
; sonst , falls , 0
, falls,,,δ
do , all for
111
0
jkkijijinj
nink
jiEjijic
ji
Vji
kkkk −−− +←=
==
∞=
∈←
∈
Laufzeit: O(n³)
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 53
Beispiel (Floyd-Warshall, Ungerichteter Graph, positive Kanten):
0 1 4 u u u1 0 2 6 u u
D0= 4 2 0 2 5 uu 6 2 0 1 6u u 5 1 0 4u u u 6 4 0
3
2 4
5
1
42
2 16
4
6
1 6
5
0 1 3 7 u u1 0 2 6 u u
D2= 3 2 0 2 5 u7 6 2 0 1 6u u 5 1 0 4u u u 6 4 0
D1 = D0
0 1 3 5 6 111 0 2 4 5 10
D4= 3 2 0 2 3 85 4 2 0 1 66 5 3 1 0 4
1110 8 6 4 0
0 1 3 5 8 u1 0 2 4 7 u
D3= 3 2 0 2 5 u5 4 2 0 1 68 7 5 1 0 4u u u 6 4 0
u.s.w.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 54
Alternativer Algorithmus:
Benutze Algorithmus von Dijkstra bzw. Bellman-Ford
Idee: Führe n-mal für alle möglichen Startknoten Bellman-Ford-Algorithmus aus.
Laufzeit :
Beobachtung:Es reicht sogar, einmal Bellman-Ford und (n-1)-mal Dijkstra auszuführen.
( )( )nmnnO log :Laufzeit +⋅
( )nmnO ⋅
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 55
7.3.3 All Pairs Shortest Paths (Matrixmultiplikation)Annahme: Keine negativen Zyklen.
{ }nVEVG ,...,2,1 ),,( ==
Wir wissen (Lemma): Wenn ein Pfad von i über k nach j derkürzeste Pfad von i nach j ist, dann sind auch die Pfade von i nach k und von k nach j jeweils kürzeste Pfade.
Sei G als Adjazenzmatrix W = (wij) repräsentiert.Sei p ein kürzester Pfad von i nach j mit m Kanten.Es gilt: m < n.Falls i = j, dann hat p die Länge 0 und keine Kanten.Falls , dann zerlegen wir p in Pfad p´ von i nach k und
Kante (k, j), wobei p´ dann m-1 Kanten hat. Es gilt:ji ≠
kjwkiji += ),(),( δδ
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 56
Sei der kürzeste Pfad zwischen Knoten i und j, der höchstens m Kanten hat. Für m = 0 gilt
Für berechnen wir
Da ein kürzester Weg von i nach j höchstens n-1 Kanten hat, gilt
∞
==
sonst falls0)0( ji
lij
)(mijl
1≥m{ }( )
{ }kjm
iknk
kjm
iknkm
ijm
ij
wl
wlll
+=
+=−
≤≤
−≤≤
−
)1(1
)1(1
)1()(
min
min,min
denn wjj = 0 für alle j
...),( )1()()1( ==== +− nij
nij
nij llljiδ
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 57
Wir berechnen also die in einer Folge von Matrizen L(1), L(2), ... L(n-1), mit L(m) = ( ).
Algorithmus Slow-All-Pairs-Shortest-Paths (W)1) L(1) := W2) for m := 2 to n-1 do begin3) for i := 1 to n do4) for j := 1 to n do begin5)6) for k := 1 to n do7)8) end9) L(old) := L(new)
10) end
)(mijl
)(mijl
∞=:)(mijl
),min(: )1()()(kj
mik
mij
mij wlll += − ),min(: )()()(
kjold
iknew
ijnew
ij wlll +=
Verwendung vonnur zwei MatrizenL(new) und L(old)
∞=:)(newijl
Zeitaufwand: O(n4)L(old) := W
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 58
2
1
3
2-3
44
5
2Beispiel:
∞∞∞∞
∞∞∞−
=
050220
340
)1(L
∞∞∞∞
∞∞−−
=
0402202310
)2(L
∞∞∞∞
∞∞−−
=
0402201310
)3(L
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 59
Beispiel (Matrixmultiplikationsalgorithmus):
0 1 4 u u u1 0 2 6 u u
L1=W= 4 2 0 2 5 uu 6 2 0 1 6u u 5 1 0 4u u u 6 4 0
3
2 4
5
1
42
2 16
4
6
1 6
5
0 1 3 5 7 121 0 2 4 5 10
L3 = 3 2 0 2 3 75 4 2 0 1 57 5 3 1 0 41210 7 5 4 0
0 1 3 5 6 111 0 2 4 5 9
L4 = 3 2 0 2 3 75 4 2 0 1 56 5 3 1 0 411 9 7 5 4 0
10
L5: 10
0 1 3 6 9 u1 0 2 4 7 12
L2 = 3 2 0 2 3 86 4 2 0 1 59 7 3 1 0 4u 12 8 5 4 0
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 60
Geht es auch schneller? Ja, durch Quadrierung!Bisher hatten wir berechnet:
L(1) = L(0) * W = WL(2) = L(1) * W = W2
L(3) = L(2) * W = W3
...L(n-1) = L(n-2) * W = Wn-1
Jetzt berechnen wir schneller:L(1) = = WL(2) = W * W = W2
L(4) = W2 * W2 = W4
L(8) = W4 * W4 = W8
...
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 61
Algorithmus Fast-All-Pairs-Shortest-Paths (W)1) L(old) := W2) m := 13) while m < n-1 do4) for i := 1 to n do5) for j := 1 to n do begin6)7) for k := 1 to n do8)9) end10) m := 2m11) L(old) := L(new)
12) endwhile
),min(: )()()()( oldkj
oldik
newij
newij llll +=
∞=:)(newijl
Zeitaufwand: O(n3 log n),das ist aber immer nochlangsamer als derFloyd-Warshall-Algorithm.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 62
7.4 Depth First Search (Tiefensuche)Durchmusterung von Graphen.
Wichtige Eigenschaften:
Beispiel:
Mit DFS Graph systematisch von einem Knoten s aus zudurchmustern, dabei immer zuerst „in die Tiefe“.
s
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 63
Rekursion:
procedure DFS (s)besucht [s] true;drucke (s);for all do
if not besucht [v]then DFS(v)
fi;od
( ) Evs ∈,
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 64
DFS teilt die Kanten des Graphen in vier Klassen ein, je nachArt des Besuchs:
Wir betrachten gerade die gerichtete Kante (v,w):
1. (v,w) gehört zu Baumkanten T, falls w noch nicht besucht.
2. (v,w) gehört zu Vorwärtskanten F, falls w schon besuchtund „ “, d.h. Pfad von v nach w bestehend aus lauter Baumkanten.
3. (v,w) gehört zu Rückwärtskanten B, falls w schon besuchtund .
4. (v,w) gehört zu Querkanten C, falls w schon besucht, aberweder noch .
∃wv T→*
vw T→*
wv T→* vw T→*
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 65
Erweiterung um dfsnum(v) und compnum(v):• dfsnum(v): Reihenfolge der rekursiven DFS-Aufrufe.• compnum(v): Abschlussreihenfolge der DFS-Aufrufe.
Hauptprogramm:
for all do besucht[v] false od; z1 z2 0;
for all doif not besucht[v] then DFS(v) fi
od
Vv∈
;o/←←←← CFBTVv∈
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 66
(1) procedure DFS(v)(2) besucht[v] true; z1 z1+1(3) dfsnum[v] z1;(4) for all do(5) if not besucht[w] then(6)(7) else if then(8) else if then(9) else(10) fi(11) fi(12) fi(13) od(14)(15) compnum[v] z2
Für die Implementierung brauchen wir 2 Zähler z1, z2:
( ) Ewv ∈,
( )wDFS ( ){ }wvFF ,∪←wv T→*
vw T→* {BB ∪←( ){ }wvCC ,∪←
;122 +← zz
( ){ }wvTT , ∪←
( )}wv,
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 67
Beispiel:i 9
b 2d 4
a 1c 3
h 8
e 5
f 6
g 7
91
2
86
7
5
3
4
dfsnum[v]
s
compnum[v]
Laufzeit: O(n+m)da a) Einzellaufzeit eines Aufrufs (ohne Rekursion)
ist O(1+outdeg(v))b) für jeden Knoten einmal DFS-Aufruf
( )( ) ( ).degout1 mnOvOVv
+=
+⇒ ∑
∈
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 68
Beispiel (Klassifikation der Kanten durch DFS):
sB
A
CF
E
G
H
J
D
L
K
1011
9
10
6
5 54
121 12 11 78
33 1313
7 22 I
94 6 8 1
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 69
Beispiel (Klassifikation der Kanten durch DFS):
sB
A
CF
E
G
H
J
D
L
K
1011
3 9
10
6
5 54
8
121 12 11 78
3 13 13
7 22 I
94 6 1
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 70
Lemma (Eigenschaften, Teil 1):a) Kantenklassen T,B,F,C bilden Partition der Kantenmenge Eb) T entspricht dem Wald der rekursiven Aufrufec) gdw.
d) Seien mit ,dann
wv T→* [ ] [ ][ ] [ ].compnumcompnum
und dfsnumdfsnumvw
wv≤
≤
Vzwv ∈,, wv T→* ( ) ¬∈ und,, Ezw ( )zv T→*
[ ] [ ]( )
[ ] [ ] ( )[ ] [ ] ( ) . gdw. compnumcompnum iv)
., gdw. compnumcompnum iii), ii)
dfsnumdfsnum i)
Cw,zvzBzwvz
CBzwvz
∈<∈>
∪∈<
zv
w**z
vw**
z
vw*
?
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 71
a), b) klar: direkt aus Algorithmus.c) Aufruf DFS(w) geschachtelt in DFS(v)
d)
wv T→* ⇔⇔ [ ] [ ]
[ ] [ ].compnumcompnumunddfsnumdfsnum
wvwv
≥≤
wv T→* [ ] [ ]wv dfsnumdfsnum ≤⇒( ) ( ) ( )wzEzw DFSbevor ,aufgerufen wirdDFS, ⇒∈
endet, und auch bevor DFS(v) endet.( )zv T→¬ * ( )zDFS⇔ nicht in DFS(v) geschachtelt
( ) ( ).DFSAufrufr startet voDFS vz⇒[ ] [ ] (i) dfsnumdfsnum vz <⇒
( ) ( ) (ii) , 2 Teil CBzw ∪∈ →( ) ⇔∈Bzw, wz T→* nach Definition von B
⇔ vz T→* da undwv T→* ( )zv T→¬
Beweis:
[ ] [ ] (iii) compnumcompnum vz >⇔*
e)
(iv)(ii), (iii)
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 72
Lemma (Eigenschaften, Teil 2):
( )( ) [ ] [ ]( ) [ ] [ ]
[ ] [ ]( ) [ ] [ ]
[ ] [ ].compnumcompnum und dfsnumdfsnum , g)
.compnumcompnum und dfsnumdfsnum, f)
.dfsnumdfsnum, e):,Sei
vwvwCwv
vwvwBwv
wvFTwvEwv
<<⇔∈>
<⇔∈≤⇔∪∈
∈
f) g)e)v
w
v*
w*
*w
*
w vor vbesucht
w* *
v v
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 73
Beweis:e) [ ] [ ]wv dfsnumdfsnum ≤⇒( ) ⇒∪∈ FTwv, wv T→*
[ ] [ ]( ) ( )
( )
( ) FTwv
vwEwv
wv
∪∈⇒
⇒
∈≤
,
ngSchachtelu echte
werden.aufgerufen DFSvon Abschluss vor DFS muss ,, Da
.dfsnumdfsnum Sei
wv T→*
f), g) folgen aus d) und e) ...
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 74
Bemerkungen:•T, B, F, C werden im wesentlichen durch dfsnum, compnum festgelegt (vgl. Lemma!)
•In azyklischen Graphen gibt es keine Rückwärtskanten, d.h. ( ) [ ] [ ]
( ) [ ].Sortierung ologischeergibt top
compnum1:num ngNummerierucompnumcompnum:,
vnvwvEwv
−+=⇒>∈∀
Mitteilung:Zusammenhangskomponenten in ungerichteten Graphenkönnen mit Hilfe von DFS in Zeit O(n+m) berechnet werden.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 75
Starke Zusammenhangskomponenten
Ein gerichteter Graph G=(V,E) heißt stark zusammen-hängend gdw.
Die maximalen (bzgl. Mengeninklusion) stark zusammen-hängenden Teilgraphen von G heißen starke Zu-sammenhangskomponenten (SZK‘s).
Beispiel:
.:, wvVwv E→∈∀ *
h
c
f
b d
g
a
e
K2
K3
K1 K4
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 76
Idee für Algorithmus: Erweitere DFS:
( ) .von Teilgraph r erforschtebisher , Sei GEVG ′′=′:von sSZK'dieVerwalte G
{ } { }{ }.SZK,o,mit Starte aEaV =/=′=′.Vv ′∈Sei (v,w) die nächste Kante in DFS. Dann ist
( ) { }
( )( )CBwvVw
wTwvVw
∪∈
′∈∈′∉
, falls zusammeneiner zu sSZK' mehrere fügedann ,Ist
. umSZK erweiteredann ,, d.h. ,Ist
Aber wie zusammenfügen?
vw
V´ V´
w v**
w v**
Vw ′∉Vw ′∈
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 77
Bezeichnungen:
• SZK K heißt abgeschlossen, wenn alle DFS-Aufrufe für Knotenin K abgeschlossen sind.
• Wurzel von K ist der Knoten mit kleinster dfsnum in K.
• Folge von Knoten heißt unfertig, falls ihre DFS aufgerufen sind, aber ihre SZK noch nicht abgeschlossen ist. (Sortiert nach dfsnum!)
• wurzeln ist Folge der Wurzeln von noch nicht abgeschlossenenSZK´s. (Sortiert nach dfsnum!)
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 78
Beispiel:
h
c
f
b d
g
a
e
unfertig: a b c e f gwurzeln: a b e f g
Beobachtung:
( ).Komponentesener abgeschlosnicht in
undsener abgeschlosin :, 2.:unfertig .1
wvEwv
v∈∃//
∈∀ gv E→*
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 79
Von g ausgehende Kanten:( )( ) { } { } { } { }. , , ,,n Komponentevier vereinigt :,
SZK.sener abgeschlosin liegt nichts,tut :,gfecbBbg
dCdg∈∈
unfertig: a b c e f gwurzeln: a b
( ) { }hThg Komponenteneueerzeuge:, ∈
Beim Abschluss von DFS(v) teste, ob v Wurzel.Wenn ja, so gib Komponente mit v als Wurzel aus und streichesie aus unfertig und v aus wurzeln.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 80
Operationen auf unfertig und wurzeln erlauben Implementierungals Keller (Stack):
z.B. Vereinigen von Komponenten:
K1 K2 K3 K4w vunfertig
wurzeln
wurzeln
K2, K3 und K4 werden vereinigt durch pop(wurzeln) bis top(wurzeln) = Wurzel der SZK von w.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 81
Beispiel (Bestimmung der SZKs durch DFS):
sB
A
CF
E
G
H
J
D
L
KI
E G IJ K
CF EI D sB
s BA C FE G HIJD LKunfertig
wurzeln s A C D F H B L
print K J G H A L
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 82
Korrektheit:Invarianten:
I1: mit v in abgeschlossener und w in nicht-abgeschlossener SZK.
I2: Nichtabgeschlossene SZK´s liegen auf einem Pfad,insbesondere ihre Wurzeln liegen auf einem Baumpfad
I3: Knoten jeder nicht abgeschlossenen Komponente Kibilden Intervall in „unfertig“, erstes Element des Intervalls ist die Wurzel von Ki.
Zu zeigen: Invarianten bleiben beim Einfügen neuer Kanten
( ) Ewv ∈∃/ ,
( ) erfüllt., Ewv ∈
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 83
1.Fall:push (w, unfertig); push (w, wurzeln)
( ) :, Twv ∈
I1: Es wird keine SZK abgeschlossen.
I2: Sei r Wurzel der Komponente von v.Dann und
I3: Trivial!
vr T→* ( ) Twv ∈,⇒ wr T→*
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 84
2.Fall:a) w in abgeschlossener SZK: Tue nichts.b) w in nicht abgeschlossener SZK: Vereinige
oberste SZK´s bis zu der, in der w liegt.
( ) :, Twv ∈/
In a) passiert nichts. Nur b) zu betrachten:
I1: Es wird keine SZK abgeschlossen...
I2: Pfad wird verkürzt.
I3: Löschen der obersten Wurzel vereinigt Intervalle zueinem neuen. Da vorher I2 galt, bildet dieses eine Intervall eine einzige Komponente.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 85
Durch nachfolgenden Algorithmus (Programm) erhalten wir:
Satz:Starke Zusammenhangskomponenten eines gerichteten Graphen können in Zeit O(n+m) berechnet werden.
Das Hauptprogramm wird erweitert um:unfertig wurzeln leerer Keller
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 86
(1) procedure DFS(v)(2) besucht[v] := true; z1:= z1+1; dfsnum[v] := z1;(3) push(v, unfertig); push(v, wurzeln);(4) for all do(5) if not besucht[w] then DFS(w)(6) else if(7) then while do(8) pop(wurzeln) od ;(9) fi(10) fi(11) od(12) z2 := z2+1; compnum[v] := z2(13) if v = top(wurzeln)(14) then repeat w := pop(unfertig)(15) print(w)(16) until v = w ;(17) pop(wurzeln) ;(18) fi
( ) Ewv ∈,
unfertig∈w( )[ ] [ ]wdfsnumwurzelntopdfsnum >
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 87
Zeilen (13)-(16) : Ausgabe der SZK mit Wurzel v.
Bemerkungen:
• Test „ “ wird mit zusätzlichem booleschen Feldin_unfertig unterstützt.
• Jeder Knoten wird höchstens einmal nach unfertig bzw. wurzeln aufgenommen.
unfertig∈w
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 88
7.5 Minimal aufspannende Bäume (MST)Sei G(V,E) ein zusammenhängender, ungerichteter Graph. Sei eine Kostenfunktion.Ziel: Berechne , sodass G(V,ET) zusammenhängend ist
undEET ⊆
( ) ( ) ist.lich kleinstmög: ∑=T ecEc
+→ c:E R
∈ TEe
Beispiel:
8
13 4
22 3
10
62
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 89
Anwendungsbeispiele:• Computer-Netzwerke...• Elektronische Schaltkreise...• Netz von Telefonanschlüssen...uvm.
Lemma:G(V,ET) ist azyklisch.
Beweis:Würde G(V,ET) einen Kreis enthalten, so könnte man eine Kante entfernen, der Graph wäre weiterhin zu-sammenhängend und die Gesamtkosten geringer.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 90
Wir suchen also einen „aufspannenden Baum“ mit minimalenKosten (MST, Minimum Spanning Tree).
Kruskals Greedy-Algorithmus für MST
Sortiere Kanten e1, e2, ... , em so, dass ( ) ( ) ( );...21 mececec ≤≤≤
;o/←TEfor to m do
ifthen
fiod
1←i( , TEV ∪
TE{ })azyklischie
{ }iT eE ∪←
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 91
Satz:Der Greedy-Algorithmus von Kruskal ist korrekt, d.h.er findet immer einen MST.
Beweis:Eine Kantenmenge heiße „gut“, falls sie zu einem MST erweiterbar ist.
Behauptung:Sei gut und sei eine billigste Kante, sodass der Graph azyklisch ist. Dann ist auch gut.
EE ⊆′
EE ⊆′ EEe ′∈ \{ }( )eEV ∪′,
{ }eE ∪′
Beweis der Behauptung per Induktion:Sei
Ist
( ) 111 mit MSTein , EEEVT ⊆′=( ).gutdaexistiert, 1 ET ′
fertig.so,1Ee∈
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 92
Ist , so betrachte Graph .H enthält einen Kreis, auf dem e liegt. Da azyklisch ist, enthält dieser Kreis auch eine Kante ausSei eine solche Kante
Betrachte
Da e eine billigste Kante war, giltAlso
Da nach Voraussetzung ein MST ist, gilt D.h. auch ein MST, also gut.
Mit der Behauptung folgt die Korrektheit von KruskalsAlgorithmus unmittelbar.
1Ee∉ { }( )eEVH ∪= 1,{ }( )eEV ∪′,
{ }( ).\1 eEE ∪′.1e
{ }( ) { }( ).\, 112 eeEVT ∪=( ) ( ) ( ) ( ).unddaufspannenist 1122 ececTcTcT −+=
( ) ( ).1ecec ≤( ) ( ).12 TcTc ≤
1T ( ) ( ).12 TcTc =2T { }eE ∪′
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 93
Beispielbild:
e1
11 : ET
e
{ }( ) { }eeET ∪112 \:
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 94
Zur Implementierung:Wir halten uns eine Partitionvon
Operationen:Starten mit Partition {{1}, {2}, ... , {n}}.
Benötigen:•Find(x): Gibt Namen der Menge zurück,
die x enthält.•Union(a,b): Vereinigt die Mengen a und b.
VVVV k =∪∪∪ ...21
.o: undo:: /≠∀/=∩≠∀ iji ViVVjiV
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 95
Damit wird die for-Schleife in Kruskals Algorithmus zu:
for to do
ifthen
Union(a,b)fi
od
Bemerkung: Auf diese Weise lassen sich i.w. auch die Zusammenhangs-komponenten eines Graphen berechnen.
mi 1←{ };,sei vuei =( );Find ua ←( );Find vb ←
ba ≠{ };iTT eEE ∪←
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 96
Zur Realisierung der Union-Find-Datenstruktur:Erste naheliegende Idee:
Realisierung als Feld R[1 .. n], wobei R[x] Name derMenge sein soll, die x enthält.
Damit:Find(x): return R[x]Union(a,b): for to n do
if then fiod
Laufzeit: Find(x): O(1)Union(a,b): O(n)
1←i[ ] aiR = [ ] biR ←
Algorithmus von Kruskal:2m Find-Operationen und n-1 Union-Operationen.
Laufzeit Kruskal: O(m+n²+m log m)
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 97
Heuristische Ideen zur Verbesserung:
•Union sollte nicht alle Elemente anschauen...Verwalte Elemente jeder Menge separat...
•Behalte bei Union immer die Namen der größerenMengen.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 98
Also zusätzlich Verwaltung der Mengen als Listen (samt Größenangabe):
Bild:
251
Size Elem.
1234
R: wie vorher
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 99
Damit folgende Implementierung:
Initialis: for to n do
odFind(x): return R[x]Union(a,b): if size[a] < size[b] then „vertausche a und b“ fi;
for all do
insert(x, Elem[a])od;
1←x[ ] ;xxR ←
[ ] { };Elem xx ←[ ] ;1size ←x
[ ]bx Elem∈[ ] ;axR ←
[ ] [ ] [ ]baa sizesizesize +←
Beachte: Im Worst Case kann ein Union aber dennoch Zeit O(n) benötigen.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 100
Satz:Mit obiger Implementierung lassen sich die Initialisierungensowie n-1 Union-Operationen und m Find-Operationen in Laufzeit ( ) n.realisierelog mnnO +⋅
Beweis:Initialisierungen: O(n), klar!m Find-Operationen: O(m), klar!n Union-Operationen kosten Zeit O(n log n):Union(a,b): Vereinige zwei Mengen mit Elementen;
o.E. seiSei ni für i-tes Union die Größe der kleineren Menge. DamitZeit für alle Union-Operationen:
ba nn bzw.( ).1Laufzeit bab nOnn +⇒≤
( ) .11
1
1
1
+=
+ ∑∑
−
=
−
=
n
ii
n
ii nnOnO
Immer wenn ein Element die Menge wechselt, trägt es bei. zu 1genau
1
1∑−
=
n
iin
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 101
wechselt.Menge
die Element oft wieangibt, wobei, Also1
1 1jrrn j
n
i
n
jji∑ ∑
−
= ==
.,... ,2 ,1allefür log2 njnrj =≤Behauptung:Beweis der Behauptung:
Wenn j die Menge wechselt und vorher in einer Menge mit l Elementen war, so ist j nachher in einer Menge mit mindestens 2l Elementen.D.h. nach dem k-ten Wechsel ist j in einer Menge mit Elementen. k2≥Da es nur n Elemente gibt, folgt .log2 nk ≤
Mit Hilfe der Behauptung folgt somit, dass n Union-OperationenZeit O(n log n) kosten.
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 102
Korollar:Der Algorithmus von Kruskal hat Laufzeit .( )mmO log⋅
Bemerkung:Obiges ist ein Beispiel für amortisierte Analyse:Wir betrachten statt Einzeloperationen, welche verschiedenteuer sind, eine Folge von Operationen und stellen fest,wieviel diese zusammen kosten.
Anderes Beispiel für amortisierte Analyse:
Binärzähler: Nicht trivial n log n, sondern 2n amortisiert...
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 103
Beispiel (Kruskal, Ungerichteter Graph, nichtnegative Kanten):
sB
A
CF
E
G
H
I
J
D
L
K
2 3
1
3
53
2
4
6
7 1
3
63
53
12
4
1
2
1
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 104
Alternative zur vorigen Implementierung:Idee: Repräsentiere jede Menge durch einen Baum
(i.a. nicht binär):Jeder Knoten (außer Wurzel) zeigt auf Elternknoten,Wurzel enthält Namen der Menge.
R[x]
xDamit:
Union(a,b): „Zusammenhängen“ von Bäumen.a b
Zeit: O(1)
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 105
Find(x): Folge dem Pfad von x zur Wurzel.Zeit: O(1+Tiefe(x)).
Ideal wäre also Baumtiefe 1...Im Worst Case können n Union-Op. aber zu Tiefe n-1 führen.
Deshalb: „Gewichtete Vereinigungsregel“:Hänge immer den kleineren an den größeren Baum(Baumgröße = Anzahl der Knoten).
Weitere Idee: PfadkomprimierungWenn bei Find der Pfad zur Wurzel zurückverfolgt wird,so hänge alle Zeiger des Pfades zur Wurzel hin um:
Bild:
x x
Vorlesung Algorithmen (RN/MK/AZ) WSI für Informatik, Universität Tübingen 106
Mitteilung:Mit gewichteter Verzweigungsregel und Pfadkomprimierunglassen sich die Initialisierungen sowie n-1 Union-Operationen und m Find-Operationen in Laufzeitrealisieren, wobei α die Inverse der Ackermannfunktion ist.
( )( )n,nmmnO +⋅+ α
α wächst extrem langsam und ist für alle realistischen Werte ≤
Der Beweis obiger Mitteilung ist ziemlich kompliziert.
.5