1 ALGORYTMY GRAFOWE

2 REPREZENTACJE GRAFÓW G = ( V, E ) V = {1,2,...,n} E = { e1, ..., em } Macierz sąsiedztwa : A[1..n ,1..n] 1 (true) jeśli {i,j}  E A[i,j] = 0 (false) jeśli {i,j}  E O(n2) pamięci

3

4 Macierz incydencji : B[1..n ,1..m]1 (true) jeśli i  ej B[i,j] = 0 (false) jeśli i  ej O(nm) pamięci

5 2 1 3 4 5 6

6 Listy sąsiedztwa L [1..n], {Adj(i), i=1,...,n } L[i] = wskaźnik na początek listy sąsiadów wierzchołka i ( Adj(i) ) O(m) pamięci

7 1 2 3 4 / 1 2 3 4 5 2 / 1 3 3 / 1 2 4 / 1 5 5 / 1 4

8 PRZESZUKIWANIE W GŁĄB begin end;{ "Odwiedza" każdy wierzchołek grafu ; Wierzchołki “odwiedzone” mają kolor czarny } DFS-VISIT (u); {"Odwiedza" wierzchołki składowej spójności zawierającej wierzchołek u } begin kolor (u) := SZARY; for każdy v Adj (u) do if kolor (v) = BIAŁY then DFS-VISIT (v); kolor (u) := CZARNY; end; DFS (G); begin for każdy u  V(G) do kolor (u) := BIAŁY; for każdy u V(G) do if kolor (u) = BIAŁY then DFS-VISIT (u); end;

9 PRZESZUKIWANIE W GŁĄB begin{ "Odwiedza" każdy wierzchołek grafu ; Wierzchołki “odwiedzone” mają kolor czarny } DFS-VISIT (u); {"Odwiedza" wierzchołki składowej spójności zawierającej wierzchołek u } begin kolor (u) := SZARY; for każdy v Adj (u) do if kolor (v) = BIAŁY then begin (v) := u; DFS-VISIT (v); end; kolor (u) := CZARNY; DFS (G); begin 1. for każdy u  V(G) do kolor (u) := BIAŁY; (u) := -1; end; 3. for każdy u V(G) do if kolor (u) = BIAŁY then DFS-VISIT (u);

10 PRZESZUKIWANIE WSZERZBFS (G,s); {Jeśli G jest spójny, to odwiedza każdy wierzchołek grafu, jeśli niespójny, to odwiedza każdy wierzchołek składowej spójności zawierającej wierzchołek s .Wierzchołki “odwiedzone” mają kolor czarny } while Q <>  do begin u:= head (Q); for każdy v  Adj (u) do if kolor (v) = BIAŁY then begin kolor (v) = SZARY; ENQUEUE (Q,v); end; DEQUEUE (Q); kolor (u) := CZARNY; end begin for każdy uV(G)–{s} do kolor (u) := BIAŁY; kolor (s) := SZARY; Q := {s};

11 PRZESZUKIWANIE WSZERZBFS (G,s); {Jeśli G jest spójny, to odwiedza każdy wierzchołek grafu, jeśli niespójny, to odwiedza każdy wierzchołek składowej spójności zawierającej wierzchołek s .Wierzchołki “odwiedzone” mają kolor czarny } while Q <>  do begin u:= head (Q); for każdy v  Adj (u) do begin if kolor (v) = BIAŁY then begin kolor (v) = SZARY; (v) := u; ENQUEUE (Q,v); end; DEQUEUE (Q); kolor (u) := CZARNY; end end; begin 1. for każdy uV(G)–{s} do begin kolor (u) := BIAŁY; (u) := -1; end; 3. kolor (s) := SZARY; 4. Q := {s};

12 Testowanie czy dany graf jest spójny Wyznaczanie składowych spójności ZASTOSOWANIE METOD Wybrane zastosowania : ( inne w dalszej części wykładu ) Testowanie czy dany graf jest spójny Wyznaczanie składowych spójności Znajdowanie drogi

13 MST – PRIM (G, w, r ); begin Q := V(G);{Wyznacza zbiór krawędzi ET = { {v, (v)}: v V(G) – {r} } minimalnego drzewa spinającego grafu G} begin for każdy u  V(G) do key(u) := ; key(r) := 0; (r) := -1; { utwórz kolejkę priorytetową Q } Q := V(G); while Q <>  do begin u := EXTRACT-MIN (Q); for każdy v  Adj(u) do if v  Q and w(u,v) < key(v) then (v) := u; key(v) := w(u,v) end end;

14 {Wyznacza zbiór ET krawędzi minimalnego drzewa spinającego grafu G}MST-KRUSKAL (G, w); {Wyznacza zbiór ET krawędzi minimalnego drzewa spinającego grafu G} begin ET := ; for każdy v  V(G) do MAKE – SET (v); posortuj krawędzie z E(G) niemalejąco względem wag w ; for każda krawędź {u,v}  E(G) (w kolejności niemalejących wag) do if FIND-SET (u) <> FIND-SET (v) then begin ET := ET  {{u,v}}; UNION (u,v) end ; return ET

