Prohledávání do hloubky

Prohledávání do hloubky (v angličtině označované jako depth-first search nebo zkratkou DFS) je grafový algoritmus pro procházení grafů metodou backtrackingu. Pracuje tak, že vždy expanduje prvního následníka každého vrcholu, pokud jej ještě nenavštívil. Pokud narazí na vrchol, z nějž už nelze dále pokračovat (nemá žádné následníky nebo byli všichni navštíveni), vrací se zpět backtrackingem.

Pořadí, v jakém je přistupováno k vrcholům

Obrazový popis průchodu algoritmu grafem

Ukázka prohledávání grafu do hloubky

Na obrázku vpravo je ukázáno, jak pracuje algoritmus prohledávání do hloubky. Po přiblížení jde z obrázku poznat postup algoritmu, postupné obarvování, neboli měnění vlastností stavu uzlu ze stavu FRESH (zelená) přes stav OPEN (červená) až po CLOSED (modrá), určování časových značek otevření a uzavření a nakonec i vyznačení typů hran.

Vlastnosti algoritmu

Na konečných grafech je algoritmus úplný (vždy najde řešení, tzn. najde všechny vrcholy, které jsou z výchozího vrcholu dostupné po orientovaných cestách), ale není optimální (pokud graf není strom, nemusí najít nejkratší možnou cestu k cíli). Naproti tomu na nekonečném grafu může pokračovat v prohledávání nekonečné větve a jinou, třeba i konečnou větev, nikdy nenavštíví.

Během prohledávání se mění stavy vrcholů. Na začátku jsou všechny vrcholy ve stavu FRESH (nový, čerstvý). Jakmile algoritmus vrchol nalezne, změní stav vrcholu na OPEN (otevřený) a když později z tohoto vrcholu provede návrat, změní se stav na CLOSED (zavřený). Výchozí vrchol tedy zůstává otevřeným nejdéle, jeho uzavřením prohledávání končí.

Během prohledávání lze vrcholům grafu přidělovat časové značky, kdy se vrchol stal otevřeným a kdy byl uzavřen. Podobně lze hrany grafu během prohledávání rozdělit do čtyř skupin na hrany stromové, příčné, zpětné a dopředné. Časové značky i členění hran mají pomocný charakter, samotné prohledávání grafu do hloubky tím není nijak ovlivněno, může to však být užitečné pro další analýzu grafu.

Algoritmus v každém okamžiku "je v nějakém vrcholu", nazvěme jej aktuálním vrcholem (v níže uvedeném kódu je označen u). Algoritmus vezme nějakou hranu vycházející z aktuálního vrcholu. Pokud tato hrana vede do nového vrcholu (FRESH), nazýváme tuto hranu stromovou a v tom případě algoritmus "postoupí do hloubky", novým aktuálním vrcholem se stane koncový vrchol této hrany a ke starému aktuálnímu vrcholu se algoritmus vrátí až poté, co skončí prohledávání z nového aktuálního vrcholu. Pokud hrana vede do vrcholu v jiném stavu než FRESH, algoritmus tuto hranu přeskočí a vezme další hranu. Jsou-li všechny hrany z aktuálního vrcholu prozkoumány, aktuální vrchol je prohlášen za uzavřený (CLOSED) a algoritmus provede návrat (po stromové hraně) do vrcholu, odkud přišel.

Stromové hrany tvoří kořenový strom (odtud název), který spojuje všechny vrcholy, které jsou orientovaně dostupné z výchozího vrcholu -- ten je kořenem stromu. Veškeré pohyby po grafu, tedy postupy do hloubky i pozdější návraty se dějí podél stromových hran. Do každého vrcholu, který je z výchozího vrcholu orientovaně dostupný, vede z výchozího vrcholu přesně jedna cesta tvořená stromovými hranami.

Hrana, jejíž koncový vrchol je (v okamžiku zpracování hrany) ve stavu OPEN, se nazývá zpětnou hranou. Zpětnou hranou prochází cyklus, který kromě zpětné hrany obsahuje žádnou, jednu nebo několik hran stromových.

Hrana, jejíž koncový vrchol je (v okamžiku zpracování hrany) ve stavu CLOSED, je hranou dopřednou nebo hranou příčnou v závislosti na časových značkách přidělených v okamžicích otevření vrcholů. Pokud hrana vede směrem k nižší značce, jde o hranu příčnou (vede do vedlejší, již dříve opuštěné větve stromu). Pokud hrana vede směrem k vyšší značce, jde o hranu dopřednou, která vede "dál v téže větvi stromu".

Obecná implementace v pseudokódu

   void DFS (Graph G) {    
1    for (Node u in U(G))
2      { stav[u] = FRESH;  p[u] = null; }
3    i = 0;
4    for (Node u in U(G))
5      if (stav[u] == FRESH) DFS-Projdi(u); 
6  }

   void DFS-Projdi(Node u) {
1    stav[u] = OPEN; d[u] = ++i;
2    for (Node v in Adj[u])  
3      if (stav[v] == FRESH)  {
4        p[v] = u;  DFS-Projdi(v); }
5    stav[u] = CLOSED; f[u] = ++i;
6  }

