Prehľadávanie do hĺbky
Prehľadávanie do hĺbky[1] (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.
Obsah
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)
