Prohledávání grafů
[editovat] Barvení grafu
Pro přehlednost při procházení grafem jednostlivé vrcholy obarvujeme
- bílá - tento vrchol algoritmus ještě nezpracoval
- šedá - vrchol byl navštíven, ale ještě se k němu budeme vracet
- černá - vrchol je zpracován, už se k němu vracet nebudeme
Na začátku jsou všechny vrcholy samozřejmě bílé a postupně během průchodu je teprve bravujeme.
Prohledávací algoritmus končí v případech, kdy:
- nalezneme požadovaný vrchol
- nebo jsou všechny vrcholy grafu obarvené na černo
[editovat] Prohledávání do šírky
(breadth-first search, BFS)
Realizace pomocí fronty
Vybereme počátecní vrchol, obarvíme na šedo a projdeme všechny jeho sousedy. Nenalezneme-li řešení, obarvíme počáteční vrchol na černo a pokračujeme výběrem každého z jeho sousedů a opet projdeme jejich sousedy, které obarvujeme. Sousedy zatím nevybíráme, zpracováváme nejprve vrcholy právě vybraného vrcholu tak dlouho, dokud tento není obarven na černo.
Lze také k vrcholům ukládat předchudce a pocet hran od pocátecního vrcholu, címž získáme (nejkratší) cestu k počátečnímu vrcholu a její délku. Prohledáním celého grafu získáme BFS strom. Implementace pomocí fronty, složitost O(|H| + |V|).
[editovat] Prohledávání do hloubky
(depth-first search, DFS)
Realizace pomocí zásobníku
Z počátecního vrcholu jdeme do jeho prvního souseda, z něj do jeho prvního souseda atd., které obarvujeme na šedo. Vybíráme ze sousedů vrcholy, které jsou bílé, které okamžite barvíme na šedo. Pokud projdeme všechny vrcholy, obarvíme vrchol na černo. a vracíme se na šedý vrchol. Pokračujeme do nalezení hledaného vrcholu nebo prohledání všech.
Prohledáním celého grafu získáme DFS strom. Implementace rekurzí nebo zásobníkem, složitost O(|H|+|V |).
Hrany orientovaného grafu: Stromové hrany (patrící do stromu, jejich směr je od výchozího vrcholu), Zpětné hrany (opačná hrana ke hraně stromové, vytváří malý cyklus, směr je do výchozího bodu), dopředné (nemusí ležet ve strome, ale její vyrcholy v něm leží, jakésy zkratky stromem) a križující (opacné k dopredným, nebo hrany mezi stromy lesa). Zpětné a křižující hrany indikují cykly v grafu.
Je-li graf rozdelen do nekolika izolovaných cástí, zbudou po prvním prohledávání bílé vrcholy. Mužeme vybrat jeden jako další pocátecní a znovu z neho spustit vyhledávání, prípadne postup opakovat, pokud zustanou opet bílé vrcholy. Získáme tím les stromů.
Jsou-li grafy orientovány, je vhodné začínat na vrcholu, do kterého nevede hrana, aby nedošlo ke zbytečnému roztržení grafu na komponenty
