Prehľadávanie do hĺbky

Prehľadávanie do hĺbky (v angličtine depth-first search, DFS) je algoritmus na prehľadávanie grafov. Na vstup mu dáme graf, v ktorom vyznačíme jeden štartovací vrchol $S$ a algoritmus nám nájde všetky vrcholy, do ktorých sa dá z vrcholu $S$ dostať po hranách grafu. V neorientovanom grafe nám teda nájde všetky vrcholy, ktoré sú v rovnakom komponente ako $S$. Od prehľadávania do šírky sa líši poradím, v akom nachádza jednotlivé vrcholy.

Algoritmus

Pri prehľadávaní grafu budeme postupne objavovať a spracúvať jednotlivé vrcholy. Aby sme zbytočne niektoré vrcholy nespracúvali viackrát, každý vrchol si počas jeho spracovania nejako označíme¹. Pre jednoduchosť vyjadrovania budeme v tomto texte neoznačené vrcholy volať zelené a označené vrcholy červené.

Predstavme si robota, ktorého na začiatku položíme do vo vrcholu $S$ a potom dookola vykonáva nasledovné inštrukcie:

1. Ak práve stojí v zelenom vrchole, prefarbí ho na červeno.
2. 1. Ak sa z vrcholu, kde stojí, dá po niektorej hrane dostať do nejakého zeleného vrcholu, prejde do tohto vrcholu.
   2. V opačnom prípade odíde z aktuálneho vrcholu po hrane, po ktorej sa do neho prvý krát dostal (v orientovanom grafe teda pôjde proti smeru šípky). V prípade, že aktuálny vrchol je vrchol $S$, sa robot nemá kam vrátiť. V takom prípade sa vypne.

Prehľadávanie do hĺbky prehľadáva graf presne ako tento robot.

Prečo to funguje?

Ukážeme si, že robotovo prehľadávanie má dobré vlastnosti:

1. Po konečnom počte krokov skončí.
2. Ofarbí na červeno všetky vrcholy, do ktorých sa dá dostať po hranách z vrcholu $S$.
3. Neprefarbí (ani nenavštívi) už nič iné.

1. Po konečnom počte krokov skončí. Vždy, keď robot vojde do nového zeleného vrcholu, hneď potom ho prefarbí na červeno. Keďže každý vrchol sa dá prefarbiť iba raz, v grafe s $n$ vrcholmi môže robot urobiť nanajvýš $n$ krokov typu a) (v skutočnosti $n-1$, lebo v jednom zelenom vrchole začína).

Okrem toho robí robot ešte kroky typu b), keď sa z červeného vcholu vracia po hrane, po ktorej sa doň prvý raz dostal. Dá sa ukázať, že aj týchto krokov bude konečne veľa. Predstavme si, že robot by vždy, keď prefarbuje vrchol na červeno, napísal do tohto vrcholu ešte jedno číslo (budeme ho volať hĺbka vrcholu), nasledovným spôsobom:

• Do štartovacieho vrcholu napíše číslo $0$.
• Vždy, keď vojde do nového zeleného vrcholu, napíše doň o $1$ väčšie číslo než je vo vrchole, odkiaľ prišiel.

Počas robotovej prechádzky grafom môžeme sledovať, v akej je robot hĺbke -- teda akú hĺbku má vrchol, v ktorom sa robot práve nachádza. Vždy, keď robot urobí krok do zeleného vrcholu (a prefarbí ho), hĺbka robota stúpne o $1$. Vždy, keď sa robot vracia z červeného vrcholu hranou, ktorou prišiel, jeho hĺbka klesne o $1$. Hĺbka pritom v každom momente bude nezáporná (lebo záporné čísla nám nemajú ako vzniknúť). Keďže robot začína v hĺbke $0$ a urobí nanajvýš $n$ krokov, v ktorých jeho hĺbka stúpne (krokov, kde vojde do zeleného vrcholu), nemôže urobiť viac než $n$ krokov, pri ktorých jeho hĺbka klesne (inak by skončil v zápornej hĺbke). To znamená, že robot zaručene skončí po nanajvýš $2n$ krokoch.

2. Ofarbí na červeno všetky vrcholy, do ktorých sa dá dostať z vrcholu $\boldsymbol{S}$. Najprv si všimnime, že robotova prechádzka má jednu zaujímavú vlastnosť: z každého vrcholu, do ktorého robot vojde ako do zeleného, sa niekedy neskôr vráti po hrane, ktorou doň prvý raz prišiel.

