Prohledávání grafu do hloubky

Tento algoritmus je též někdy označován zkratkou DFS (Depth First Search).

Vstup: Vstupem algoritmu je libovolný orientovaný nebo neorientovaný souvislý graf.

Inicializace: Na začátku algoritmu uložíme do zásobníku startovací uzel (vrchol grafu, ve kterém zahajujeme prohledávání).

Popis: Z uzlu, který je na vrcholu zásobníku, se vydáme po hraně do některého z jeho neoznačených následníků. Každý takovýto neoznačený uzel, do kterého vede hrana, přidáme na zásobník a opět se vydáme po hraně do některého z jeho neoznačených následníků, který přidáme na vrchol zásobníku. Takto postupujeme, dokud nenarazíme na uzel, který žádné další neoznačené následníky nemá. Tento uzel vyjmeme z vrcholu zásobníku, označíme (nastavíme mu příznak) a ukončíme jeho prohledávání. V prohledávání se vrátíme do uzlu, který je momentálně na vrcholu zásobníku a celý proces opakujeme, dokud zásobník není prázdný.

Výstup: Prohledané uzly grafu je možné zachytit tzv. preorder, tedy v pořadí, v jakém byly ukládány na zásobník, nebo postorder, tedy v pořadí, v jakém bylo ukončeno jejich prohledávání.

Následující obrázek ilustruje, jak algoritmus prohledávání grafu do hloubky prochází grafem: