AP17, IN16 Grafové algoritmy

Zadání

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.

Procházení grafu do hloubky a do šířky

Prohledávání do hloubky

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)

Algoritmus prohledávání do hloubky s omezením na maximální délku větve.

  1. CLOSED = \emptyset, OPEN = {S0}, kde S0 je počáteční stav. Je-li S0 současně i cílový stav, pak ukonči prohledávání.
  2. Je-li OPEN prázdný, řešení neexistuje → ukonči prohledávání!
  3. Vyber a současně vymaž první stav ze seznamu OPEN, označ jej i a zapiš jej do seznamu CLOSED.
  4. Pokud se hloubka uzlu i rovná maximální přípustné hloubce MAX, pokračuj krokem č. 2.
  5. Expanduj stav i. Pokud stav i nemá následovníky, nebo všichni následovníci byli již expandováni (tj. jsou v seznamu CLOSED), jdi na krok č. 2.
  6. Zapiš všechny následovníky stavu i, kteří nejsou v seznamu CLOSED na začátek seznamu OPEN.
  7. Pokud některý z následovníků stavu je cílovým stavem, tj. řešení bylo právě nalezeno, ukonči prohledávání, jinak pokračuj krokem č. 2.

Pro znovuzobrazení postupu refreshuj..:)

Algoritmus a příklad z FI MUNI

Prohledávat graf do hloubky od uzlu x znamená, že do zásobníku na počátku dáme prvek x.
Následně s každým výběrem prvku ze zásobníku do něj dáme jeho následovníky.

Algoritmus podle skript

Algoritmus dfs (depth-first search)

G = (V,E), V = \{1, \dots , n\}, W \subseteq V Budeme označovat všechny navštívené uzly pomocí procedury mark.
Na začátku jsou všechny uzly nenavštívené (marked(u) = False).
Pro každý uzel u je Successors(u) seznam uzlů-následníků uzlu u.
Vycházíme z uzlů z množiny W a postupujeme stále dál po hranách do dosud nenavštívených uzlů.
Cesty z označených do nově navštívených uzlů tvoří les s kořeny ve W.

Procházení grafu do hloubky – imperativní pseudokód

 
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; 

Chceme-li projít do hloubky všechny uzly grafu G = (V,E), položíme W = V.
Věta: Algoritmus dfs navštíví všechny uzly grafu dosažitelné z uzlů z množiny W.
Důkaz je zřejmý a plyne z toho, že se opakovaně označují všechny uzly, které dosud označeny nebyly. Množina neoznačených uzlů se zmenšuje, takže algoritmus konverguje.
Poznámka: Algoritmus funguje stejně pro orientované i neorientované grafy.

Prohledávání do šířky

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.

Jak to funguje?

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.

Algoritmus prohledávání do šířky

  1. CLOSED = \emptyset, OPEN = {S0}, kde S0 je počáteční stav. Je-li S0 současně i cílový stav, pak ukonči prohledávání.
  2. Je-li OPEN prázdný, řešení neexistuje → ukonči prohledávání!
  3. Vyber a současně vymaž první stav ze seznamu OPEN, označ jej i a zapiš jej do seznamu CLOSED.
  4. Expanduj stav i. Pokud stav i nemá následovníky, nebo všichni následovníci byli již expandováni (tj. jsou v seznamu CLOSED), jdi na krok č. 2.
  5. Zapiš všechny následovníky stavu i, kteří nejsou v seznamu CLOSED na začátek seznamu OPEN.
  6. Pokud některý z následovníků stavu je cílovým stavem, tj. řešení bylo právě nalezeno, ukonči prohledávání, jinak pokračuj krokem č. 2.

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.

Algoritmus podle skript

Řešíme problém Projít systematicky všechny uzly grafu G = (V,E) dosažitelné (orientovanou) cestou z některého z počátečních uzlů zadaných množinou W \subseteq V.

Algoritmus bfs (breadth-first search) prochází uzly v jiném pořadí než při prohledávání do hloubky: uzly, které leží blíže počátečním uzlům (uzlům, v nichž procházení začíná), jsou navštíveny dříve než uzly ležící dále od počátečních uzlů.

