AP17, IN16 Grafové algoritmy

IN (procházení grafu do hloubky a do šířky, složitost procházení grafu, komponenty souvislosti, hledání nejkratších cest, toky v sítích, kostra grafu)
AP (procházení grafu do hloubky a do šířky, složitost procházení grafu)
Pre IN otázka nadväzuje na Triedenie.

Prohledávání do hloubky (v angličtině označované jako depth-first search nebo zkratkou DFS) je grafový algoritmus pro procházení grafů metodou backtrackingu. Pracuje tak, že vždy expanduje prvního následníka každého vrcholu, pokud jej ještě nenavštívil. Vrcholy k procházení ukládá do zásobníku (LIFO). Pokud narazí na vrchol, z nějž už nelze dále pokračovat (nemá žádné následníky nebo byly všichni navštíveni), vrací se zpět backtrackingem.

Backtracking (česky zpětné vyhledávání) je způsob řešení algoritmických problémů založený na metodě pokus – omyl. Jedná se o vylepšení hledání řešení hrubou silou v tom, že velké množství potenciálních řešení může být vyloučeno bez přímého vyzkoušení. Algoritmus je založen na procházení do hloubky možných řešení.

Algoritmus je úplný (vždy najde řešení, tzn. určitý cílový vrchol, pokud existuje), ale není optimální (pokud graf není strom, nemusí najít nejkratší možnou cestu k cíli). Jeho asymptotická složitost je O(|V| + |E|), kde V je množina vrcholů a E množina hran daného grafu.

Podle pořadí, ve kterém se prochází uzly uspořádaného stromu, se rozlišují tři metody.

Výsledky způsobů procházení v binárním vyhledávacím stromu:

N = navštívený uzel, L = levý, R = pravý

• Preorder (NLR): F, B, A, D, C, E, G, I, H
• Inorder (LNR): A, B, C, D, E, F, G, H, I
• Postorder (LRN): A, C, E, D, B, H, I, G, F
• (Procházení do šířky (po vrstvách) Level-order: F, B, G, A, D, I, C, E, H)

Pro znovuzobrazení postupu refreshuj..:)

 
procedure dfs (G:Graph; var W:Nodeset; var P:Nodearray); 
procedure dfs1 (u:Node); 

begin 
  if not marked (u) 
     then begin mark (u); 
                for v in Successors (u) do 
                   begin P[v] := u; 
                      dfs1 (v) 
                   end 
           end 
  end; 

 
begin {dfs} 
    for u in V do begin unmark (u); 
                           P[u] := empty 
                  end; 
    for u in W do 
          if not marked (u) then dfs1 (u) 
end; 

Prohledávání do šířky (anglicky Breadth-first search, zkráceně BFS) je grafový algoritmus, který postupně prochází všechny vrcholy v dané komponentě souvislosti. Algoritmus nejprve projde všechny sousedy startovního vrcholu, poté sousedy sousedů atd. až projde celou komponentu souvislosti.

Prohledávání do šířky je algoritmus či metoda, která postupuje systematickým prohledáváním grafu přes všechny uzly. Nepoužívá při svém prohledávání žádnou heuristickou analýzu, pouze prochází všechny uzly a pro každý projde všechny jeho následovníky. Přitom si poznamenává předchůdce jednotlivých uzlů a tím je poté vytvořen strom nejkratších cest k jednotlivým uzlům z kořene (uzlu, ve kterém jsme začínali) v hranově neohodnoceném grafu.

Z hlediska algoritmu, veškeré následovníky uzlu získané expanzí uzlu vkládáme do FIFO fronty. FIFO fronta znamená, že první uzel, který do fronty vstoupil, ji také první opustí. V typických implementacích jsou dosud neobjevené označeny jako FRESH. Uzly, které se dostávají do fronty a jsou v této chvíli právě vyšetřovány na jejich následníky, jsou označeny jako OPEN a naposled uzly, které už byly z fronty vybrány a dále se s nimi nebudeme pracovat, jsou označeny jako CLOSE. CLOSE uzly již nikdy v tomto běhu algoritmu nebudou prozkoumávány, mají vyplněné všechny informace. To znamená vzdálenost od kořenového (počátečního) uzlu, stav uzlu (CLOSE) a předchůdce.

Příklad procházení do šířky při vzdálenosti měst:

Výsledek:

Algoritmus z FIMUNI

Prohledávat graf do šířky od nějakého uzlu x, znamená, že na začátku dáme do fronty FIFO uzel x. Následně vždy z fronty vybereme prvek, zapíšeme jej, a do fronty přidáme jeho následovníky.

 
procedure bfs (G:Graph; var W:Nodeset; var P:Nodearray); 
  var Q:Queue; 
  procedure bfs1 (q:Queue); 
     begin while not (isempty(q)) do 
         begin u := headq(q); 
              dequeue(q); 
              for v in Successors (u) do 
                  if not (marked(v)) 
                     then begin mark (v); 
                            enqueue (v,q); 
                            P[v] := u 
                          end 
         end 
      end{bfs1}; 

 
