Paieška į gylį

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Paieška į gylį (angl. Depth-first search ar DFS) – grafo apėjimo (paeiškos) būdas, kurio pagrindinis principas – pasirenkama pradinė viršūnė ir einama grafu kiek įmanoma giliau, tada grįžtama iki artimiausios neaplankytos briaunos ir vėl ieškoma kuo giliau. Šis būdas priešpastatomas paieškai į plotį, kur esant viršūnėje X pirma aplankomos visos artimos X viršūnės (sujungtos su X briauna), tik tada pereinama prie kitos viršūnės.

[taisyti] 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 tiesioginis kelias 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 betkuria viršūne ir vėliau patikrinti ar aplankytos visos viršūnės.
• norint nustayti trumpiasią kelią nesvoriniame grafe nuo duotosios viršūnės t iki visų grafo viršūnių. Tuomet Lankyk(i) procedūrą reikėtu šiektiek praplėsti:
  

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

Šią procedūrą reiketu iškviesti jai kaip argumentą paduodant 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ų komponetų paieškoje (Strongly connected components)

Algoritmo sudėtingumas: kadangi kiekviena viršūnė aplankoma tik kartą, grafui saugoti naudojant „Adjactency list“ (gretimų viršūnių sarašą) galima pasiekti O( | V | + | E | ), kur |V| – viršūnių skaičius, |E| briaunų skaičius (tarkime t_j j-ai viršūnei gretimų viršūnių skaičius, tuomet kiekvieną kart iškietus Lankyk(i), kuri bus iškviesta nedaugiau kaip |V| kartų, bus atliekama t_i operacijų, todėl bendras neaplankytų gretimų viršūnių tikrinimo laikas . Tuomet bendras vykdymo laikas O( | V | + | E | ) ), t. y. gauname tiesinį vykdymo laiką.