Pomocné datové struktury: fronta Q uzlů, les nejkratších cest (uložený v poli P)
Navštívené uzly se opět označují pomocí procedury mark, uzel u bude označen, právě když marked(u) = True.

Procházení grafu do šířky – imperativní pseudokód

 
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} 

Věta: Nechť G = (V,E), s, u, v \in V a nechť vzdálenost z s do u je menší než vzdálenost z s do v. Pak uzel u bude při výpočtu bfs(G,{s}) označen dříve než uzel v.

Důkaz: Stačí ukázat, že do fronty Q jsou vždy přidávány uzly s aspoň tak velkou vzdáleností od s, než jakou měl poslední přidaný uzel. To však lehce plyne indukcí podle vzdálenosti od uzlu s.

Věta: Nechť G = (V,E), s \in V. Pak po provedení výpočtu bfs(G,{s}) jsou navštíveny právě všechny uzly, do nichž vede z uzlu s (orientovaná) cesta.
Důkaz: Indukcí podle vzdálenosti od uzlu s.

Složitost procházení grafu do šířky Věta: Nechť G = (V,E) je graf a W \in V je množina počátečních uzlů (vstupního stupně 0). Pak délka výpočtu bfs(G,W) v nejhorším případě je v O(|W| + |E|).

Složitost procházení grafu

Složitost procházení do hloubky

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

Složitost procházení do šířky

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(BM), 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.

Borůvkův-Kruskalův algoritmus

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|).

Jarníkův-Primův algoritmus

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|).

Dijkstrův algoritmus

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

Bellmanův - Fordův algoritmus

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

Floyd - Warshall

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

Poznámka k složitosti

Komponenty súvislosti

Nech G=(V,E), komponenta súvislosti je maximálna podmnožina K \subset V , 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.

Hľadanie najkratších ciest

Daný je orientovaný graf G=(V,E) spolu s ohodnotením hrán w: H \rightarrow R. Sled p = <v_0,v_1,...,v_k> má dĺžku, ktorá je súčtom jeho hrán:
w(p) = \sum_{i=1}^{k} w(v_{i-1},v_i) Cyklus c = <v_0,v_1,...,v_k>, v_0 = v_k nazývame záporný cyklus práve keď jeho dĺžka w(c) < 0.
Definujeme dĺžku najkratšej cesty z u do v:

  • \delta(u,v) = \infty ak neexistuje cesta z u do v
  • \delta(u,v) = - \infty ak nejaká cesta z u do v obsahuje vrchol patriaci zápornému cyklu
  • \delta(u,v) = min\{w(p)|p=<u,...,v>\} 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

Bellman-Fordov algoritmus

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 v \neq s rovná d[v] = \infty a d[s] = 0. Na konci výpočtu je d[v] = \delta (s,v).

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 (u,v) \in H 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).

Dijkstrov algoritmus

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 u \in V\setminus S 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: O(|V|^2 + |H|) = O(|V|^2), pre Fibonacciho haldu: O(|V|log|V| + |H|)

Floyd-Warshallov algoritmus

Daný je orientovaný graf G=(V,H), V = \{1,2,..,\} s ohodnotením hrán w:\ H \rightarrow R bez záporných cyklov. Predpokladajme, že graf je zadaný maticou susednosti rozmerov n \times n, W = (w_{ij}). Nech p = <v_1,v_2,...,v_l>, l \geq 2 je cesta v grafe. Vnútorné vrcholy cesty p sú vrcholy v_2,...,v_{l-1}.