begin {bfs} 
   for u 2 V do begin unmark (u); 
                     P[u] := empty 
                end; 
    Q := emptyq; 
    for u in W do 
       begin mark (u); 
         enqueue (u,Q) 
       end; 
    bfs1 (Q) 
end {bfs} 

Celková složitost algoritmu : O(|V| + |E|), kde V je množina vrcholů a E množina hran daného grafu.

Asymptotická časová složitost algoritmu je O(|V| + |E|), kde V je množina vrcholů a E je množina hran grafu.

Prostorová složitost je O(|V| + |E|). Řečeno jinak, prostorová složitost je O(B^M), kde B je nejvyšší stupeň větvení stromu a M je nejvyšší délka cesty ve stromě. Tento velký nárok na prostor ve srovnání s nárokem prohledávání do hloubky je důvod, proč je prohledávání do šířky nepraktické pro rozsáhlejší problémy.

Asymptotická složitost: Řazení hran má asymptotickou složitost O(|H| · log |H|), množinový rozklad pak O(|H| · log* |U|), kde log* je velmi pomalu rostoucí inverzní Ackermannova funkce s jedním parametrem. Celková asymptotická složitost Borůvkova-Kruskalova algoritmu je tedy O(|H| · log |H|).

Asymptotická složitost: Počáteční nastavení má asymptotickou složitost O(|U|), získání minimálního prvku z fronty zabere čas O(|U| · log |U|). For cyklus přes všechny sousedy uzlu se provede O(|H|)-krát a zjištění, zda je prvek ve frontě (ke kterému dochází uvnitř tohoto cyklu) trvá O(log |U|). Celková asymptotická složitost Jarníkova-Primova algoritmu je tedy O(|U|) + O(|U| · log |U|) + O(|H| · log |U|) = O(|H| · log |U|).

složitost O(|U|²), při implementaci haldou O(|H|·log|U|)

složitost obecně O(|U|·|H|), pro acyklické grafy lze upravit na O(|U|+|H|) (topologické uspořádání uzlů)

operační složitost O(|U|3), paměťová O(|U|2)

Nech G=(V,E), komponenta súvislosti je maximálna podmnožina , pre ktorú platí, že medzi každými 2 vrcholmi vedie neorientovaná cesta. Ak v celom grafe medzi každými 2 vrcholmi vedie cesta, graf je súvislý (komponenta súvislosti je v tom prípade celý graf).
Všetky komponenty súvislosti môžeme nájsť pomocou prehľadávania do šírky.

Daný je orientovaný graf G=(V,E) spolu s ohodnotením hrán . Sled má dĺžku, ktorá je súčtom jeho hrán:
Cyklus nazývame záporný cyklus práve keď jeho dĺžka .
Definujeme dĺžku najkratšej cesty z u do v:

• ak neexistuje cesta z u do v
• ak nejaká cesta z u do v obsahuje vrchol patriaci zápornému cyklu
• inak (p je sled medzi u a v)

Hlavné problémy spojené s najkratšími cestami a algoritmy, ktoré sa používajú k ch riešeniu:

• Najkratšie cesty z daného vrcholu s do ostatných vrcholov grafu. Algoritmy: Bellman-Fordov alg., Alg. pre acyklické grafy, Dijkstrov alg. pre grafy s nezápornými dĺžkami hrán
• Najkratšie cesty medzi všetkými dvojicami vrcholov grafu. Algoritmy: alg. založený na násobení matíc, Floyd-Warshallow alg., Johnsonov alg. pre riedke grafy

Pre každý vrchol udržujeme hodnotu p[v] - otec vrchola v (na začiatku je p[v] = Nil), hodnotu d[v] - dlĺžka cesty z s do v v aktuálnom grafe indukovanom hranami (p[v],v). Iniciálna hodnota je pre rovná a . Na konci výpočtu je .

Algoritmus Bellman-Ford je založený na postupnom zlepšovaní hodnôt d[u]. Ak vrcholu u zlepšíme hodnotu d[u], musíme následne preskúmať všetky hrany a ak je to možné, zlepšiť hodnotu d[v] (operácia RELAXACIA). Algoritmus vráti true práve ak graf neobsahuje cyklus zápornej dĺžky dosiahnuteľný z koreňa s.

BELLMAN-FORD(G,w,s) 
1 INICIALIZACIA(G,s) 
2 for i=1 to |V|-1 do 
3   for kazdu hranu (u,v) ∈ H do RELAXACIA(u,v,w) od 
4 od 
5 for kazdu hranu (u,v) ∈ H do 
6   if d[v] > d[u] + w(u,v) then return false fi od 
7 return true 

