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

'''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 ==

 

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.

 

[[Image:Depth search.GIF|thumb|800px|left|]]

 

* [http://links.math.rpi.edu/applets/appindex/graphtheory.html Interaktivní demonstrace]

 

[[Kategorie:Grafové algoritmy]]

 

[[ca:Cerca en profunditat]]