algoritmica grafurilor ii. reprezentari, parcurgeri în …mihai-suciu/graf/curs02.pdf · ·...

Algoritmica grafurilorII. Reprezentari, parcurgeri în

grafuri, drumuriMihai Suciu

Facultatea de Matematica și Informatica (UBB)Departamentul de Informatica

Martie, 7, 2018Mihai Suciu (UBB) Algoritmica grafurilor Martie, 7, 2018 1 / 48

Conţinut

1 Reprezentari ale grafurilorLista de adiacentaMatrice de adiacentaExemple

2 Parcurgeri in latime si adancimeParcurgere in latimeParcurgere in adancimeExempleKosaraju

3 Cel mai scurt drum

4 Algoritmul lui Dijkstra

Mihai Suciu (UBB) Algoritmica grafurilor Martie, 7, 2018 2 / 48

Reprezentari ale grafurilor

Reprezentări

în general se alege una din doua variante pentru a reprezenta un grafG=(V,E):

liste de adiacenţamatrice de adiacenţa

ambele variante pot fi folosite pentru grafuri orientate sau neorientatedeoarece reprezentarea prin lista de adiacenţa este mult mai compactaeste de preferat în cazul grafurilor rare

Graf rarun graf este rar daca |E | << |V |2


Reprezentari ale grafurilor

Reprezentări (II)

reprezentarea prin matrice de adiacenţa este preferata în cazulgrafurilor dense

Graf densun graf este dens daca |E | ≈ |V |2

sau când trebuie sa stabilim rapid daca o muchie (sau un arc) leagadoua vârfuri


Reprezentari ale grafurilor Lista de adiacenta

Listă de adiacenţă

pentru un graf G = (V ,E ) lista de adiacenţa reprezinta o matrice de|V | liste

Lista de adiacenţă pentru un nodfie x ∈ V (G), lista de adiacenţa pentru nodul x , Adj[x ], conţine toatevârfurile j astfel încât {x , j} ∈ E (G)

Adj[x ] consta din toate nodurile adiacente lui x din Gsuma lungimilor fiecarei liste într-un

graf orientat este |E |graf neorientat este 2|E |

pentru un graf ponderat se salveaza ponderea împreuna cu vârful înlistareprezentarea sub forma de lista de adiacenţa necesita Θ(V + E )memorieMihai Suciu (UBB) Algoritmica grafurilor Martie, 7, 2018 5 / 48

Reprezentari ale grafurilor Matrice de adiacenta

Matrice de adiacenţă

un dezavantaj al listei de adiacenţa este: nu putem determina rapiddaca muchia {x , y} aparţine grafului Gtrebuie cautat vârful y în Adj[x ]pentru a elimina acest dezavantaj se folosește matricea de adiacenţa

Matrice de adiacenţăfie un graf G = (V ,E ), reprezentarea sub forma de matrice de adiacenţaA = (aij) pentru G este o mtrice de dimensiune |V |x |V | unde