Pre ľubovoľnú dvojicu vrcholov i,j \in V uvažujeme všetky cesty z i do j, ktorých vnútorné vrcholy sú množiny \{1,2,...,k\} , 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 \{1,2,...,k-1\} (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 \{1,2,...,k-1\} je zároveň najkratšou cestou z i do j s vnútornými vrcholmi z \{1,2,...,k\}
  • 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 \{1,2,...,k-1\}

Označme d_{ij}^{k} dĺžku najkratšej cesty z i do j s vnútornými vrcholmi z množiny \{1,2,...,k\}. Platí:

  • d_{ij}^{k} = w_{ij} ak k=0
  • d_{ij}^{k} = min(d_{ij}^{k-1},d_{ik}^{k-1} + d_{kj}^{k-1}) ak k ≥ 1

Algoritmus (D je matica najkratších ciest):
(riadok 5 je d_{ij}^{k} \leftarrow min(d_{ij}^{k-1},d_{ik}^{k-1} + d_{kj}^{k-1}), 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 O(n^3).

Toky v sietiach

Sieť G=(V,H) je orientovaný graf, ktorého každá hrana (u,v) \in H má nezápornú kapacitu (priepustnosť) c(u,v) \geq 0. Ak (u,v) \not\in H, kladieme c(u,v) = 0. 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 f: V \times V \rightarrow R spĺňajúca:

  • kapacitné ohraničenia \forall u,v \in V:\ f(u,v) \leq c(u,v)
  • podmienky symetrie \forall u,v \in V:\ f(u,v) = -f(v,u)
  • podmienky kontinuity \forall u,v \in V\setminus\{s,t\} platí \sum_{u\in V} f(u,v) = 0 (čo do vrcholu priteká, to z neho aj odteká)

Hodnota f(u,v) sa nazýva tok z u do v. Hodnota toku f je |f| = \sum_{v\in V} f(s,v) (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 metóda a algoritmus

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 c_f(u,v) = c(u,v) - f(u,v) (rezerva na danej hrane)
  • reziduálna kapacita cesty p je c_f(p) = min\{c_f(u,v)| (u,v)\ lezi\ na\ p \}
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):
Ford Fulkersonov algoritmus 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|).

Kostra grafu

Je daný súvislý neorientovaný graf G = (V,H) spolu s ohodnotením hrán (váhovou funkciou) w: H \rightarrow R^{+}. Množinu K \subset H nazveme kostrou grafu G, ak je graf G' = (V,K) súvislý a acyklický.
Definujeme váhu kostry K predpisom:
w(K) = \sum_{h\in K}w(h) 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

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 O(|H|log|H|).
Kruskalov algoritmus

Primov algoritmus

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.
Primov algoritmus Celková zložitosť algoritmu je O(|V| log |V| + |H|) ak štruktúru Q implementujeme ako Fibonnaciho haldu.

Zdroje

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

Užitečné odkazy

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

Vypracoval

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

Diskuze

, 2008/06/11 22:30

Ahoj, vymenil jsem obrazky za nepruhlednou verzi, mel jsem s tim problemy s tiskem, tiskli se cele cerne.

, 2008/06/13 23:29

Diky..:)

, 2008/06/12 17:47

Nemá náhodou být u procházení do hloubky být místo „expanduje prvního následníka každého vrcholu“ být posledního následníka?
Podle mě se to prvně vždy podívá na všechny následníky a vybere toho na kterého narazilo jako poslední (struktura zásobník), ale moc si za tím nestojím :)

, 2008/06/13 23:21

NO, co ja pochopil tento algoritmus, tak se expanduje vzdy prvni naslednik.

, 2008/06/12 18:49

Kdyz se na to tak divam zacinam mit pocit ze jsme se to v navalu ucili trosku jinak, treba vysvetleni prohledavani grafu na zasobniku a fronte se mi zdalo lepsi. Proc to stavis na skriptech z jinych univerzit?

, 2008/06/15 19:32

Souhlasim, v navalu to se mi to zdalo jine. Taky se mi zda ze tam dost veci chybi.

, 2008/06/21 10:19

Doplnil jsem to o info ze skript z navalu. Vic jsem toho opravdu nenasel. Sorry. Vsak kdyztak doplnte,pkud neco chybi

, 2008/06/12 19:04

A není ten druhý obrázek špatně? Konkrétně předpředposlední krok - neměli bysme vycházet z uzlu sedm a ne znovu 5?

