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 byly všichni navštíveni), vrací se zpět backtrackingem.
Obsah |
[editovat] Obrazový popis průchodu algoritmu grafem
Na tomto obrázku 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 FREE přes stav OPEN až po CLOSE. Určování časových značek otevření a uzavření a nakonec i vyznačení typů hran.
[editovat] Vlastnosti algoritmu
Algoritmus je úplný (vždy najde řešení, tzn. určitý cílový vrchol, pokud existuje), ale není optimální (pokud graf není strom, nemusí najít nejkratší možnou cestu k cíli). Algoritmus dokáže prohledat pouze souvislé komponenty grafu, není tedy vždy zajištěno ani to, že algoritmus projde všechny uzly. Předpokládáme, že graf má uzly ohodnocené číselnými hodnotami, které budeme dále používat zejména pro výběr jakým směrem, přes jaký uzel z následníků daného uzlu se má algoritmus vydat. V tomto algoritmu totiž panuje pravidlo výběru postupně právě těch následníků daného uzlu v pořadí hodnot, kterými jsou uzly hodnoceny. Od nižšího ohodnocení k vyšším. V grafu se vyskytují celkem čtyři typy hran. Jsou to hrany stromové, příčné, zpětné a dopředné. Algoritmus prochází hranami a postupuje tím stylem že se snaží projít nejprve co nejhlouběji do nitra (z tohoto principu se také tomuto algoritmu říká prohledávání do hloubky), či co nejdál to jen jde. Tyto hrany, po kterých algoritmus prochází takto "co nejdál" grafem se nazývají hrany stromové. Z těchto hran je poté vytvořen strom nejkratších cest z kořene (počátečního uzlu). Když algoritmus zkouší nalézt další FRESH uzly po dalších hranách, tak se stane, že místo aby tento uzel měl stav FRESH tak bude OPEN. Tuto hranu poté pojmenujeme jako zpětnou. Tuto zpětnou vazbu vlastně ani nevyužijeme jelikož díky ní pouze zjistíme, že dále pokračovat již není možné a musíme se algoritmem vracet zpět a zkoušet cestu přes jinou hranu vedoucí k dalšímu následníkovi. Jestliže narazíme z uzlu OPEN na uzel CLOSE, jedná se o příčnou či o dopřednou hranu. Mezi těmito dvěma typy hran rozlišujeme podle časové značky otevření uzlu. Jestliže se dostaneme z uzlu OPEN s časovou značkou otevření například 10 do uzlu CLOSE, přes dopřednou hranu tak bude platit že tento CLOSE uzel bude mít časovou značku otevření vyšší než 10. Dopředná hrana spojí uzel s nižší čas. značkou otevření s uzlem s vyšší značkou otevření. Jestliže se stane tato situace přesně opačně, že hrana spojí uzel s vyšší čas. značkou otevření s uzlem s nižší značkou otevření, bude se jednat o hranu příčnou. Stejně jako hranu zpětnou tak ani posledně dvě zmiňované hrany ve výsledném stromu nejkratších vzdáleností nevyužijeme a slouží nám pouze jen pro to abychom zjistili, že se máme vydat jinou cestou.
[editovat] 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 }
[editovat] 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 vyvolána metoda DFS-Projdi. V této metodě je na počátku stav uzlu, pro který byla tato metoda volána nastaven na OPEN. 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 uzlu, pro který bylo voláno DFS-projdi zjistí, jestli je jako následník ještě FRESH, zapíše se hodnota předchůdce a zavolá se rekurzivně znovu metoda DFS-Projdi na tohoto následníka v kterém právě jsme. Jestliže se projdou všichni následníci uzlu, tento uzel se uzavře, neboli se tomuto uzlu přiřadí stav CLOSE 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ší.
[editovat] Použité datové struktury
1) Pole stavů - V tomto poli jsou uloženy
stavy jednotlivých uzlů.
2) Pole č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.
3) Pole č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 CLOSE.
4) Pole předchůdců - V tomto poli jsou uloženy
předchůdci jednotlivých uzlů. Z tohoto pole se poté konstruuje strom
nejkratších cest.
[editovat] Rozdíl v algoritmu při aplikaci na neorientovaný graf
Algoritmus má i pro neorientovaný graf stejný průběh. Jediné v čem se celkově algoritmus liší oproti aplikaci na orientovaný graf, je ž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é v tomto typu grafu neexistuje.
[editovat] Další využití algoritmu
Algoritmus prohledá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.
[editovat] 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í tak tento daný uzel vložíme do zásobníku. Na konci běhu algoritmu máme v zásobníku topologicky uspořádané uzly.
[editovat] Nalezení silných komponent
Pomocí algoritmu prohledá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.
[editovat] Zjištění acykličnosti grafu
Zjištění acykličnosti grafu provedeme pouze přidáním podmínky, že jestliže algoritmus nalezně nějakou hranu kterou určíme jako zpětnou tak se v grafu bude vyskytovat cyklus. Zpětná hrana totiž v grafu tvoří cykly.
[editovat] Složitost algoritmu
Celková složitost algoritmu : O(|V| + |E|), kde V je počet vrcholů a E počet hran daného grafu.
[editovat] Související články
[editovat] Reference
- Jakub Černý: Základní grafové algoritmy (texty v pdf)