Prehľadávanie do hĺbky (DFS)
Prechádza graf tak, že ide po jednej ceste čo najhlbšie a potom sa vráti k poslednému rázcestiu. Zásobník na obrazovke je práve táto cesta.
- O(V + E)
- pamäť O(V)
- zásobník
V a E: počet vrcholov a hrán. O(V + E) znamená, že každý vrchol a každá hrana sa spracuje iba pevne daný počet ráz.
Zásobník: kto príde posledný, odíde prvý. DFS vždy pokračuje z vrcholu, ku ktorému sa dostal naposledy.
Ďalšie pojmy na tejto stránke
- Vrchol: bod grafu, tu nakreslený ako krúžok s písmenom.
- Hrana: čiara, ktorá spája dva vrcholy. Tu sa po nej dá ísť oboma smermi.
- Susedia: vrcholy spojené s daným vrcholom hranou. Prezerajú sa v abecednom poradí.
Skúste: Zvoľte graf s cyklami. Každá prerušovaná hrana vedie späť do vrcholu, ktorý už je na zásobníku alebo je hotový. Taká hrana uzatvára cyklus.
Ako to funguje
DFS zavolá sám seba na prvého suseda, ktorého ešte nevidel, potom na prvého nového suseda tohto vrcholu a tak ďalej. Keď vrchol už nemá nových susedov, jeho volanie skončí a DFS sa vráti o krok späť, kde skúsi ďalšieho suseda. Otvorené volania tvoria zásobník, ktorý je vždy cestou od štartu k aktuálnemu vrcholu. Číslo pri vrchole je poradie, v akom bol navštívený.
Kedy sa hodí
DFS použite, keď chcete zistiť, kam sa vôbec dá dostať, nájsť cykly, prejsť bludiskom alebo zoradiť úlohy, ktoré od seba závisia. Najkratšiu cestu nenájde.