Prohledávání do hloubky (DFS)
Prochází graf tak, že jde po jedné cestě co nejhlouběji a pak se vrátí k poslednímu rozcestí. Zásobník na obrazovce je právě ta cesta.
- O(V + E)
- paměť O(V)
- zásobník
V a E: počet vrcholů a hran. O(V + E) znamená, že každý vrchol a každá hrana se zpracuje jen pevně daný počet krát.
Zásobník: kdo přijde poslední, odejde první. DFS vždy pokračuje z vrcholu, do kterého se dostal naposledy.
Další pojmy na této stránce
- Vrchol: bod grafu, tady nakreslený jako kroužek s písmenem.
- Hrana: čára, která spojuje dva vrcholy. Tady se po ní dá jít oběma směry.
- Sousedé: vrcholy spojené s daným vrcholem hranou. Prohlížejí se v abecedním pořadí.
Zkuste: Zvolte graf s cykly. Každá čárkovaná hrana vede zpět do vrcholu, který už je na zásobníku nebo je hotový. Taková hrana uzavírá cyklus.
Jak to funguje
DFS zavolá sám sebe na prvního souseda, kterého ještě neviděl, pak na prvního nového souseda tohoto vrcholu a tak dále. Když vrchol už nemá nové sousedy, jeho volání skončí a DFS se vrátí o krok zpět, kde zkusí dalšího souseda. Otevřená volání tvoří zásobník, který je vždy cestou od startu k aktuálnímu vrcholu. Číslo u vrcholu je pořadí, v jakém byl navštíven.
Kdy se hodí
DFS použijte, když chcete zjistit, kam se vůbec dá dojít, najít cykly, projít bludiště nebo seřadit úkoly, které na sobě závisejí. Nejkratší cestu nenajde.