aij ={

1, (i , j) ∈ E0, (i , j) /∈ E



Matrice de adiecenţă (II)

matricea de adiacenţa necesita Θ(V 2) memoriepentru un graf neorientat A este simetrica de-a lungul diagonaleiprincipalepentru grafuri orientate aij este ponderea muchieiavantaje:

reprezentare mai simplapentru un graf neorientat și neponderat este nevoie de un singur bitpenru un element din matrice



Matrice de incidenţă

matrice de incidenţămatricea de incidenţa pentru un graf simplu orientat G = (V ,E ) este omatrice, B = (bij), de dimensiunea |V |x |E | unde

bij =

1, ∃j ∈ V |e = {i , j},−1, ∃j ∈ V |e = {j , i}, i ∈ V , e ∈ E0, altfel

E fiind sortata.


Reprezentari ale grafurilor Exemple

Exemplu - graf neorientat

graf → lista adiacenţa → matrice de adiacenţa

1 2

3

45



Lista de adiacenţă şi matricea de adiacenţă

2 5 /

1 5 3 4 /

2 4 /

2 5 3 /

4 1 2 /

1

2

3

4

5

A =

0 1 0 0 11 0 1 1 10 1 0 1 00 1 1 0 11 1 0 1 0



Exemplu - graf orientat

graf → lista adiacenţa → matrice de adiacenţa

1 2 3

4 5 6



Lista de adiacenţă şi matricea de adiacenţă

2 4 /

5 /

6 5 /

2 /

4 /

6 /

1

2

3

4

5

6A =

0 1 0 1 0 00 0 0 0 1 00 0 0 0 1 10 1 0 0 0 00 0 0 1 0 00 0 0 0 0 1



Exemplu - graf orientat, matricea de incidenţă

1

2

3

4

5

1

6

4

2

53

B =

1 1 −1 0 0 0−1 0 1 1 0 −10 −1 0 −1 0 00 0 0 0 1 10 0 0 0 −1 0


Parcurgeri in latime si adancime Parcurgere in latime

Parcurgere în lăţime (Breadth-first search BFS)

un algoritm simplu de cautare în grafurimai mulţi algoritmi folosesc idei similare BFS (Prim’sminimum-spanning-tree, Dijkstra’s single-source shortest-path)

algoritmul BFSdându-se un graf G = (V ,E ) și un vârf sursa s, algoritmul de parcurgereîn laţime exploreaza sistematic muchiile lui G pentru a descoperi fiecarevârf accesibil din s

algoritm pentru grafuri orientate / neorientatealgoritmul construiește un arbore cu radacina în s, arbore ce conţinetoate vârfurile accesibilepentru fiecare vârf v accesibil din s, lanţul simplu din arborereprezinta lanţul minim dintre s și vMihai Suciu (UBB) Algoritmica grafurilor Martie, 7, 2018 14 / 48


BFS (II)

se numește cautare în laţime deoarece algoritmul BFS descoperatoate vârfurile accesibile la distanţa k de vârful sursa dupa care trecela vârfurile de distanţa k + 1

Exemplu:pentru a urmari progresul sunt trei tipuri de vârfuri: albe, gri și negre:

alb - nu a fost vizitatnegru - daca {u, v} ∈ E , vârful u este negru, vârful v este negru sau grigri - poate avea adiacent vârfuri albe (vârfurile gri reprezinta frontieraîntre vârfurile descoperite și cele nedescoperite)

BFS construiește iniţial un arbore ce conţine doar vârful sursa s, suntadaugate vârfuri noi pe masura ce sunt descoperite



BFS (III)

procedura presupune graful reprezentat ca și lista de adiacenţaatributul π ţine vârful predecesor, atributul d ţine distanţa de la sursala nodul curent



BFS (IV) - proceduraBFS(G, s)

for fiecare vârf u ∈ G,V − {s} dou.color = albu.d = ∞u.π = NIL

end fors.color = gris.d = 0s.π = NILQ = ∅Enqueue(Q,s)while Q 6= ∅ do

u = Dequeue(Q)for fiecare v ∈ G.Adj[u] do

if v.color == alb thenv.color = griv.d = u.d + 1v.π = uEnqueue(Q,v)

end ifend foru.color = negru

end whileMihai Suciu (UBB) Algoritmica grafurilor Martie, 7, 2018 17 / 48


BFS

durata în timp a algoritmului este O(V + E )

Exemplu



BFS

BFS, vârfuri fara atribute

BFS(G,s):create a queue Qenqueue s onto Qmark sourcewhile Q is not empty:

dequeue an item from Q into vfor each edge e incident on v in Graph:

let w be the other end of eif w is not marked:

mark wenqueue w onto Q

Exemplu - click



BFS - drumuri / lanţuri elementare minime

BFS gasește distanţa de la nodul sursa s la nodurile accesibile din G

Lanţ elementar de distanţă minimăse definește lanţul elementar de distanţa minimia δ(s, v) de la vârful s lavârful v ca și lanţul elementar între s și v ce conţine numarul minim demuchii. Daca nu exista un lanţ elementar între vârfurile s și v atunciδ(s, v) =∞

Lemafie G = (V ,E ) un graf orientat sau neorientat și s ∈ V un vârf alesarbitrar. Pentru oricare arc / muchie {u, v} ∈ E

δ(s, v) ≤ δ(s, u) + 1.



BFS - drumuri / lanţuri elementare minime (II)

Lemafie G = (V ,E ) un graf orientat sau neorientat și BFS e rulat pe G dinnodul sursa s ∈ V . Dupa ce a terminat BFS, pentru fiecare v ∈ V ,valoarea v .d calculata de BFS satisface

v .d ≥ δ(s, v).

Lemadaca în timpul execuţiei BFS pe un graf G = (V ,E ) coada Q conţinevârfurile {v1, v2, ..., vr}, unde v1 este în vârful cozii și vr este vârful dincoada. vr .d ≤ v1.d + 1 și vi .d ≤ vi+1.d pentru i = 1, 2, ..., r − 1.



BFS - drumuri / lanţuri elementare minime (III)

Corolarfie vârfurile vi și vj introduse în coada pe parcursul execuţiei BFS, vârful vieste prelucrat înaintea lui vj . Atunci vi .d ≤ vj .d în momentul în care vjeste prelucrat.

Teorema: corectitudine BFSfie G = (V ,E ) un graf orientat sau neorientat și BFS e rulat pe G dinnodul sursa s ∈ V . Pe parcursul execuţiei BFS descopera fiecare vârfv ∈ V accesibil din s și la final v .d = δ(s, v),∀v ∈ V . Pentru orice vârfv 6= s care e accesibil din s, unul din lanţurile elementare de dimensiuneminima din s în v este un lanţ elementar de dimensiune minima din s înv .π urmat de muchia {v .π, v}.


Parcurgeri in latime si adancime Parcurgere in adancime

Parcurgere în adâncime (Depth-first search DFS)

algoritm de parcurgere care exploreaza muchiile vârfurilor noudescoperitedupa ce au fost explorate toate muchiile dintr-un vârf v , algoritmul seîntoarce la vârful muchiei care a dus în v și continua explorareaprocesul se repeta pâna au fost explorate toate vârfurile accesibile dinsursadaca ramân vârfuri neexplorate, DFS alege unul dintre ele ca și sursasi continua execuţia



DFS (II)

Exemplualgoritmul coloreaza vârfurile pe parcursul cautarii similar cu BFS,prin culoare se indica starea noduluipe lânga stare DFS marcheaza și timpul când a fost descoperit vârfulșî timpul când a fost explorat complet arborele din vârful descoperit

pentru a masura performanţa algoritmuluipentru a descoperi structura grafului

u.d marcheaza timpul când a fost descoperit vârful vu.f marcheaza timpul când a fost explorat vârful vstarea unui vârf: alb - u.d - gri - u.f - negru



DFS - procedura

DFS(G, s)

for fiecare vârf u ∈ G .V dou.color = albu.d = ∞u.π = NIL

end fortime = 0for fiecare u ∈ G .V do

if u.color == alb thenDFS_VISIT(G,u)

end ifend for



DFS - procedura (II)

DFS_VISIT(G, u)

time = time + 1u.d = timeu.color = grifor fiecare v ∈ G .Adj[u] do

if v.color == alb thenv .π = uDFS_VISIT(G,v)

end ifend foru.color = negrutime = time + 1u.f = time



DFS

durata în timp a algoritmului este:în timpul execuţiei bucla din DFS_VISIT se executa de |Adj[v ]| ori,deoarece ∑

v∈V|Adj[v ]| = Θ(E )

costul buclei este Θ(E )durata de execuţie a algoritmului este Θ(V + E )

Exemplu



DFS

procedura DFS, noduri fara atributeDFS(G,v) ( v is the vertex where the search starts )Stack S := ; ( start with an empty stack )for each vertex u, set visited[u] := false;push S, v;while (S is not empty) do

u := pop S;if (not visited[u]) then

visited[u] := true;for each unvisited neighbour w of u

push S, w;end if

end whileEND DFS()

Exemplu - click



DFS - proprietăţi

Teoremăfie G = (V ,E ) un graf orientat sau neorientat, în DFS pentru oricarenoduri u și v una din urmatoarele condiţii este adevarata:

intervalele [u.d , u.f ] și [v .d , v .f ] sunt disjuncte, u și v nu suntdescendenţi unul altuiaintervalul [u.d , u.f ] este inclus [v .d , v .f ], u este un descendent al lui vintervalul [v .d , v .f ] este inclus in [u.d , u.f ] și v este un descendent allui u


Parcurgeri in latime si adancime Exemple

Exemple

Relaţia: Din orice punct puteţi ajunge la orice punctCâte componente conexe are urmatorul graf?



Exemple (II)

facebook - sugestie de noi prieteni pe baza BFSnumarul Kevin Bacon / Erdos Pál



Exemple (II)



Exemple (III) - prelucrare de imagini

sa se caute stelele mai mari din imagine



Exemple (IV) - parcurgerea unui labirint

Algortmul lui Thremaux - secolul 19, bazat pe DFS



Graf tare conex, slab conex

Fie un graf orientat G = (V ,E )

Graf tare conexun graf orientat este tare conex daca între oricare doua vârfuri ale grafuluiexista un drum.

graf tare conex - prin oricare doua vârfuri trece cel puţin un circuit

Graf slab conexîntre oricare doua vârfuri u și v ale grafului exista un drum de la u la v saude la v la u, nu exista ambele drumuri.



Exemplu

componente conexe pe grafuri orientate / neorientate (DFS)



Exemplu DFS

Închiderea tranzitiva a unui graf


Parcurgeri in latime si adancime Kosaraju

Algoritmul Kosaraju - Sharir

algoritm pentru determinarea componentelor tare conex dintr-un graforientatpași

DFS cu vârfurile puse pe o stivaDFS pe complementul grafului

Exemplu - click


Cel mai scurt drum

Cel mai scurt drum / lanţ

pentru un graf neponderat, orientat sau neorientat, putem folosialgoritmul lui Moore pentru a gasi cel mai scurt drum / lanţnotaţii

u - nodul sursal(v) - lungimea drumuluip(v) - parintele vârfului vQ - o coada


Cel mai scurt drum

Algoritmul lui Moore

Moore(G , u)1. l(u) := 02. for toate vârfurile v ∈ V (G), v 6= u do3. l(v) :=∞4. Q = ∅5. u → Q6. while Q 6= ∅ do7. Q → x8. for toţi vecinii y ∈ N(x) do9. if l(y) =∞ then10. p(y) := x11. l(y) := l(x) + 112. y → Q13. return l , p


Cel mai scurt drum

Algoritmul lui Moore (II)

știind l , p, v cum putem afla drumul

Moore_drum(l , p, v)1. k := l(v)2. uk := v3. while k 6= 0 do4. uk−1 := p(uk)5. k := k − 16. return u


Cel mai scurt drum

Exemplu


Algoritmul lui Dijkstra

Dijkstra

Dijkstra(G , u)1. S := {u}, T := V \ S, l(u) := 02. for fiecare v ∈ V , v 6= u do3. l(v) :=∞4. x := u5. while T 6= ∅ do6. for fiecare v ∈ N(x) ∩ T do7. if l(v) > l(x) +W(x , v) then8. l(v) := l(x) +W(x , v)9. p(v) := x10. fie x ∈ T : l(x) = min

y∈Tl(y)

11. S := S ∪ {x}, T := T \ {x}12. return l , p



Exemplu



Exemplu (II)



Exemplu (III)



Exemplu (IV)



Exemplu (V)


algoritmica grafurilor ii. reprezentari, parcurgeri în …mihai-suciu/graf/curs02.pdf · ·...

Documents