, 2008/06/13 23:20

nee, obrázek je ok. Vzdy prohledas celou podvrstu prvku u ktereho jsi.

, 2008/06/15 16:31

Pořád tomu nerozumím - Začneš prohledávat - prohedáš 2,5,7
v další kroku 2→6 5→3 a teď by snad mělo být 7→1 nebo ne? A proč?

, 2008/06/21 10:18

Nemas pravdu.
Musis vzdy projit vsechny nasledniky uzlu. Tj, 5ka ma dva. 5→3, 5→4

, 2008/06/12 19:46

muzu se jeste hloupe zeptat, co znamena u casove slozitosti ta absolutni hodnota? O(|V| + |E|)

, 2008/06/12 20:15

mohutnost mnoziny :) cize pocet uzlov a hran grafu

, 2008/06/15 21:52

No ja to tak chapal, ale bylo psano ze V je pocet vrcholu, a ne mnozina vrcholu … toz tak

, 2008/06/13 23:58

Takže by zde mělo být vše ze skript. Stránku jsem doplnil o sekce „algoritmus podle skript“, kde je vše uvedeno jako v návalových skriptech.

, 2008/06/16 19:45

Ahoj, mam dotaz ku Kruskalovmu algoritmu. Podla mna je zle zapisane budovanie mnoziny K. Mali by sa do nej pridavat mnoziny prvkov, a nie jednotlive prvky. Teda u_v namiesto {u,v}. Ak sa mylim, opravte ma plz.

, 2008/06/17 07:36

V kazdej iteracii pridas hranu - cize (u,v) a zjednotis mnoziny, pekne to vidno na tom predpslednom obrazku - nepridas hranu 5, pretoze tie 2 vrcholy su v rovnakej mnozine, ale hranu 6 (cize jej 2 vrcholy, nie mnoziny). Inak je to presne opisane zo skript Navalu II.

Podla mojho nazoru vzhladom na rozsah tejto otazky (Triedenie + Grafove algoritmy spolu) je mozne v tych 15 min. pripravy + naslednych 7-8 minut rozpravy uviest akurat _princip_ jednotlivych algoritmov, pripadne ich ukazat na nejakom priklade, pseudokod nestihnes uviest u vsetkych (max. u nejakych hlavnych alg. typu quicksort, bfs). Co si o tom myslite vy?

, 2008/06/18 14:10

Stale sa mi zda, ze pri tom postupe budem mat po skonceni v mnozine K nasypane nejake vrcholy…a ja chcem hrany…

Co sa tyka rozsahu otazky, plne suhlasim. Podla mna sa da stihnut akurat ich vymenovanie, zlozitosti a kratky opis.

, 2008/06/18 15:03

Ako na to pozeram, tak mozno mas pravdu…v tom pripade je ale chyba aj v skriptach z Navalu 2, asi tam teda ma byt {(u,v)}…

, 2008/06/20 15:14

Mam pripominku k prohledavani do hloubky. Je tu napsane ze je uplny, ale to neni pravda. Pokud algoritmus zacne expandovat nekonecnou vetev, na ktere nelezi reseni tak se k reseni nikdy nedostane. To same u prohledavani do sirky v pripadne nekonecneho vetveni grafu (ale ten se vetsinou neuvazuje).

, 2008/06/21 10:21

No, na to jsem nepomyslel. To neni typicke. Ale doplnim to. Za zminku to stoji

, 2008/06/22 16:29

Prohledavani do hloubky urcite neni uplne a je to jeden ze zakladnich rysu toho algoritmu. Je to potreba opravit, docela zasadni chyba.

, 2008/06/21 16:23

