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.
- čas O(V + E)
- paměť O(V)
- používá zásobník
Co to znamená?
- 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í.
- Fronta: kdo dřív přijde, ten dřív odejde. BFS vždy bere vrchol, který čeká nejdéle.
- Zásobník: kdo přijde poslední, odejde první. DFS vždy pokračuje z vrcholu, do kterého se dostal naposledy.
- 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.
- na zásobníku
- aktuální
- hotový
- hrana stromu prohledávání
- přeskočená hrana
Začněte ve vrcholu A. Stiskněte Přehrát nebo procházejte prohledávání krok po kroku.
Mezerník: přehrát nebo pozastavit. Šipky vlevo/vpravo: krok. Home a End: přeskočit.
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.