Úvod

Prehľadávanie do hĺbky (v angličtine depth-first search, DFS) je algoritmus na prehľadávanie grafov. Na vstup mu dáme graf, v ktorom vyznačíme jeden štartovací vrchol $S$ a algoritmus nám nájde všetky vrcholy, do ktorých sa dá z vrcholu $S$ dostať po hranách grafu. V neorientovanom grafe nám teda nájde všetky vrcholy, ktoré sú v rovnakom komponente ako $S$. Od prehľadávania do šírky sa líši poradím, v akom nachádza jednotlivé vrcholy.

Algoritmus

Pri prehľadávaní grafu budeme postupne objavovať a spracúvať jednotlivé vrcholy. Aby sme zbytočne niektoré vrcholy nespracúvali viackrát, každý vrchol si počas jeho spracovania nejako označíme¹. Pre jednoduchosť vyjadrovania budeme v tomto texte neoznačené vrcholy volať zelené a označené vrcholy červené.

Predstavme si robota, ktorého na začiatku položíme do vo vrcholu $S$ a potom dookola vykonáva nasledovné inštrukcie:

1. Ak práve stojí v zelenom vrchole, prefarbí ho na červeno.
2. Inak:
   1. Ak sa z vrcholu, kde stojí, dá po niektorej hrane dostať do nejakého zeleného vrcholu, prejde do tohto vrcholu.
   2. V opačnom prípade odíde z aktuálneho vrcholu po hrane, po ktorej sa do neho prvý krát dostal(v orientovanom grafe teda pôjde proti smeru šípky). V prípade, že aktuálny vrchol je vrchol $S$, sa robot nemá kam vrátiť. V takom prípade sa vypne.