sd_curs-08
56
Curs 8 – conținut • Sortare topologică • Arbore de acoperire minim – Algoritmul lui Kruskal Structuri de date 2013 - 2014 1 – Algoritmul lui Prim • Drumuri minime de sursă unică – Algoritmul lui Dijkstra • Cuplaj bipartit maxim
-
Upload
olea-zubcova -
Category
Documents
-
view
218 -
download
0
description
APA-analiza si proiectarea algoritmelor
Transcript of sd_curs-08
Curs 8 – conținut
• Sortare topologică
• Arbore de acoperire minim
– Algoritmul lui Kruskal
Structuri de date 2013 - 2014 1
– Algoritmul lui Prim
• Drumuri minime de sursă unică
– Algoritmul lui Dijkstra
• Cuplaj bipartit maxim
Sortare topologică
• Digrafurile aciclice pot modela precedența între evenimente.
• O sortare topologică a unui digraf D= • O sortare topologică a unui digraf D= (V, A) este o ordonare a vârfurilor sale astfel încât dacă (i,j) є A, atunci i apare înaintea lui j.
Structuri de date 2013 - 2014 2
Sortare topologică - exemplu
lenjerie
pantaloni
curea
cămașă
cravată
ciorapi
pantofi
ceas
Structuri de date 2013 - 2014 3
curea cravată
sacou
ciorapi lenjerie pantaloni pantofi ceas cămașă curea cravată sacou
(Cormen T.H. et al., Introducere în algoritmi)
Sortare topologică
procedure SortareTopologica(D)
begin
1. DFSCompTareConexe(D)
2. Afisează vârfurile în ordinea descrescătoare a timpilor finali de vizitare
2. Afisează vârfurile în ordinea descrescătoare a timpilor finali de vizitare timpFinal[i]
end
• Complexitatea: O(n+m)
Structuri de date 2013 - 2014 4
Sortare topologică - exemplu
lenjerie
pantaloni
curea
cămașă
cravată
ciorapi
pantofi
ceas
1/8
2/56/7
12/15
11/1617/18
13/14
9/10
Structuri de date 2013 - 2014 5
curea cravată
sacou
ciorapi lenjerie pantaloni pantofi ceas cămașă curea cravată sacou
(Cormen T.H. et al., Introducere în algoritmi)
2/5
3/4
6/7
18 457810141516
Arbore de acoperire minim
• G=(V,E) – graf neorientat și conex.
• w:E �R+ - funcție de cost
• Dacă T ⊆ E, atunci ∑∈
=
Te
w(e) w(T)
• Să se găsească T ⊆ E a.î. graful A=(V, T) este conex și w(T) minim.
Structuri de date 2013 - 2014 6
∈Te
Arbore de acoperire mimin
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 7
0 4
57 6
8
8
21
7 610
Algoritmul lui Kruskal
procedure AAM-Kruskal(G, w)
begin
1. T ← ∅
2. for i ← 0 to n-1 do singleton(i)
3. sortează muchiile din E în ordinea crescătoare 3. sortează muchiile din E în ordinea crescătoare
a costului w
4. for (fiecare muchie {i,j} є E în ordinea crescătoare a costului w) do
5. if (find(i) != find(j)) then
6. T ← T ∪ {{i,j}}
7. union(i,j)
end
Structuri de date 2013 - 2014 8
O(m lg m)
Algoritmul lui Kruskal - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 9
0 4
57 6
8
8
21
7 610
Algoritmul lui Kruskal - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 10
0 4
57 6
8
8
21
7 610
Algoritmul lui Kruskal - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 11
0 4
57 6
8
8
21
7 610
Algoritmul lui Kruskal - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 12
0 4
57 6
8
8
21
7 610
Algoritmul lui Kruskal - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 13
0 4
57 6
8
8
21
7 610
Algoritmul lui Kruskal - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 14
0 4
57 6
8
8
21
7 610
Algoritmul lui Kruskal - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 15
0 4
57 6
8
8
21
7 610
Algoritmul lui Kruskal - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 16
0 4
57 6
8
8
21
7 610
Algoritmul lui Kruskal - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 17
0 4
57 6
8
8
21
7 610
Algoritmul lui Kruskal - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 18
0 4
57 6
8
8
21
7 610
Algoritmul lui Kruskal - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 19
0 4
57 6
8
8
21
7 610
Algoritmul lui Kruskal - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 20
0 4
57 6
8
8
21
7 610
Algoritmul lui Kruskal - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 21
0 4
57 6
8
8
21
7 610
Algoritmul lui Kruskal - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 22
0 4
57 6
8
8
21
7 610
Algoritmul lui Kruskal - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 23
0 4
57 6
8
8
21
7 610
Algoritmul lui Prim
procedure AAM-Prim(G, w, radacina)
begin
1. Q ← CoadaPrioritatiVida() // minim prioritar
2. for i ← 0 to n-1 do
3. cheie[i] ← ∞; insereaza(Q, i)
4. cheie[radacina] ← 0; tata[radacina] ← -14. cheie[radacina] ← 0; tata[radacina] ← -1
5. while (not esteVida(Q)) do
6. i ← citeste(Q); elimina(Q)
7. for (fiecare vârf j în listaDeAdiac(i)) do
8. if (j є Q and w({i,j}) < cheie[j]) then
9. tata[j] ← i
10. cheie[j] ← w({i,j})
end
Structuri de date 2013 - 2014 24
O(m lg n)
Algoritmul lui Prim - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 25
0 4
57 6
8
8
21
7 610
Q=[(0,0), (1,∞), (2,∞), (3,∞), (4,∞), (5,∞), (6,∞), (7,∞), (8,∞) ]
Algoritmul lui Prim - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 26
0 4
57 6
8
8
21
7 610
Q=[(1,4), (2,∞), (3,∞), (4,∞), (5,∞), (6,∞), (7,8), (8,∞) ]
Algoritmul lui Prim - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 27
0 4
57 6
8
8
21
7 610
Q=[(2,8), (3,∞), (4,∞), (5,∞), (6,∞), (7,8), (8,∞) ]
Algoritmul lui Prim - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 28
0 4
57 6
8
8
21
7 610
Q=[(3,7), (4,∞), (5,4), (6,∞), (7,8), (8,2) ]
Algoritmul lui Prim - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 29
0 4
57 6
8
8
21
7 610
Q=[(3,7), (4,∞), (5,4), (6,6), (7,7) ]
Algoritmul lui Prim - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 30
0 4
57 6
8
8
21
7 610
Q=[(3,7), (4,10), (6,2), (7,7) ]
Algoritmul lui Prim - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 31
0 4
57 6
8
8
21
7 610
Q=[(3,7), (4,10), (7,1) ]
Algoritmul lui Prim - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 32
0 4
57 6
8
8
21
7 610
Q=[ (3,7), (4,10) ]
Algoritmul lui Prim - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 33
0 4
57 6
8
8
21
7 610
Q=[ (4,9) ]
Algoritmul lui Prim - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 34
0 4
57 6
8
8
21
7 610
Q=[ ]
Algoritmul lui Prim - exemplu
0 4
31 2
8
4
11
24
8 7
14
9
Structuri de date 2013 - 2014 35
0 4
57 6
8
8
21
7 610
Drumuri minime de sursă unică
• D=(V,A) – digraf și s є V – vârf sursă
• w:A �R+ - funcție de cost
• Costul unui drum minim de la i la j (i, j є V):
∑ j la i la de drum p exista daca ,w(a)min
• Să se găsească δ(s,i) pentru i = 0,1, ..., n-1
Structuri de date 2013 - 2014 36
∞=
∑∈
altfel ,
j la i la de drum p exista daca ,w(a)min j)(i, pa
pδ
Drumuri minime – exemplu s=0
0
21
3
2 1 4
6
Structuri de date 2013 - 2014 37
0
34
2 1
5 3
6
2 7
Drumuri minime – exemplu s=0
0
21
3
2 1 4
63 9
Structuri de date 2013 - 2014 38
0
34
2 1
5 3
6
2 7
5 11
Drumuri minime – exemplu s=0
0
21
3
2 1 4
63 9
Structuri de date 2013 - 2014 39
0
34
2 1
5 3
6
2 7
5 11
Algoritmul lui Dijkstra
procedure DM-Dijkstra(D, w, radacina)
begin
1. Q ← CoadaPrioritatiVida() // minim prioritar
2. for i ← 0 to n-1 do
3. cheie[i] ← ∞; insereaza(Q, i); tata[i] ← -1;
4. cheie[radacina] ← 0; S ← ∅4. cheie[radacina] ← 0; S ← ∅
5. while (not esteVida(Q)) do
6. i ← citeste(Q); elimina(Q); S ← S ∪ {i}
7. for (fiecare vârf j în listaDeAdiacExt(i)) do
8. if (cheie[j] > cheie[i] + w(i,j) then
9. tata[j] ← i
10. cheie[j] ← cheie[i] + w(i,j)
end
Structuri de date 2013 - 2014 40
O(n lg n + m)
Alg. lui Dijkstra – exemplu (s=0)
0
21
10
2 3 9
1∞ ∞
0
Structuri de date 2013 - 2014 41
0
34
2 3
5 7
2
4 6
Q=[(0,0), (1,∞), (2,∞), (3,∞), (4,∞) ]
∞ ∞
0
Alg. lui Dijkstra – exemplu
0
21
10
2 3 9
110 ∞
0
Structuri de date 2013 - 2014 42
0
34
2 3
5 7
2
4 6
Q=[ (1,10), (2,∞), (3,∞), (4,5) ]
5 ∞
0
Alg. lui Dijkstra – exemplu
0
21
10
2 3 9
18 14
0
Structuri de date 2013 - 2014 43
0
34
2 3
5 7
2
4 6
Q=[ (1,8), (2,14), (3,7) ]
5 7
0
Alg. lui Dijkstra – exemplu
0
21
10
2 3 9
18 13
0
Structuri de date 2013 - 2014 44
0
34
2 3
5 7
2
4 6
Q=[ (1,8), (2,13) ]
5 7
0
Alg. lui Dijkstra – exemplu
0
21
10
2 3 9
18 9
0
Structuri de date 2013 - 2014 45
0
34
2 3
5 7
2
4 6
Q=[ (2,9) ]
5 7
0
Alg. lui Dijkstra – exemplu
0
21
10
2 3 9
18 9
0
Structuri de date 2013 - 2014 46
0
34
2 3
5 7
2
4 6
Q=[ ]
5 7
0
Alg. lui Dijkstra – exemplu
0
21
10
2 3 9
18 9
0
Structuri de date 2013 - 2014 47
0
34
2 3
5 7
2
4 6
5 7
0
Cuplaj bipartit maxim
• Un graf bipartit este un graf neorientat G=(V, E), fără vârfuri izolate, a.î. V = L ∪ R și toate muchiile din E sunt între L și R.
• Un cuplaj în G este o submulțime de muchii M a.î. pentru fiecare vârf v ∈ V, există cel mult o pentru fiecare vârf v ∈ V, există cel mult o muchie în M incidentă în v.
• Un cuplaj M în G este maxim dacă pentru orice alt cuplaj M’ în G avem |M| ≥ |M’|.
• Un vârf v ∈ V este cuplat de cuplajul M dacă există o muchie în M incidentă în v.
Structuri de date 2013 - 2014 48
Exemplu
0
1
2
6
Structuri de date 2013 - 2014 49
5
3
8
6
4
7L
R
Cuplaj bipartit maxim
• Fie G = (V, E) un graf bipartit și M un cuplaj în G. Se numește drum de creștere relativ la M un drum P în G care leagă două vârfuri necuplate și care este compus alternativ din muchii din U-M și M.
• Observații:• Observații:– |P| este impar;
– M’ = M xor P este un cuplaj în G a.î. |M’| > |M| .
• Corolar: Un cuplaj M în G este maximal dacă și numai dacă nu există în G drumuri de creștere relative la M.
Structuri de date 2013 - 2014 50
Cuplaj bipartit maxim - algoritm
procedure CuplajBipartitMaxim(G)
begin
1. M ← ∅
2. while (există P un drum de creștere
relativ la M) dorelativ la M) do
3. M ← M xor P
end
Structuri de date 2013 - 2014 51
O(m √n) (Hopcroft & Carp, SIAM J. of Comp.1973)
Cuplaj bipartit maxim - exemplu
0
1
2
6
Structuri de date 2013 - 2014 52
5
3
8
6
4
7
Cuplaj bipartit maxim - exemplu
0
1
2
6
Structuri de date 2013 - 2014 53
5
3
8
6
4
7
Cuplaj bipartit maxim - exemplu
0
1
2
6
Structuri de date 2013 - 2014 54
5
3
8
6
4
7
Cuplaj bipartit maxim - exemplu
0
1
2
6
Structuri de date 2013 - 2014 55
5
3
8
6
4
7
Cuplaj bipartit maxim - exemplu
0
1
2
6
Structuri de date 2013 - 2014 56
5
3
8
6
4
7
