====== 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 [[home:inf:ap16|Triedenie]]. ===== Procházení grafu do hloubky a do šířky ===== ==== Prohledávání do hloubky ==== {{:home:inf:obrdohloubky.png|}} 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. {{:home:inf:hloubka.jpg|}} 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) - CLOSED = \emptyset, OPEN = {//S//0}, kde //S//0 je počáteční stav. Je-li //S//0 současně i cílový stav, pak ukonči prohledávání. - Je-li OPEN prázdný, řešení neexistuje → ukonči prohledávání! - Vyber a současně vymaž první stav ze seznamu OPEN, označ jej //i// a zapiš jej do seznamu CLOSED. - Pokud se hloubka uzlu //i// rovná maximální přípustné hloubce MAX, pokračuj krokem č. 2. - 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. - Zapiš všechny následovníky stavu //i//, kteří nejsou v seznamu CLOSED na začátek seznamu OPEN. - 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. {{:home:inf:dohloubky.gif|}} Pro znovuzobrazení postupu refreshuj..:) {{:home:inf:dohloubky2.gif|}} 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. {{:home:inf:graf_hloubka.jpg|}} 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. - CLOSED = \emptyset, OPEN = {//S//0}, kde //S//0 je počáteční stav. Je-li //S//0 současně i cílový stav, pak ukonči prohledávání. - Je-li OPEN prázdný, řešení neexistuje → ukonči prohledávání! - Vyber a současně vymaž první stav ze seznamu OPEN, označ jej //i// a zapiš jej do seznamu CLOSED. - 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. - Zapiš všechny následovníky stavu //i//, kteří nejsou v seznamu CLOSED na začátek seznamu OPEN. - 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:// {{:home:inf:graf_2.jpg|}} **Výsledek:** {{:home:inf:graf_3.jpg|}} {{:home:inf:do_sir.gif|}} {{:home:inf:dosirky2.gif|}} 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. {{:home:inf:graf_sirka.jpg|}} Ř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 ===== {{:home:inf:slozitost_znacky.jpg|}} =====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 = 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_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=\} 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 = , 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): {{:home:inf:tokyfulkerson.png?550|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|). {{:home:inf:kruskal.png|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. {{:home:inf:prim.png|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 ===== [[http://links.math.rpi.edu/applets/appindex/graphtheory.html|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> ~~DISCUSSION~~