Prehľadávanie do hĺbky - História úprav

147.175.190.172: /* Preudokód */

2020-01-16T23:53:00Z

Preudokód

Juraj na 20:22, 16. august 2010

2010-08-16T20:22:21Z

Juraj: /* Preudokód */

2010-06-06T15:07:51Z

Preudokód

Juraj na 09:30, 18. máj 2010

2010-05-18T09:30:00Z

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika Kategória:Teória grafov {{Draft}} {{Skripta programovanie}} Prehľadáva…“

2010-05-17T19:59:59Z

Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika Kategória:Teória grafov {{Draft}} {{Skripta programovanie}} Prehľadáva…“

Nová stránka

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:Informatika]]
[[Kategória:Teória grafov]]
{{Draft}}
{{Skripta programovanie}}
Prehľadávanie do hĺbky<ref>http://cs.wikipedia.org/wiki/Prohled%C3%A1v%C3%A1n%C3%AD_do_hloubky</ref> (anglicky Depth-first search - DFS) je grafový algoritmus, ktorý postupne prechádza všetky metódou backtrackingu.
Pracuje tak, že vždy expanduje prvého nasledovníka každého vrcholu, ak ho ešte nenavštívil. Ak narazí na vrchol, z ktorého sa nedá ďalej pokračovať (nemá žiadnych nasledovníkov alebo všetci boli navštívení), vracia sa späť backtrackingom.

==Vlastnosti algoritmu==
Algoritmus sa snaží o maximálne preskúmanie zvolenej cesty pred prípadnou voľbou ďalšej cesty.
Algoritmus je úplný (vždy nájde riešenie, tzn. nájde všetky vrcholy, ktoré sú z východzieho vrcholu dostupné po orientovaných cestách), ale nie je optimálny (pokiaľ graf nieje strom, nemusí nájsť najkratšiu možnou cestu k cieľu).

===Využitie algoritmu DFS===
Algoritmus prehľadávania do hĺbky sa môže ďalej využívať napríklad pre
*topologické usporiadanie uzlov grafu,
*hľadanie silných komponentov grafu *
*zisťovania acyklickosti grafu,
*riešenie hádaniek s jedným riešením (bludiská) a iné.

==Princíp algoritmu DFS==
* v grafe začíname od určitého, dopredu stanoveného vrcholu,
* z vrcholu prejdeme k jednému susednému vrcholu, ktorý je s počiatočným vrcholom spojený hranou,
* ak existuje hrana, pokračujeme od susedného vrcholu k ďalšiemu nespracovanému vrcholu atď.,
* ak prídeme do vrcholu, z ktorého sa nedá ísť ďalej, vrátime sa k predchádzajúcemu vrcholu a od neho skúsime pokračovať v prehľadávaní grafu,
* aby sme rozlíšili tie vrcholy, ktoré sme už spracovali od tých, ktoré sme ešte nenavštívili a nespracovali, máme v každom vrchole stavovú položku ''znacky'':
** na začiatku zabezpečíme, aby mali všetky vrcholy nastavenú položku ''znacky'' na hodnotu 0,
** postupne, ako budeme vrcholy navštevovať, budeme týmto vrcholom nastavovať ''znacky'' na hodnotu 1,

prechádzanie do hĺbky vyzerá tak, akoby sme sa v grafe rozbehli po hranách ďaleko od počiatočného vrcholu a vrcholy krížom-krážom ponavštevovali vrcholy grafu.

==Implementácia algoritmu DSF==
===Preudokód===
Počiatočný vrchol: ''v''.
TRASA – zásobník ([[FIFO]]).
#''TRASA''={0}, označkujeme ''v''
#Vyber ľubovoľnú hranu ''e'' začínajúcu vo vrchole ''v''. Ak taká existuje tak =>3, ak neexistuje =>5
#Označ ''w'' ako koncový vrchol vybranej hrany. Ak je ''w'' označkovaný, tak =>2, inak =>4
#Hranu ''e'' pridáme do zoznamu ''TRASA''. Dosadíme ''v''=''w''. Označkujeme ''v''. choď => 2
#Ak je ''TRASA'' neprázdny odober z konca hranu ''e'' a jej počiatočný vrchol označ ''v''. Choď => 2
#Ak je ''TRASA'' prázdny, tak koniec.

