Prohledávání do hloubky: Porovnání verzí
Smazaný obsah Přidaný obsah
Bez shrnutí editace |
Bez shrnutí editace |
||
Řádek 15:
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), či co nejdál 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 nejkratších cest z kořene (počátečního uzlu). Když algoritmus zkouší nalézt další FRESH uzly po dalších hranách, tak se stane, že místo aby tento uzel měl stav FRESH tak bude OPEN. Tuto hranu poté pojmenujeme jako zpětnou. Tuto zpětnou vazbu vlastně ani nevyužijeme jelikož díky ní pouze zjistíme, že dále pokračovat již není možné a musíme se algoritmem vracet zpět a zkoušet cestu přes jinou hranu vedoucí k dalšímu následníkovi. Jestliže narazíme z uzlu OPEN na uzel CLOSE, jedná se o příčnou či o dopřednou hranu. Mezi timito dvěma typy hran rozlišujeme podle časové značky otevření uzlu. Jestliže se dostaneme z uzlu OPEN s časovou značkou otevření například 10 do uzlu CLOSE, přes dopřednou hranu tak bude platit že tento CLOSE uzel bude mít časovou značku otevření vyšší než 10. Dopředná hrana spojí uzel s nižší čas. značkou otevření s uzlem s vyšší značkou otevření. Jestliže se stane tato situace přesně opačně, že hrana spojí uzel s vyšší čas. značkou otevření s uzlem s nižší značkou otevření, bude se jednat o hranu příčnou. Stejně jako hranu zpětnou tak ani posledně dvě zmiňované hrany ve výsledném stromu nejkratších vzdáleností nevyužijeme a slouží nám pouze jen pro to abychom zjistili, že se máme vydat jinou cestou.
== Obecná implementace v pseudokódu ==
Řádek 60:
== Další využití algoritmu ==
Algoritmus prohledá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í časouvou značku uzavření tak tento daný 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ání do hloubky určíme u všech uzlů časové značky uzavření. Pote graf na kterém jsme tento algoritmus spustili poprvé, tak mu změníme orientaci na opačnou (každá hrana bude opačně orientovaná). Na tento opačně orientovaný graf spustíme znovu algoritmus prohledávání do hloubky a uzly budeme brát 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 ===
Zjištění acykličnosti grafu provedeme pouze přidáním podmínky, že jestliže algoritmus nalezně nějakou hranu kterou určíme jako zpětnou tak se v grafu bude vyskytovat cyklus. Zpětná hrana totiž v grafu tvoří cykly.
== Složitost algoritmu ==
| |||