Prohledávání do hloubky: Porovnání verzí

Smazaný obsah Přidaný obsah
částečný rv - konečné grafy jsou asi důležitější a na těch úplný je, to by tam mělo zůstat
značka: vrácení zpět
JAnDbot (diskuse | příspěvky)
m robot: přidáno {{Autoritní data}}; kosmetické úpravy
Řádek 1:
[[Soubor:Depth-first-tree.svg|thumbnáhled|upright=1.3|Pořadí v jakém je přistupováno k vrcholům]]
'''Prohledávání do hloubky''' (v [[Angličtina|angličtině]] označované jako ''depth-first search'' nebo zkratkou ''DFS'') je grafový [[algoritmus]] pro procházení [[Graf (teorie grafů)|grafů]] metodou [[backtracking]]u. 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 ==
[[Soubor:Depth search.GIF|thumbnáhled|upright=1.5|Ukázka prohledávání grafu do hloubky]]
 
[[Soubor:Depth search.GIF|thumb|upright=1.5|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ý graf|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 (graf)|strom]], nemusí najít nejkratší možnou cestu k cíli). Naproti tomu na [[nekonečný graf|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í.
 
Řádek 43 ⟶ 41:
 
=== 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.
 
Řádek 49 ⟶ 46:
 
=== 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.
Řádek 56 ⟶ 52:
 
=== 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ý.
 
== Složitost algoritmu ==
 
Celková složitost algoritmu : Θ(|V| + |E|), kde ''|V|'' je počet vrcholů a ''|E|'' počet hran daného grafu.
 
Řádek 90 ⟶ 80:
* {{Commonscat}}
* [http://js1k.com/2010-first/demo/162 Prohledávání bludiště (bez cyklů)]
{{Autoritní data}}
 
[[Kategorie:Grafové algoritmy]]