Paieška į gylį

Paieška į gylį ( 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..

 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 , kur |V| – viršūnių skaičius, |E| briaunų skaičius (tarkime  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  operacijų, todėl bendras neaplankytų gretimų viršūnių tikrinimo laikas . Tuomet bendras vykdymo laikas ), t. y. gauname tiesinį vykdymo laiką.

 Šaltiniai 

Kategorija:Algoritmai
Kategorija:Grafų teorija