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]);
        }
    }
}