Prečo je to tak? Predstavme si situáciu, keď robot prešiel z nejakého červeného vrcholu $C$ do zeleného vrcholu $Z$ (ale ešte ho neprefarbil). Vrcholy, ktoré sú v tomto momente červené, budeme volať staré a vrcholy, ktoré sú v tomto momente zelené, budeme volať nové. Robot je teda momentálne vo vrchole $Z$, ktorý je nový. Na konci algoritmu však bude vo vrchole $S$ (lebo len tam sa môže vypnúť), ktorý je zaručene starý. To znamená, že niekedy medzi súčasným okamihom a koncom algoritmu bude musieť prejsť z nejakého nového vrcholu do nejakého starého vrcholu. Keď sa toto stane prvý raz, určite to bude krokom typu b), keďže kroky typu a) musia ísť do zelených vrcholov a všetky staré vrcholy sú už teraz červené. V tomto kroku sa teda robot bude z nejakého nového vrcholu vracať po hrane, ktorou ho objavil, naspäť do nejakého starého vrcholu. Od momentu, keď vošiel do vrcholu $Z$, však ešte v žiadnom starom vrchole nebol. To znamená, že všetky nové vrcholy (okrem $Z$), ktoré medzičasom prefarbil, musel objaviť len z iných nových vrcholov. Jediný možný spôsob, ako sa mohol vrátiť na starý vrchol je teda ten, že sa vrátil zo $Z$ na $C$.

Nakoniec si ešte stačí uvedomiť, že ako vrchol $Z$ mohol v predchádzajúcej úvahe vystupovať ľubovoľný vrchol (okrem $S$), ktorý robot počas svojej prechádzky objavil a prefarbil. To znamená, že z každého vrcholu, ktorý robot objaví, sa niekedy neskôr vráti po hrane, ktorou doň prvý raz vošiel.

Poďme teraz ukázať pôvodné tvrdenie (že robot objaví všetky vrcholy dosiahnuteľné z $S$). Predstavme si, že by to tak nebolo, teda že by sa v grafe dal nájsť bol vrchol $D$, ktorý je dosiahnuteľný z $S$, ale robot ho neobjavil. Vrchol $D$ má byť dosiahnuteľný, teda v grafe má existovať cesta z $S$ do $D$. Posledný vrchol na tejto ceste, ktorý robot ešte objavil (a prefarbil na červeno) označme $O$ a prvý vrchol, ktorý už neobjavil, označme $N$. Z vrcholu $O$ sa teda po hrane dá dostať do $N$.

Vieme, že v nejakom momente robot vošiel do vrcholu $O$ krokom typu a) (resp. ak $O$ je totožný s $S$, tak v ňom začal na začiatku). Ukázali sme už, že potom z neho musel niekedy neskôr odísť krokom typu b) (v prípade, že $O = S$, sa v ňom musel na konci vypnúť). To ale znamená, že tesne pred týmto krokom typu b) (alebo vypnutím) bol robot vo vrchole $O$ a nemohol sa z neho po hrane dostať do žiadneho zeleného vrcholu. Čo však nesedí s tým, že z $O$ sa dá ísť po hrane do vrcholu $N$, ktorý zostal až do konca zelený. Celá táto situácia je teda nemožná, čiže robot naozaj objaví všetky vrcholy, do ktorých sa z $S$ dá dostať.

3. Neprefarbí (ani nenavštívi) už nič iné. Robot začína vo vrchole $S$, ktorý zjavne je dosiahnuteľný z $S$. Ak by mal počas prechádzky vojsť do nedosiahnuteľného vrcholu, niekedy by sa to muselo stať prvý raz. Určite sa to nemôže stať krokom typu b), lebo takýmto krokom sa robot vracia na vrchol, kde už niekedy bol a doteraz bol iba na dosiahnuteľných vrcholoch. Nemôže sa to stať ani krokom typu a), lebo z dosiahnuteľného vrcholu sa po hrane grafu dá dostať iba do dosiahnuteľného. To znamená, že robot sa nemá ako dostať do nedosiahnuteľného vrcholu.

Implementácia

Prehľadávanie do hĺbky sa typicky programuje ako rekurzívna funkcia (nazvime ju dfs()). Tejto funkcii dáme na vstup zelený vrchol $Z$ a budeme chcieť, aby nám odsimulovala robota od okamihu, keď vojde do $Z$ krokom typu a) až po okamih, keď sa z neho bude vracať krokom typu b).

