Prohledávání grafů

Barvení grafu: Grafy je možné během průchodu obarvovat, tedy tak, že vrcholy nezpracované jsou bílé, ty které jsme navštívili obarvíme na šedo a ty které jsme navštívili a zpracovali obarvíme na černo. Progledávací algoritmy končí, pokud jsou všechny vrcholy černé nebo pokud nalezneme požadovaný vrchol

Do šírky

(breadth-first search, BFS) fronta nejdriv vyberu a obarvim na cerno 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 |).

Do hloubky

(depth-first search, DFS) zasobnik

Z pocá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