Prohledávání do hloubky: Porovnání verzí
Smazaný obsah Přidaný obsah
m robot přidal: ko:깊이 우선 탐색 |
→Vlastnosti algoritmu: opravena chyba -- stromové hrany netvoří strom *nejkratších* cest. |
||
Řádek 11:
Algoritmus je úplný (vždy najde řešení, tzn. určitý cílový vrchol, pokud existuje), ale není optimální (pokud graf není [[strom (graf)|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) aneb nejdál, co 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
== Obecná implementace v pseudokódu ==
|