Prehľadávanie do hĺbky (DFS)
Prechádza graf tak, že ide po jednej ceste čo najhlbšie a potom sa vráti k poslednému rázcestiu. Zásobník na obrazovke je práve táto cesta.
- čas O(V + E)
- pamäť O(V)
- používa zásobník
Čo to znamená?
- Vrchol: bod grafu, tu nakreslený ako krúžok s písmenom.
- Hrana: čiara, ktorá spája dva vrcholy. Tu sa po nej dá ísť oboma smermi.
- Susedia: vrcholy spojené s daným vrcholom hranou. Prezerajú sa v abecednom poradí.
- Front: kto prv príde, ten prv odíde. BFS vždy berie vrchol, ktorý čaká najdlhšie.
- Zásobník: kto príde posledný, odíde prvý. DFS vždy pokračuje z vrcholu, ku ktorému sa dostal naposledy.
- V a E: počet vrcholov a hrán. O(V + E) znamená, že každý vrchol a každá hrana sa spracuje iba pevne daný počet ráz.
- na zásobníku
- aktuálny
- hotový
- hrana stromu prehľadávania
- preskočená hrana
Začnite vo vrchole A. Stlačte Prehrať alebo prechádzajte prehľadávanie krok po kroku.
Medzerník: prehrať alebo pozastaviť. Šípky vľavo/vpravo: krok. Home a End: preskočiť.
Skúste: Zvoľte graf s cyklami. Každá prerušovaná hrana vedie späť do vrcholu, ktorý už je na zásobníku alebo je hotový. Taká hrana uzatvára cyklus.
Ako to funguje
DFS zavolá sám seba na prvého suseda, ktorého ešte nevidel, potom na prvého nového suseda tohto vrcholu a tak ďalej. Keď vrchol už nemá nových susedov, jeho volanie skončí a DFS sa vráti o krok späť, kde skúsi ďalšieho suseda. Otvorené volania tvoria zásobník, ktorý je vždy cestou od štartu k aktuálnemu vrcholu. Číslo pri vrchole je poradie, v akom bol navštívený.
Kedy sa hodí
DFS použite, keď chcete zistiť, kam sa vôbec dá dostať, nájsť cykly, prejsť bludiskom alebo zoradiť úlohy, ktoré od seba závisia. Najkratšiu cestu nenájde.