Cesko.wiki Prohledávání do hloubky
Author
Albert FloresPořadí, v jakém je přistupováno k vrcholům 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.
Obrazový popis průchodu algoritmu grafem
+more5'>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). +more 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ý). +more 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é. +more Č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. +more 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. +more 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). +more 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. +more 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. +more 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. +more # 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. +more 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. +more 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. +more 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. +more 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ř. +more 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
[url=http://js1k. com/2010-first/demo/162]Prohledávání bludiště (bez cyklů)[/url] * Jakub Černý: [url=https://web. +morearchive. org/web/20071018060717/http://kam. mff. cuni. cz/~kuba/ka/]Základní grafové algoritmy[/url] (texty v pdf).