15 CONNECTED_COMPONENT(G);{ Wyznacza rodzinę zbiorów rozłącznych; każdy zbiór zawiera wierzchołki jednej składowej spójności grafu G} begin for każdy wierzchołek v  V(G) do MAKE-SET(v); for każda krawędź {u,v}  E(G) do if FIND-SET(u) <> FIND-SET(v) then UNION (u,v); end;

16 SAME-COMPONENT(S, u,v);{ Testuje czy wierzchołki u i v należą do tej samej składowej spójności grafu } begin if FIND-SET(u) = FIND-SET(v) then return TRUE else return FALSE; end;

17 NAJKRÓTSZE DROGI W GRAFIE ZORIENTOWANYM

18 -4 s a s b 20 3 6 5 s 8 s c g s s s d -3 2 7 3 s e f f -6

19 { Może zmniejszyć wartość d(v) i zmienić (v) }RELAX (u, v, w); { Może zmniejszyć wartość d(v) i zmienić (v) } begin if d(v) > d(u) + w(u,v) then d(v) := d(u) + w(u,v); (v) := u end end; u v 3 4 9 u v 3 4 7

20 {Wyznacza odległość każdego wierzchołka grafu G od wierzchołka s ;DIJKSTRA (G, w, s); {Wyznacza odległość każdego wierzchołka grafu G od wierzchołka s ; w : E(G)  R 0 } S := ; Q := V(G); while Q <>  do begin u := EXTRACT-MIN (Q); S := S  {u}; for każdy v  Adj(u) do RELAX (u, v, w); end end; begin for każdy v  V(G) do d(v) := ; (v) := NIL; end; d(s) := 0; d(u) + w(u,v) then return FALSE; return TRUE. end; begin. for każdy v  V(G) do. d(v) := ; (v) := NIL; end; d(s) := 0;", "width": "800" } 22 a b 5   -2 6 e -3 7 8 2 -4 7   9 c d Kolejność krawędzi : (a,b), (a,c), (a,d), (b,a), (c,b), (c,d), (d,b), (d,e), (e,a), (e,c) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/59992/1/images/22/a+b.+5.+%EF%82%A5+%EF%82%A5+-2.+6.+e.+-3.+7.+8.+2.+-4.+7.+%EF%82%A5+%EF%82%A5+9.+c.+d.+Kolejno%C5%9B%C4%87+kraw%C4%99dzi+%3A.jpg", "name": "a b. 5.   -2. 6. e. -3. 7. 8. 2. -4. 7.   9. c. d. Kolejność krawędzi :", "description": "(a,b), (a,c), (a,d), (b,a), (c,b), (c,d), (d,b), (d,e), (e,a), (e,c)", "width": "800" } 23 a s  s d 2 7 3 s  f  -6 b c Kolejność krawędzi : (a,b), (b,c), (c,b), (c,d) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/59992/1/images/23/a+s+%EF%82%A5+s+d+2+7+3+s+%EF%82%A5+f+%EF%82%A5+-6+b+c+Kolejno%C5%9B%C4%87+kraw%C4%99dzi+%3A+%28a%2Cb%29%2C+%28b%2Cc%29%2C+%28c%2Cb%29%2C+%28c%2Cd%29.jpg", "name": "a s  s d 2 7 3 s  f  -6 b c Kolejność krawędzi : (a,b), (b,c), (c,b), (c,d)", "description": "a s  s d 2 7 3 s  f  -6 b c Kolejność krawędzi : (a,b), (b,c), (c,b), (c,d)", "width": "800" } 24 FLOYD-WARSHALL (W); {Wyznacza macierz D(n) odległości miedzy każdą parą wierzchołków grafu reprezentowanego przez macierz wag W } begin D(0) := W; for k:=1 to n do for i := 1 to n do for j := 1 to n do Dij(k) := min { Dij(k-1) , Dik(k-1) + Dkj(k-1) }; return D(n) end;

21 BELLMAN – FORD (G, w, s); { Testuje czy graf ma cykle ujemnej długości ; jeśli nie ma, to znajduje odległość każdego wierzchołka grafu G od wierzchołka s ; w : E(G)  R } for i := 1 to |V(G)| - 1 do for każda krawędź {u,v}  E(G) do RELAX (u, v, w); if d(v) > d(u) + w(u,v) then return FALSE; return TRUE end; begin for każdy v  V(G) do d(v) := ; (v) := NIL; end; d(s) := 0;

22 a b 5   -2 6 e -3 7 8 2 -4 7   9 c d Kolejność krawędzi : (a,b), (a,c), (a,d), (b,a), (c,b), (c,d), (d,b), (d,e), (e,a), (e,c)

23 a s  s d 2 7 3 s  f  -6 b c Kolejność krawędzi : (a,b), (b,c), (c,b), (c,d)

24 FLOYD-WARSHALL (W); {Wyznacza macierz D(n) odległości miedzy każdą parą wierzchołków grafu reprezentowanego przez macierz wag W } begin D(0) := W; for k:=1 to n do for i := 1 to n do for j := 1 to n do Dij(k) := min { Dij(k-1) , Dik(k-1) + Dkj(k-1) }; return D(n) end;