DSAL - 8. Globalübung
Tim Quatmann
19. Juni 2018
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 1 / 19
Agenda
1 Tiefen- und Breitensuche
2 Anwendung Breitensuche: k-begrenzte Erreichbarkeit
3 Kritische-Pfad-Analyse
4 Bipartite Graphen
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 2 / 19
Tiefen- und Breitensuche
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 3 / 19
Elementare Graphenalgorithmen Graphendurchlauf
Tiefensuche: Implementierung
1 void DFS(List adj[n], int start, int &color[n]) {2 color[start] = GRAY; // start ist noch zu verarbeiten3 foreach (w in adj[start]) {4 if (color[w] == WHITE) { // neuer ("ungefundener") Knoten5 DFS(adj, w, color);6 }7 }8 color[start] = BLACK; // start ist abgeschlossen9 }
11 void completeDFS(List adj[n], int n, int start) {12 int color[n] = WHITE; // noch kein Knoten ist gefunden worden13 for (int i = 0; i < n; i++)14 if (color[i] == WHITE) DFS(adj, i, color);15 }
Joost-Pieter Katoen Datenstrukturen und Algorithmen 41/80
ffnstteaif: "
Knotenlrreiehbare Kaoten
/Find
Start -
Knoten
Tiefensuche: Beispiel
A B C D
E F G
H I J K
L M N
Reihenfolge Graufärbung: A,B ,C ,D,K , J,G , I ,E ,F ,H, L,M,NReihenfolge Schwarzfärbung: G ,E ,F ,H, I , J,K ,D,C ,B ,A,N,M, L
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 4 / 19
= Grau Schw .
Tiefensuche: Beispiel
A B C D
E F G
H I J K
L M N
Reihenfolge Graufärbung: A,B ,C ,D,K , J,G , I ,E ,F ,H, L,M,NReihenfolge Schwarzfärbung: G ,E ,F ,H, I , J,K ,D,C ,B ,A,N,M, L
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 4 / 19
Elementare Graphenalgorithmen Graphendurchlauf
Breitensuche: Implementierung
1 void BFS(List adj[n], int start, int &color[n]) {2 Queue wait; // zu verarbeitende Knoten3 color[start] = GRAY; // Knoten start ist noch zu verarbeiten4 wait.enqueue(start);5 while (!wait.isEmpty()) {// es gibt noch unverarbeitete Knoten6 int v = wait.dequeue(); // nächster unverarbeiteter Knoten7 foreach (w in adj[v]) {8 if (color[w] == WHITE) { // neuer ("ungefundener") Knoten9 color[w] = GRAY; // w ist noch zu verarbeiten
10 wait.enqueue(w);11 }12 }13 color[v] = BLACK; // v ist abgeschlossen14 }15 }
17 void completeBFS(List adj[n], int n) {18 int color[n] = WHITE; // noch kein Knoten ist gefunden worden19 for (int i = 0; i < n; i++)20 if (color[i] == WHITE) BFS(adj, n, i, color);21 }
Joost-Pieter Katoen Datenstrukturen und Algorithmen 34/80
FIFO
Breitensuche: Beispiel
A B C D
E F G
H I J K
L M N
Reihenfolge Graufärbung: A,B ,E ,F ,C , I ,D,G ,H, J,K , L,M,NReihenfolge Schwarzfärbung: A,B ,E ,F ,C , I ,D,G ,H, J,K , L,M,N
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 5 / 19
wait : * *#¥# *A,##*** , # , #
Breitensuche: Beispiel
A B C D
E F G
H I J K
L M N
Reihenfolge Graufärbung: A,B ,E ,F ,C , I ,D,G ,H, J,K , L,M,NReihenfolge Schwarzfärbung: A,B ,E ,F ,C , I ,D,G ,H, J,K , L,M,N
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 5 / 19
Anwendung Breitensuche:k-begrenzte Erreichbarkeit
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 6 / 19
Sei G = (V ,E ) ein (ungewichteter) Graph.
Ein Pfad von u 2 V zu w 2 V im Graphen G = (V ,E ) ist eine Folgev0v1 . . . vk�1vk mit vi 2 V , (vi , vi+1) 2 E , v0 = u, vk = w .k ist die Länge des Pfades v0v1 . . . vk�1vk
Für zwei Knoten u,w 2 V sei dist(u,w) die Länge eines kürzestenPfades von u zu w , d.h.
dist(u,w) = min{k 2 N | Es gibt einen Pfad der Länge k von u zu w}
Außerdem: dist(u,w) = 1, falls w nicht von u erreichbar ist.
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 7 / 19
( beige w . sraphcn Ist es anders )
A B C D
E F G
H I J K
L M N
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 8 / 19
dist ( Ap ) =3
dist ID ,H 7=4
dist IHD )=4
distic ,m)=a
k-begrenzte ErreichbarkeitGegeben: Ein Graph G = (V ,E ), ein Startknoten u 2 V , k 2 NGesucht: Alle Knoten w 2 V mit dist(u,w) k .
Idee: Nutze Breitensuche!Starte bei u
Merke die aktuelle Suchtiefe
Stoppe bei Suchtiefe k
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 9 / 19
Beispiel: Finde alle Knoten w 2 {A,B , . . . ,N} mit dist(A,w) 2:
A B C D
E F G
H I J K
L M N
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 10 / 19
O 1 2
Ergebnis :
^ 1 AM , E. F, I
2
k-begrenzte Erreichbarkeit: Algorithmus
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 11 / 19
k-begrenzte Erreichbarkeit: Algorithmus
1 boundedReach(List adj[n], int start, int k) {2 Queue wait; // zu verarbeitende Knoten3 if (k > 0) wait.enqueue(start);4 int dist[n] = -1; // Distanz der gefundenen Knoten5 dist[start] = 0;6 Set result;7 result.insert(start);8 while (!wait.isEmpty()) { // es gibt noch unverarbeitete Knoten9 int v = wait.dequeue();
10 foreach (w in adj[v]) {11 if (dist[w] == -1) { // neuer ("ungefundener") Knoten12 result.insert(w);13 dist[w] = dist[v] + 114 // Untersuche w nur, wenn mit
Kritische-Pfad-Analyse
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 13 / 19
Kritischer-Pfad-ProblemGegeben: Knotengewichteter DAG G = (V ,E ,W )
Gesucht: Der längste Pfad (bezogen auf das Gesamtgewicht)
Anwendung: Abhängigkeiten von Aufgaben v 2 V mit Dauer W (v)(v , v 0) 2 E () “Um v zu erledigen muss erst v 0 erledigt werden”
Idee: Bestimme est/eft (earliest start/finish time) für jeden Knoten
est(v) =
8><
>:
max(v ,v 0)2E
eft(v 0) , falls 9 (v , v 0) 2 E
0 , sonst
eft(v) = est(v) +W (v)
Nutze Tiefensuche um die Knoten in “richtigen” Reihenfolge zu bearbeiten.
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 14 / 19
a.a¥E±¥wig
Kritischer-Pfad-ProblemGegeben: Knotengewichteter DAG G = (V ,E ,W )
Gesucht: Der längste Pfad (bezogen auf das Gesamtgewicht)
Anwendung: Abhängigkeiten von Aufgaben v 2 V mit Dauer W (v)(v , v 0) 2 E () “Um v zu erledigen muss erst v 0 erledigt werden”
Idee: Bestimme est/eft (earliest start/finish time) für jeden Knoten
est(v) =
8><
>:
max(v ,v 0)2E
eft(v 0) , falls 9 (v , v 0) 2 E
0 , sonst
eft(v) = est(v) +W (v)
Nutze Tiefensuche um die Knoten in “richtigen” Reihenfolge zu bearbeiten.
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 14 / 19
Elementare Graphenalgorithmen Anwendungen der Tiefensuche
Kritische-Pfad-Analyse: Implementierung
1 // Knotengewichte in duration.2 // Ausgabe: eft, kritischer Pfad kodiert in critDep3 void DFS(List adj[n], int start, int &color[n],4 int duration[n], int &critDep[n], int &eft[n]) {5 color[start] = GRAY; critDep[start] = -1; int est = 0;6 foreach (next in adj[start]) {7 if (color[next] == WHITE)8 DFS(adj, next, color, duration, critDep, eft);9 if (eft[next] >= est) {
10 est = eft[next]; critDep[start] = next;11 }12 }13 eft[start] = est + duration[start];14 color[start] = BLACK;15 }16 void critPath(List adj[n], int n,17 int duration[n], int &critDep[n], int &eft[n]){18 int color[n] = WHITE;19 for (int i = 0; i < n; i++)20 if (color[i] == WHITE)21 DFS(adj, i, color, duration, critDep, eft);22 }
Joost-Pieter Katoen Datenstrukturen und Algorithmen 78/80
|critical dependency
A, 1 B, 1 C, 3 D, 2
E, 2 F, 3 G, 1 H, 1
I, 3 J, 2 K, 2 L, 3
Knoten A B C D E F G H I J K L
estcritDepeft
Gesamtdauer:
Kritischer Pfad:
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 15 / 19
0
EEIEEEEa¥s¥¥ I73 ( Max e At )
I E A B C F
Bipartite Graphen
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 16 / 19
Definition (Bipartiter Graph)Ein ungerichteter Graph G = (V ,E ) heißt bipartit, falls es zwei Mengen Uund W gibt mit
U [W = VU \W = ;E ✓
�{v , v 0} | v 2 U und v 0 2 W
, d.h. es gibt keine Kanten
zwischen zwei Knoten in U bzw. zwei Knoten in W .
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 17 / 19
} UOW , now
u WA - B
F C
| c \ g- HD - E ¥#DF g- H
-
SatzEin ungerichteter Graph G = (V ,E ) ist bipartit genau dann, wenn er keineZykeln ungerader Länge hat
Die Länge eines Zyklus v0v1 . . . vk mit v0 = vk ist k
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 18 / 19
o_0 O_0 Of\o/ Kb orndcht bipartite
bipartite
bipartit
' '
⇒"
sci gift,E ) bipuvtit mitkuuwAndren 8 hat einen ungeraden Zykel
✓ov , . . . VK ( Vo=Vk , Vitvj fair its )OBDA : Sei voeU . Wegen wo.vn ) EE folgt ,
class VNEW . Daher Vz EU r . -
Esfolgt : view , fallgi geradeVIEW , falls i ungerade
Da K ungerade gilt also VKEW
be Widersprach , da v ,c=Vo C- U
Es folgt , class g Keihin unyeraden
Zykd haben Kann.
"
⇐' ' g habe kcime Zykel ungeradcr
liinge . Wir nehmen an , class g
Zusammenhiinyend ist ( dnsonstea
betrachten wir die Zush . komponenten
einzelh ) ,
Sci UEV ein beliebiger , testgewiihlter Knoten . Sci
liinye lines kcivzestenPfadesW :{ vtvldistluu ) gerade } wnu
nach W
U={ vevldistluu ) ungerade }Wir Zeigen , class G bipartite
mint U,
WEV ist :
• WuU=V
• Wnu ?0
d. Fall : Falls es line Kante ( uv' )EE
Mit v.v' EW gibe . betoachte
die Pfade Vovn . . . Vk mitliinyedistcuvu )W w
=V =u
Vjvn'
. .iv
'
.
' mitlcinyedistcviu )W W
=v ' =u
sei ¢: min { mewl Fjeoo , ... ik ' } :k=v' g)( lntuitivist ' veeder ersteknoten , der aat
beiden Pfaden b sucht wivd )Wiihle l 't { o
,...
,. ) mit v. =Vu
: \ °
, ,,
v / , u
,-
, (, /
~ - -
Betrachte den Zykel
Vovn . ..VuVi
. , VI. z . . . Vol ✓w
W W=V
=j , =v'
unit binge distlvo ,vu ) tdistlvi'
,vo' ) +7
Wedgendiatlviutdistlv ,v . ) + distlv . ,u ) -distlviukdistlvivi . ) + disY.cn,u ) Perak
gilt : distlviuclgerade €7 distlu ,v' it gerude
Daher ist distcvoihltdistlviiivo ' )inner gerade . Obigcr Zykel
hat also unqevade Langeb. Wider , pruch
2. Fall ( kante Zwischeu zweiknoten in W ist analog-
A
1--
dist ( A. b) =L\c D
dist ( Bi D) =LB
a
Nächster Termin
Nächste VorlesungFreitag, 22. Juni, 13:15 (H01).
Nächste GlobalübungDienstag, 26. Juni, 14:15 (Aula 1).
Tim Quatmann Datenstrukturen und Algorithmen 19. Juni 2018 19 / 19