'''Ukážka k predchádzajúcemu pseudokódu:'''
Na nasledujúcich obrázkoch bude ukážka algoritmu DFS.
Graf je daný nasledovne: G=(V,E), V={r,s,t,u,v,w,x,y}, E={a,b,c,d,e,f,g,h,i}.

Vrchol s modrou výplňou reprezentuje navštívený vrchol a vrchol s oranžovým okrejom reprezentuje aktuálny vrchol (vrchol 'v' z preudokódu)

[[Súbor:dfs1.svg|center]]

[[Súbor:dfs2.svg|center]]

[[Súbor:dfs3.svg|center]]

[[Súbor:dfs4.svg|center]]

[[Súbor:dfs5.svg|center]]

[[Súbor:dfs6.svg|center]]

[[Súbor:dfs7.svg|center]]

[[Súbor:dfs8.svg|center]]

[[Súbor:dfs9.svg|center]]

[[Súbor:dfs10.svg|center]]

[[Súbor:dfs11.svg|center]]

[[Súbor:dfs12.svg|center]]

[[Súbor:dfs13.svg|center]]

[[Súbor:dfs14.svg|center]]

[[Súbor:dfs15.svg|center]]
==Zdroje a odkazy==
<references/>

@@ Riadok 77: / Riadok 77: @@
 |13. Nie je možné označiť žiadnu ďalšiu hranu. Preto odoberieme zo zoznamu FRONTA hranu ''h''.
 |-
-|[[Súbor:dfs3.svg|center]]
+|[[Súbor:dfs5.svg|center]]
 |[[Súbor:dfs13.svg|center]]
 |-
@@ Riadok 98: / Riadok 98: @@
+|
 |}
 ===Kód v jazyku C===
 Pri implementácii algoritmu DFS v jazyku C namiesto dátovej štruktúry FIFO využijeme mechanizmus rekurzie. Pri rekurzívnom volaní funkcie sa stav (kontext) vo funkcii uložia do zásobníka. Túto skutočnosť využijeme ako náhradu dátovej štruktúry FIFO.

@@ Riadok 28: / Riadok 28: @@
 ==Implementácia algoritmu DSF==
-===Preudokód===
+===Pseudokód===
 Počiatočný vrchol: ''v''.
 TRASA – zásobník ([[FIFO]]).

@@ Riadok 1: / Riadok 1: @@
-[[Kategória:Študijné materiály]]
+[[Kategória:Grafové algoritmy]]
 {{Draft}}
 {{Skripta programovanie}}

@@ Riadok 46: / Riadok 46: @@
 Graf je daný nasledovne: G=(V,E), V={r,s,t,u,v,w,x,y}, E={a,b,c,d,e,f,g,h,i}.
-Vrchol s modrou výplňou reprezentuje navštívený vrchol a vrchol s oranžovým okrejom reprezentuje aktuálny vrchol (vrchol 'v' z preudokódu)
+Vrchol s modrou výplňou reprezentuje navštívený vrchol a vrchol s oranžovým okrejom reprezentuje aktuálny vrchol (vrchol 'v' z preudokódu).
-[[Súbor:dfs1.svg|center]]
+{| class=wikitable
-[[Súbor:dfs2.svg|center]]
+Opis funkčného prototypu:
-[[Súbor:dfs3.svg|center]]
+'''int **graf''': maticová reprezentácia grafu.
-[[Súbor:dfs4.svg|center]]
+'''int n''': počet vrcholov grafu ''graf''.
-[[Súbor:dfs5.svg|center]]
+'''int znacky[]''': pole, v ktorom uchovávame navštívené vrcholy.
-[[Súbor:dfs6.svg|center]]
+'''int i''': počiatočný vrchol
-[[Súbor:dfs8.svg|center]]
+<source lang="c" line>
-[[Súbor:dfs9.svg|center]]
+'''Komentáre ku zdrojovému kódu''':
 ==Zdroje a odkazy==
 <references/>