Prohledavani do hloubky, anglicky Depth First Search (DFS), slouzi k prohledani orientovaneho ci neorientovaneho grafu pocinaje danym vrcholem. Slouzi predevsim jako zaklad k slozitejsim grafovym algoritmum (napriklad topologickemu trideni). Lze pouzit take k nalezeni cesty mezi dvema vrcholy, nikoliv ovsem nejkratsi! Jde vlastne o systematicke prochazeni vsech moznych cest grafem, tedy o algoritmus, ktery bychom pouzili v realnem zivote napriklad pri hledani cesty bludistem (treba vychodu z egyptske pyramidy), pro pocitacove zpracovani (kdy muzeme libovolne skakat z jednoho uzlu grafu do druheho) existuji vsak lepsi algoritmy (napriklad Dijkstruv algoritmus).

Algoritmus DFS:

Vstup: graf G a pocatecni uzel s

zasobnik_inicializuj(Z)
for each vrchol u do
  found[u]:=False
  pred[u]:=NIL
end for
found[s]:=True
zasobnik_uloz(Z,s)
while not zasobnik_prazdny(Z) do
  u:=zasobnik_odeber(Z)
  for each vrchol v sousedni s u do
    if not found[v] then
      found[v]:=True
      pred[v]:=u
      zasobnik_uloz(Z,v)
    end if
  end for
end while

Vystup: pole pred obsahuje pro kazdy uzel u
                  jeho bezprostredniho predchudce na ceste z s do u

Poznamka 1: uvedenou iterativni verzi lze, samozrejme, jednoduse prepsat na rekurzivni bez pouziti zasobniku

Poznamka 2: pokud bychom zamenili zasobnik za frontu, dostali bychom prohledavani do sirky.

Poznamka 3: pokud bychom pracovali s ohodnocenym grafem a chteli urcit nejkratsi cesty z daneho uzlu, muzeme to udelat tak, ze si na zacatku zjistime pocty predchudcu u kazdeho vrcholu a budeme tento pocet zmensovat u kazdeho souseda aktivniho uzlu. Vzdalenost budeme upravovat stejne jako u Dijkstrova algoritmu a do zasobniku zaradime uzel vzdy az tehdy, kdyz pocet predchudcu klesne na nulu.