S rekurziou sa táto funkcia bude programovať prekvapivo jednoducho:

1. Najprv prefarbíme vrchol $Z$ na červeno.
2. Následne postupne skontrolujeme každú hranu vedúcu zo $Z$. Vždy, keď nájdeme nejakú hranu, ktorá vedie do nejakého dosiaľ zeleného vrcholu $V$, zavoláme na vrchol $V$ našu funkciu dfs(). To nám odsimuluje časť prechádzky robota od okamihu, keď vojde do $V$ až po moment, keď sa z neho opäť vráti do $Z$. Keď sme už prešli všetky hrany, máme zaručené, že každá hrana zo $Z$ vedie do červeného vrchola (buď bol červený keď sme ho kontrolovali, alebo sme doň zavolali funkciu dfs(), počas ktorej sa prefarbil). To znamená, že robot by sa v tomto momente vrátil zo $Z$ krokom typu b), teda sme už splnili svoju robotu a môžeme skončiť.

Celé prehľadávanie odštartujeme tak, že zavoláme dfs() do vrcholu $S$ -- vypnutie robota na konci algoritmu totiž vyzerá úplne rovnako, ako keď sa z iných vrcholov vracia krokom typu b). Predtým si však musíme dávať pozor, aby všetky vrcholy, ktoré majú byť na začiatku zelené, boli naozaj zelené.

int n;                         // pocet vrcholov
vector<vector<int> > sused(n); // zoznam susedov
vector<bool> cerveny(n);       // true, ak je dany vrchol zeleny

void dfs(int Z)
{
    cerveny[Z] = true;
    for(int i=0; i<sused[Z].size(); i++)
    {
        if(!cerveny[sused[Z][i]])
        {
            dfs(sused[Z][i]);
        }
    }
}

Zložitosť

Každé volanie funkcie dfs() samo o sebe prefarbí jeden vrchol. Celkový počet volaní teda bude rovný počtu prefarbených vrcholov (čiže nanajvýš $n$). Každé volanie urobí (okrem rekurzívnych volaní) množstvo práce úmerné počtu hrán vedúcich zo $Z$. Keďže z do každého vrchola sa dfs() volá najviac raz, každú hranu takto kontrolujeme najviac raz (v prípade orientovaných hrán), resp. dvakrát (v prípade neorientovaných hrán). To znamená, že v najhoršom prípade má náš algoritmus časovú zložitosť $O(n+m)$, kde $n$ je počet vrcholov grafu a $m$ je počet hrán. Presnejší odhad dostaneme, ak namiesto počtu všetkých vrcholov vezmeme iba počet navštívených (teda dosiahnuteľných z $S$) a namiesto počtu všetkých hrán vezmeme iba počet dosiahnuteľných hrán.

Na pamätanie grafu potrebujeme aspoň $O(m)$ pamäte. Niekedy si však graf pamätáme aj z iných dôvodov a teda ho nemusíme počítať do pamäťovej zložitosti prehľadávania do hĺbky. V takom prípade má prehľadávanie pamäťovú zložitosť $O(n)$, kvôli zásobníku počas rekurzie.

Využitie

Samotné prehľadávanie do hĺbky, ako je prezentované v tomto článku, sa dá využiť na testovanie dosiahnuteľnosti jedného vrcholu z druhého, ale napríklad aj na spočítanie komponentov neorientovaného grafu:

1. Najprv zafarbíme celý graf na zeleno a vynulujeme si počítadlo.
2. Následne skontrolujeme všetky vrcholy grafu. Vždy, keď nájdeme nejaký zelený vrchol, zavoláme doň dfs() a zvýšime si počítadlo o $1$.
3. Na konci budeme mať v počítadle počet komponentov.

Tento algoritmus sa dá dokonca rozšíriť tak, aby každý komponent zafarbil inou farbou (do funkcie dfs() pridáme parameter, aký odtieň červenej má používať).

To zatiaľ nevyzerá ako nič, čo by nezvládlo aj prehľadávanie do šírky. Prehľadávanie do hĺbky má však veľký význam ako základ rôznych zložitejších algoritmov, ktoré dokážu napríklad:

• Hľadať mosty v grafoch.
• Hľadať artikulácie v grafoch.
• Hľadať silno súvislé komponenty v orientovaných grafoch.
• Testovať planaritu grafov.