Tato otázka je zadána v jiné podobě pro BcAP a v jiné pro BcIN (první je zde nevlastní podmnožinou druhého). Přitom není zcela jasné, které části vypracování odpovídají kterému oboru. Kromě společného procházení do hloubky a do šířky mají BcAP do otázky zařazenu už jen „složitost procházení grafu“. To je ale aspoň podle mne poněkud neurčitý termín a těžko si představit, co se pod tím skrývá. Může se možná jednat pouze o složitost onoho procházení do hloubky a šířky. Pokud by se jednalo i o složitosti k jednotlivým algoritmům typu Borůvka, Kruskal apod. (jak to podle vypracované otázky vypadá teď), bylo by zase dost nelogické, proč nejsou v otázce pro BcAP zahrnuty i tyto algoritmy (resp. byl by myslím docela nesmysl muset znát jejich složitost, ale přitom ani nic základního o nich). Má někdo představu o tom, jak to je, resp. co se tou „složitostí procházení grafu“ mohlo skutečně myslet?

, 2008/06/21 18:19

Tato otazka je podle me dost nestastne zadana… pro BcIN je az moc obsahla (i s tridenim a se vsemi temi informacemi), pro BcAP je tam toho malo… na papir k tomu asi zas tak moc nenapisete a pak se na to komise taky muze divat, ze jsem toho moc nerekli a bude chtit vice podrobnosti a kde je pak ma clovek brat…? Ja osobne (BcAP) urcite budu zminovat i kostry grafu, hledani nejkratsich cest a toky v sitich na urovni, jak jsme je brali v Matematice s panem Slovakem.

, 2008/06/22 10:35

Souhlas, tato otazka je opravdu nestasne zadana co se rozsahu tyca ja na BcIN opravdu nevim co z tech 24 stran vybrat…. casove to vychazi na 2-4 vety ke kazdymu bodu

, 2008/06/22 10:55

ja ked som si tuto otazku vypracovaval na papier, zmienil som 3 alg zakladne (select sort, bubble a insert sort) po jednej vete, heap, merge a quick trochu viac - to mas tak do 6-7 minut, zvysnych 8-9 potom k jednotlivym pojmom nieco, algoritmy som vysvetloval na priklade, uviedol som ku kazdemu zlozitost (celkovo Dijkstra, Floyd-Warshall, Ford.fulk metoda a Kruskal - tak 1,5-2 min na jeden :) )
Inak tie algoritmy sa oplati naucit, ja ich pouzivam napr. aj v otazke IN19 Metody konstrukce efektivních algoritmů namiesto tych, co su tam teraz - rozdeluj a panuj mas mergesort, dyn.programovanie Floyd-Warshall a hladovy napr. Kruskal…akurat backtracking si musis vymysliet :)

, 2008/06/21 19:06

Rekl bych, ze DFS a BFS a jejich slozitosti odpovidaji BcAP, a cela otazka potom BcIN jako soucast otazky trideni. Preci jenom optimalni sledy, minimalni kostra a toky v sitich striktne receno neprochazeji graf.

, 2008/06/22 00:33

pridal jsem odkaz na sikovny applet, ktery pomuze pochopit chovani nekterych algoritmu, kdyby nestacilo, to co tu je :)

, 2008/06/27 21:08

Ahojte, zda se mi, ze ve slovnim popisu algoritmu prohledavani do sirky je chyba.
„5.Zapiš všechny následovníky stavu i, kteří nejsou v seznamu CLOSED na zacatek seznamu OPEN. “
Nemelo by tam byt „na konec seznamu OPEN“?

, 2008/06/28 00:58

Ten popis nerika, jakou pouziva algoritmus datovou strukturu a celkove se mi nelibi. Pravdu dis, pokud si myslis, ze by tam melo byt nejlepe „umisti do fronty“.

, 2010/06/04 14:36

V tom prehladavani do sirky je chyba, takto je to pouzite ako zasobnik, cize LIFO a nie FIFO, bud sa to hadze na koniec zoznamu alebo sa bere z konca zoznamu, ale nie ako je to tam teraz ze sa hadze na zaciatok aj zo zaciatku sa bere…

You could leave a comment if you were logged in.
home/inf/ap17.txt · Poslední úprava: 2014/10/27 09:07 (upraveno mimo DokuWiki)
Nahoru
CC Attribution-Noncommercial-Share Alike 3.0 Unported
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0