Paieška į gylį

Paieška į gylį (angl. depth-first search ar DFS) – paieškos grafe arba grafo apėjimo būdas, kai pasirinkus pradinę viršūnę einama grafo briaunomis kiek įmanoma giliau, renkantis vis naują viršūnę; kai paskutinė aplankyta viršūnė naujos (dar neaplankytos) kaimynės nebeturi, tada grįžtama iki artimiausios neaplankytos briaunos ir vėl ieškoma kuo giliau tol, kol bus rastas ieškomas tikslas arba kol bus aplankytos visos grafo viršūnės ir briaunos. Šis būdas priešpastatomas paieškai į plotį, kur esant viršūnėje X pirmiausia aplankomos visos viršūnei X gretimos (sujungtos su X briauna) viršūnės, po to viršūnės, gretimos pastarosioms, ir t. t. Algoritmas žinomas jau nuo 19 amžiaus, kuomet jis buvo naudojamas rasti keliui iš labirinto.

Paieška į gylį

Algoritmas

 Kiekvienai neaplankytai viršūnei I, esančiai grafe G: Lankyk(I) 

 Lankyk(I): Pažymime kad viršūnė I aplankyta Kiekvienai neaplankytai viršūnei J, į kurią yra briauna iš einamosios viršūnės I: Lankyk(J) 

Algoritmo pritaikymas:

• norint nustatyti ar grafas jungus, jis bus jungus tuomet jei Lankyk(viršūnė) išoriniame cikle bus iškviestas tik vieną kartą, galima Lankyk iškviesti su bet kuria viršūne ir vėliau patikrinti, ar aplankytos visos viršūnės.
• norint nustayti trumpiausią kelią nesvoriniame grafe nuo duotosios viršūnės t iki visų grafo viršūnių. Tuomet Lankyk(I) procedūrą reikėtų šiek tiek praplėsti:
  

Lankyk(I): Pažymime, kad viršūnė I aplankyta Kiekvienai neaplankytai viršūnei J, į kurią yra briauna iš einamosios viršūnės, I: Pažymime nuotolis(J) = nuotolis(I) + 1 Lankyk(J)

Šią procedūrą reikėtų iškviesti, jai kaip argumentą pateikiant duotąją viršūnę, ir prieš tai pažymėjus: nuotolis(t) = 0, ty. nuotolis nuo pradinės viršūnės iki jos pačios lygus nuliui.

• Stipriai susietų komponentų paieškoje (Strongly connected components)

Algoritmo sudėtingumas: kadangi kiekviena viršūnė aplankoma tik kartą, grafui saugoti naudojant „Adjacency list“ (gretimų viršūnių sarašą) galima pasiekti ${\displaystyle O(|V|+|E|)}$, kur |V| – viršūnių skaičius, |E| briaunų skaičius (tarkime ${\displaystyle t_{j}}$ yra j-ai viršūnei gretimų viršūnių skaičius, tuomet kiekvieną kartą iškvietus Lankyk(i), kuri bus iškviesta ne daugiau kaip |V| kartų, bus atliekama ${\displaystyle t_{i}}$ operacijų, todėl bendras neaplankytų gretimų viršūnių tikrinimo laikas ${\displaystyle \sum _{j=1}^{n}{O(t_{j})}=O(|E|)}$. Tuomet bendras vykdymo laikas ${\displaystyle O(|V|+|E|)}$), t. y. gauname tiesinį vykdymo laiką.

Šaltiniai

1. (2011), [books.google.com Graph Algorithms] (2nd ed.), Cambridge University Press, p. 46–48,  .

Vikiteka: Paieška į gylį – vaizdinė ir garsinė medžiaga