Prohledávání do hloubky: Porovnání verzí
Smazaný obsah Přidaný obsah
m uprights |
m typo CLOSE -> CLOSED značka: editace z Vizuálního editoru |
||
Řádek 46:
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
=== Použité datové struktury ===
Řádek 52:
# 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
# Pole p předchůdců — v tomto poli jsou uloženi předchůdci jednotlivých uzlů ve stromě cest.
| |||