Průchod do hloubky bude beze změny fungovat i pro orientované grafy. Na následujícím obrázku je nalevo orientovaný graf a napravo jeho strom průchodu do hloubky. Opět, pokud jsme během DFS měli na výběr z několika vrcholů, tak jsme si vybrali abecedně nejmenší vrchol.

V případě neorientovaných grafů jsme rozlišovali mezi stromovými a zpětnými hranami. U orientovaných grafů budeme muset rozlišit více případů nestromových hran. Typ hrany určíme ve chvíli, kdy hranu procházíme pomocí DFS a to podle barvy vrcholu, do kterého hrana vede, případně podle časů příchodu a odchodu z koncových vrcholů hrany.

  • stromové hrany – vedou z právě prozkoumávaného vrcholu do nenavštíveného (bílého) vrcholu; tvoří DFS strom.
  • zpětné hrany – vedou z právě prozkoumávaného vrcholu do šedivého vrcholu, tj. do předchůdce v DFS stromě.
  • dopředné hrany – vedou z právě prozkoumávaného vrcholu do černého vrcholu v témže podstromě, tj. do svého potomka.
  • příčné hrany– vedou z právě prozkoumávaného vrcholu do černého vrcholu v jiném podstromě, tj. mezi dvěmi různými podstromy téhož grafu.

Hloubavý čtenář vidí, že barvy vrcholů ve skutečnosti nepotřebujeme a že jsme schopni barvu vrcholu určit pomocí hodnot $in[v]$, $out[v]$. Lepší charakterizaci hran při DFS dává následující pozorování.

Pozorování: Intervaly $(in[v], out[v])$ pro všechny $v\in V$ tvoří dobré uzávorkování. To znamená, že dva intervaly jsou buď disjunktní a nebo je jeden podmnožinou druhého. Pro každou hranu $uv\in E$ platí jedna z následujících možností:

  • $uv$ je stromová nebo dopředná hrana $\Longleftrightarrow$ $(in[v], out[v]) \subseteq (in[u], out[u])$
  • $uv$ je zpětná hrana $\Longleftrightarrow$ $(in[u], out[u]) \subseteq (in[v], out[v])$
  • $uv$ je příčná hrana $\Longleftrightarrow$ $in[v] < out[v] < in[u] < out[u]$ (intervaly jsou disjunktní)

Interval $(in[v], out[v])$ znázorňuje dobu, po kterou byl vrchol $v$ uložen na zásobníku. Vlastnost korektního uzávorkování plyne přímo z toho, jak pracujeme se zásobníkem. Vrchol neopustíme a neodebereme ze zásobníku dříve, než jsou zpracováni všichni jeho potomci.

Průběh zaplnění zásobníku pro graf ze začátku stránky je na následujícím obrázku. Stavu zásobníku odpovídá jen jeden sloupeček. Obrázek zachycuje stav zásobníku v různých časech. Vrchol $X$ je vložen na zásobník v čase $\ARRAY{in}{X}$ a je ze zásobníku odebrán v čase $\ARRAY{out}{X}$.

Zkuste si rozmyslet, v jakém vztahu jsou intervaly $(in[u], out[u])$ a $(in[v], out[v])$, pokud je $u$ následníkem $v$.