Popis algoritmu

Celý algoritmus začíná inicializací všech uzlů grafů hodnotami stavů uzlů a nastavením jejich předchůdců. Každý uzel je nastaven jako FRESH uzel a žádný zatím nemá určeného svého předchůdce. To znamená, že v poli předchůdců jsou všechny hodnoty prvků nastaveny na null. Index (dále již časový index), který budeme dále využívat pro zapisování časových značek, nastavíme na nulu. Poté je pro všechny uzly, které jsou dosud ve stavu FRESH, vyvolána metoda DFS-Projdi.

Metoda DFS-Projdi realizuje vlastní prohledávání do hloubky. V této metodě je na počátku stav uzlu u, pro který byla tato metoda volána, nastaven na OPEN a do časové značky otevření uzlu se zapíše hodnota časového indexu, který se ve stejné době i inkrementuje, abychom mohli o jedna větší index použít pro další uzel. Poté se pro každého následníka (značíme jej v) uzlu u zjistí, zda tento následník v je ještě ve stavu FRESH, a pokud ano, zapíše se pro něj do pole p hodnota předchůdce a zavolá se pro něj rekurzivně metoda DFS-Projdi. Jestliže byli zpracováni všichni následníci uzlu u, tento uzel se prohlásí za uzavřený (přiřadí se mu stav CLOSED) a nastaví se pro něj časová značka uzavření použitím námi využívaného časového indexu, který se následně o jedna zvětší.

Použité datové struktury

Pole stav — v tomto poli jsou uloženy stavy jednotlivých uzlů.
Pole d časových značek otevření — v tomto poli jsou uloženy časové značky otevření, kdy se z uzlů stavu FRESH stanou uzly stavu OPEN.
Pole f časových značek uzavření — v tomto poli jsou uloženy časové značky uzavření, kdy se z uzlu stavu OPEN stanou uzly stavu CLOSED.
Pole p předchůdců — v tomto poli jsou uloženi předchůdci jednotlivých uzlů ve stromě cest.

Rozdíl v algoritmu při aplikaci na neorientovaný graf

Algoritmus má i pro neorientovaný graf stejný průběh. Oproti aplikaci na orientovaný graf se tu algoritmus vcelku liší jen v tom, že se zde nacházejí pouze dva ze čtyř různých typů hran. V tomto případě se v grafu budou vyskytovat pouze hrany stromové a zpětné. Zbývající dva typy hran, dopředné a příčné, se při průchodu neorientovaného grafu nevyskytnou.

Další využití algoritmu

Algoritmus prohledávání do hloubky se může dále využívat například pro topologické uspořádání uzlů grafu, nalezení silných komponent grafu či zjištění acykličnosti grafu.

Topologické uspořádání uzlů grafu

Použijeme novou datovou strukturu, zásobník. Dále necháme volně procházet algoritmus prohledání do hloubky po grafu a jedinou změnou, kterou v algoritmu vůči "normálnímu" průběhu uděláme, bude, že pokaždé, když algoritmus nějakému uzlu přiřadí časovou značku uzavření, tento uzel vložíme do zásobníku. Na konci běhu algoritmu máme v zásobníku topologicky uspořádané uzly.

Nalezení silných komponent

Pomocí algoritmu prohledávání do hloubky určíme u všech uzlů časové značky uzavření. V dalším kroku změníme orientací každé hrany v původním grafu a znovu spustíme algoritmus prohledávání do hloubky. Uzly budeme vybírat v klesajícím pořadí značek uzavření, jež jsme zjistili prvním průchodem algoritmu ještě na "originálně orientovaném" grafu. Po ukončení tohoto algoritmu už získáme stromy lesa, které nám budou určovat silné komponenty grafu.

Zjištění acykličnosti grafu

Pro zjištění acykličnosti grafu přidáme do algoritmu podmínku, zda byla nalezena zpětná hrana, tj. hrana, která vede do vrcholu ve stavu OPEN. Zpětná hrana spolu s jednou nebo několika hranami stromovými tvoří cyklus. Pokud se při prohledávání do hloubky žádná zpětná hrana nevyskytne, je graf acyklický.

Určení následníka trůnu

Většina monarchií užívá prohledávání do hloubky jako základ pro nalezení nadcházejícího panovníka. Viz např. Linie následnictví britského trůnu a Linie následnictví španělského trůnu.

Složitost algoritmu

Celková složitost algoritmu : Θ(|V| + |E|), kde |V| je počet vrcholů a |E| počet hran daného grafu.

Související články

Externí odkazy

Obrázky, zvuky či videa k tématu Prohledávání do hloubky na Wikimedia Commons
Prohledávání bludiště (bez cyklů)
Jakub Černý: Základní grafové algoritmy (texty v pdf)