INICIALIZACIA(G,s) 
1 for kazdy vrchol v ∈ V do 
2  d[v] ← ∞; p[v] ← Nil od 
3 d[s] ← 0 

RELAXACIA(u,v,w) 
1 if d[v] > d[u] + w(u,v) 
2   then d[v] ← d[u] + w(u,v); p[v] ← u fi 

Zložitosť algoritmu je O(|V|·|H|) (vidieť to z algoritmu).

Graf musí mať nezáporné ohodnotenie hrán, aby na ňom Dijkstrov algoritmus korektne fungoval. Algoritmus udržuje množinu S vrcholov, pre ktoré sa už vypočítala dĺžka najkratšej cesty. Algoritmus opakovane vyberá vrchol s najkratšou cestou a relaxuje hrany vychádzajúce z u

DIJKSTRA(G,w,s) 
1  INICIALIZACIA(G,s) 
2  S ← Ø; Q ← V 
3  while Q ≠ Ø do 
4    u ← (u ∈ Q ∧ d[u] = min{d[x] | x ∈ Q} 
5    S ← S ∪ {u} 
6    Q ← Q \ {u} 
7    for kazdy vrchol v taky, ze (u,v) ∈ H do 
8       RELAXACIA(u,v,w) 
9    od 
10 od 

RELAXACIA a INICIALIZACIA sú tie isté procedúry ako v prípade Bellman-Fordovho algoritmu. Zložitosť závisí od spôsobu reprezentácie množiny Q, efektivity výberu prvku u s minimálnou hodnotou d[u] a aktualizácie hodnôt d[v] pre vrcholy susediace s u. Pre pole: , pre Fibonacciho haldu:

Daný je orientovaný graf s ohodnotením hrán bez záporných cyklov. Predpokladajme, že graf je zadaný maticou susednosti rozmerov . Nech je cesta v grafe. Vnútorné vrcholy cesty p sú vrcholy .

Pre ľubovoľnú dvojicu vrcholov uvažujeme všetky cesty z i do j, ktorých vnútorné vrcholy sú množiny , nech p je z nich najkratšia. Floydov-Warshallow algoritmus využíva vzťah medzi touto množinou ciest z i do j a množinou ciest z i do j, ktorých vnútorné vrcholy sú z množiny (dynamické programovanie).

• ak k nie je vnútorným vrcholom cesty p, tak najkratšia cesta z i do j s vnútornými vrcholmi z je zároveň najkratšou cestou z i do j s vnútornými vrcholmi z
• ak k je vnútorným vrcholom cesty p, tak cestu p môžeme rozdeliť na i→k→j, pričom cesta z i do k, aj cesta z k do j sú najkratšími cestami s vnútornými vrcholmi z

Označme dĺžku najkratšej cesty z i do j s vnútornými vrcholmi z množiny . Platí:

• ak k=0
• ak k ≥ 1

Algoritmus (D je matica najkratších ciest):
(riadok 5 je , nefunguje math v code :( )

FLOYD-WARSHALL(W) 
1 D(0) ← W 
2 for k=1 to n do 
3    for i=1 to n do 
4       for j=1 to n do 
5         uvedene vyssie 
6       od 
7    od 
8 od 
9 return D(n) 

Časová zložitosť algoritmu je .

Sieť G=(V,H) je orientovaný graf, ktorého každá hrana má nezápornú kapacitu (priepustnosť) . Ak , kladieme . Predpokladáme, že v sieti sú vyznačené dva vrcholy - zdroj s a cieľ t a že všetky vrcholy grafu ležia na nejakej ceste z s do t.

Tok v sieti G je funkcia spĺňajúca:

• kapacitné ohraničenia
• podmienky symetrie
• podmienky kontinuity platí (čo do vrcholu priteká, to z neho aj odteká)

Hodnota sa nazýva tok z u do v. Hodnota toku f je (súčet hodnôt vytekajúcich z s). Problém maximálneho toku v sieti je nájsť tok maximálnej hodnoty - používa sa Ford-Fulkersonova metóda.

Ford Fulkersonova metoda 
1 inicializuj tok f na 0 
2 while existuje zlepsujuca cesta p do 
3    zlepsi hodnotu toku na ceste p od 
4 return f 

Jedná sa o iteratívny algoritmus. Začína s tokom nulovej hodnoty a postupne zvyšuje hodnotu toku. V každej iterácii hľadá tzv. zlepšujúcu cestu z s do t, po ktorej môže zvýšiť hodnotu toku. Existujú rôzne varianty algoritmu podľa spôsobu hľadania zlepšujúcej cesty, jeden z nich je Ford-Fulkersonov algoritmus. Na jeho pochopenie potrebujeme zaviesť pomocné pojmy:

• reziduálna kapacita hrany (u,v) je (rezerva na danej hrane)
• reziduálna kapacita cesty p je

Ford Fulkersonov algoritmus 
1 for kazdu hranu (u, v) ∈ H do 
2    f[u, v] ← 0; f[v, u] ← 0 
3 od 
4 while existuje zlepsujuca cesta p do 
5     c_f (p) ← min{c_f (u, v) | (u, v) lezı na p} 
6     for kazdu hranu (u, v) na p do 
7        f[u, v] ← f[u, v] + c_f (p) 
8        f[v, u] ← −f[u, v] 
9     od 
10 od 
11 return f 

Obrázok, ktorý by to mal všetko objasniť (reziduálna sieť je graf s reziduálnymi kapacitami väčšími ako 0):
Ak v sieti G s celočíselnými kapacitami je |f*| hodnota maximálneho toku, cyklus 4-10 sa vykoná nanajvýš |f*| krát. Zložitosť jednej iterácie je rovná zložitosti nájdenia cesty z s do t a je O(|H|), celková zložitosť je O(|f*|.|H|).

Je daný súvislý neorientovaný graf spolu s ohodnotením hrán (váhovou funkciou) . Množinu nazveme kostrou grafu G, ak je graf súvislý a acyklický.
Definujeme váhu kostry K predpisom:
Minimálna kostra je potom kostra s minimálnou váhou.

Na nájdenie minimálnej kostry sa používajú 2 známe algoritmy: Kruskalov a Primov algoritmus.

Kruskalov algoritmus je príkladom hladového algoritmu. Množina K tvorí les. V každom kroku vyberáme hranu h s minimálnou váhou zo všetkých hrán spájajúcich rôzne komponenty z K.
Implementácia algoritmu využíva štruktúry UNION-FIND. V jednotlivých množinách sú práve vrcholy z rovnakej komponenty vzhľadom ku K.

Kruskal((V,H),w) 
1 K ← ∅ 
2 foreach v ∈ V do 
3     MAKE-SET(v) od //kazdy prvok dame do samostatnej mnoziny 
4 Zotried hrany podla w do neklesajucej postupnosti 
5 foreach (u, v) ∈ H v tomto poradı do 
6     if Find-Set(u) ≠ Find-Set(v) //su z roznych komponent 
7     then K ← K ∪ {u, v} //pridaj ich do kostry 
8        UNION(u, v) fi od //zjednot mnoziny 
9 return K 

Inicializácia (riadky 1-4) má zložitost Θ(|V|) + (|H| log |H|). Cyklus 5-8 prebehne |H| krát, celkovo sa teda prevedie Θ(|H|) operácıí Find-Set, Union, čo má zložitosť O(|H|α(|V|)). Celková zložitosť Kruskalovho algoritmu je .

Primov algoritmus je opäť príkladom hladového algoritmu. MnožinaK vždy tvorí jediný strom. Na začiatku zvolíme ľubovoľný vrchol r za koreň a postupne pridávame ďalšie vrcholy, resp. hrany. Tomuto koreňu priradíme ohodnotenie 0, zvyšným ∞. Efektívna implementácia Primovho algoritmu využíva štruktúru Q s operáciami EXTRACT-MIN a DECREASE-KEY.

Prim((V,H),w, r) 
1 Q ← V 
2 foreach v ∈ Q do 
3    key[v] ← ∞ od 
4    key[r] ← 0 
5    π[r] ← Nil 
6    while Q ≠ ∅ do 
7       u ← EXTRACT-MIN(Q) 
8       foreach v taky, ze (u, v) ∈ H do 
9           if v ∈ Q ∧ w(u, v) < key[v] 
10            then π[v] ← u 
11            DECREASE-KEY(Q, v,w(u, v)) fi od od 
12 return {(π[v], v) | v ∈ V, v ≠ r} 

Primov algoritmus postupne ohodnocuje vrcholy podľa hrán, ktoré do nich vedú,zo štruktúry Q odstráni vrchol, do ktorého vedie minimálna hrana. Uchovávame si pole predchodcov π - rodičov vo vytváranom strome, z ktorého na konci algoritmu vytvoríme kostru.
Celková zložitosť algoritmu je O(|V| log |V| + |H|) ak štruktúru Q implementujeme ako Fibonnaciho haldu.

http://ui.fpf.slu.cz http://zorro.fme.vutbr.cz skriptá z Návrhu algoritmov II

Užitečný applet, který dokáže simulovat různé algoritmy jako je Dijkstra, Bellman-Ford, Kruskal…

Petr Kott
petr.kott@post.cz
Dusan Katona, ICQ: <426 081 873>