Prohledávání do hloubky: Porovnání verzí
Smazaný obsah Přidaný obsah
Řádek 11:
Algoritmus je ú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).
Během prohledávání se mění stavy vrcholů. Na začátku jsou všechny vrcholy ve stavu
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é. Č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. Pokud tato hrana vede do
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. 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.
| |||