Podobně jako u stromů k základním úkolům na grafech patří nalezení všech vrcholů grafu systematickým způsobem, čemu říkáme prohledávání grafu. Na rozdíl od stromu, kde jsme jeho procházení začínali kořenem, v případě grafu obecně můžeme jeho prohledávání začít v libovolném vrcholu.
Pro daný graf G = (V, H) vybereme začáteční vrchol s a systematickým postupem nalezneme všechny dosažitelné vrcholy, tj. takové, ke kterým vede v grafu G cesta tvořená posloupností jeho hran. Název prohledávání je odvozen z toho, že ze začátečního vrcholu s nalezneme všechny vrcholy ve vzdálenosti k od vrcholu s předtím, než nalezneme vrcholy ve vzdálenosti k+1. Jinými slovy napřed nalezneme všechny sousedy začátečního vrcholu, potom jejich sousedy atd. Algoritmus pracuje pro orientované i neorientované grafy.
Při postupu prohledávání je potřeba mít informaci jestli jsme již vrchol nalezli. Další informací, kterou můžeme sledovat je, jestli jsme pro daný vrchol nalezli všechny sousedy. Tyto informace můžeme udržovat tzv. barvením vrcholů. Před začátkem prohledávání jsou všechny vrcholy bílé a po prvním nalezení je vrchol obarven šedě. Nalezli-li jsme všechny jeho sousedy a tedy nemá bíle obarvené sousedy, je vrchol obarven černě. Algoritmus končí se všemi uzly obarvenými černě.
Prohledávání do šířky začneme obarvením začátečního vrcholu s šedě a jeho vložením do fronty vrcholů. Postupně vybíráme vrcholy z fronty, přičemž všechny bílé sousedy právě vybraného vrcholu obarvíme šedě a vložíme do fronty a potom vybraný vrchol obarvíme černě. Algoritmus skončí když je fronta prázdná.
Prohledávání do šířky umožňuje nalezení vzdálenosti vrcholů grafu od začátečního vrcholu jakož i cesty ze začátečního vrcholu k vrcholům grafu.
Vzdálenost začátečního vrcholu od sebe samého je 0. Vrcholy nalezené jako jeho sousedi mají vzdálenost o 1 větší, tedy 1, vrcholy nalezené z vrcholů ve vzdálenosti 1 mají vzdálenost o 1 větší, tedy 2 atd.
Pro nalezení cesty ze začátečního vrcholu k vrcholu grafu stačí, aby jsme když je vrchol poprvé nalezen do něj uložili vrchol, z kterého byl nalezen. Tomuto vrcholu budeme říkat předchůdce. Začáteční vrchol nemá předchůdce. Pro každý jiný vrchol známe jeho předchůdce, pro něj jeho předchůdce, atd. až přijdeme k vrcholu bez předchůdce, tedy k začátečnímu vrcholu.
Pro uložení uvedených informací rozšíříme prvky pole vrcholy o odpovídající položky, tedy třídu Vrchol o členské proměnné:
barva - barva vrcholu, na začátku bílá
vzdalenost - vzdálenost od vrcholu s, na začátku nekonečno
predchudce - číslo předcházejícího vrcholu, na začátku -1, není žádný předchůdce
Odpovídající algoritmus BFS (breath first search) je na obr.
. Začáteční vrchol obarvíme šedě - 'S', jeho vdálenost nastavíme na 0 a vložíme ho do fronty. V cyklu pak z fronty vybereme vrchol a vkládáme do fronty všechny sousedy vybraného vrcholu pokud byly bílé - 'B', přičemž před vložením je obarvíme šedě, určíme jejich vzálenost od začátečního vrcholu a jejich předchůdce. Skončí-li cyklus for, pro vybraný vrchol jsme prošli všechny sousedy a obarvíme ho černě - 'C'.
Činnost algoritmu je ilustrována postupně na obr.
a 
, kde začáteční vrchol prohledávání je 6 a u vrcholů je vyznačena jejich vzdálenost od začátečního vrcholu.
Vrcholy grafu, jsou při vložení do fronty obarveny šedě a již se nikdy nestanou bílé, a proto jsou do ní vloženy a vybrány nejvíce jednou. Protože vložení a vybrání z fronty je O(1), trvání všech těchto operací je O(|V |). Seznamy sousednosti vrcholů jsou procházené když je vrchol vybrán z fronty. Součet jejich délek je Θ(|H|) a tedy čas jejich procházení je O(|H|). Čas prohledávání do hloubky tedy je O( |V | + |H| ).
Vykonáním prohledávaní do šířky nalezneme všechny dosažitelné vrcholy ze začátečního vrcholu s a vypočteme jejich vzdálenost (počet hran) od vrcholu s, která je uložená v členské proměnné vzdalenost.
Pro dosažitelné vrcholy jsme prohledáváním do šířky ukazateli predchudce vytvořili strom, nazývaný BSF strom, kterého kořen je začáteční vrchol s. BFS strom vytvořený prohledáváním grafu na obr. a , je na obr.
, přičemž jeho kořenem je vrchol 6. Definujeme-li v grafu G(V,H) délku nejkratší cesty mezi vrcholy s,vÎV jako cestu s minimálním počtem hran ze všech cest z vrcholu s do vrcholu v, potom délka nejkratší cesty mezi vrcholy s a v je rovná hloubce vrcholu v v tomto stromě.
Vrcholy na nejkratší cestě z vrcholu s do vrcholu v po vykonání prohledávání do šířky vytiskne metoda tiskCesty na obr.
.
Prohledávání do šířky je základem dalších algoritmů (Primův algoritmus minimální kostry, Dijkstrův algoritmus minimální cesty).
Na rozdíl od prohledávání do šířky v grafu hledáme vrcholy, když je to možné, napřed do „hloubky“, tj. do větší vzdálenosti. Tedy, když má začáteční vrchol souseda, dál hledáme některého z jeho sousedů atd. Když projdeme všechny sousedy vrátíme se k vrcholu, z kterého byl nalezen a stejným způsobem pokračujeme dál. Algoritmus opět pracuje pro orientované i neorientované grafy. Podobně jako u prohledávání do šířky použijeme techniku barvení uzlů. Na začátku prohledávání jsou všechny vrcholy obarveny bíle, když je vrchol poprvé nalezen je obarven šedě. Když jsme prošli všechny jeho sousedy, je obarven černě, kdy se vrátíme k vrcholu, z kterého byl objeven, tedy k jeho předchůdci anebo skončíme, když jde o začáteční vrchol, který nemá předchůdce.
Z uvedeného plyne, že stejně jako u prohledávání do šířky budeme ve vrcholu ukládat ukazatel na jeho předchůdce, tj. vrchol z kterého byl nalezen. Prohledávání do hloubky tedy pro vrcholy nalezené ze začátečního vrcholu opět vytvoří strom dosažitelných vrcholů, nyní nazývaný DFS strom, kterého kořen je začáteční vrchol. Strom vytvořený prohledáváním do šířky se obecně bude lišit od stromu vytvořeném prohledáváním do hloubky.
Kromě položek barva a predchudce zavedeme pro každý vrchol dvě časové značky, pro které je jednotka „času“ přechod na další vrchol a to
objeven - čas nalezení vrcholu, kdy je obarven šedě
dokoncen - čas konce procházení seznamu sousedů vrcholu, kdy je vrchol obarven černě
Protože, každý vrchol je jednou nalezen a jednou ukončen hodnoty časových značek jsou mezi 1 a 2|V|. Pro každý vrchol u platí objeven(u) < dokoncen(u). Okamžitou hodnotu času pro prohledávaný graf budeme uchovávat na proměnné cas, která má začáteční hodnotu 0.
Volání rekurzivní metody DFS(s) (depth first search) na obr.
vykoná prohledání grafu do hloubky z vrcholu s, který má roli prvního nalezeného vrcholu.
Algoritmus pro zadaný vrchol, tento obarví šedě, nastaví čas objeven jeho nalezení a prochází jeho sousedy. Je-li soused bílý, uloží jako jeho předchůdce vrchol, z kterého byl nalezen a zavolá pro něj metodu DFS( ). Když v (rekurzivně volané) metodě DFS( ) skončí cyklus for, je dokončeno procházení sousedů vrcholu, pro který byla volána a tedy tento vrchol je obarven černě a nastaven čas dokoncen.
Jestliže po vykonání DFS( ) zůstaly neobjevené vrcholy, můžeme jeden z nich vybrat a opět z něho začít prohledávání. Takto můžeme pokračovat dokud je nějaký vrchol bílý a vznikne tak tzv. les stromů prohledáváním do hloubky. Podobně můžeme postupovat i při prohledávání grafu do šířky. Jestli prohledávání grafu použijeme jenom pro jeden začáteční vrchol anebo opakovaně závisí na použití výsledků prohledávání. V článku 6.4 ukážeme vhodnost vytvoření lesa stromů prohledáváním do hloubky.
Činnost algoritmu DFS jeho aplikací dokud existuje bílý vrchol je ilustrována postupně na obr.
,
a 
. Časy nalezení a dokončení jednotlivých vrcholů jsou odděleny lomítkem.
Použitím zásobníku pro nalezené vrcholy lze rekurzivní algoritmus prohledávání přepsat na iterační.
Poznamenejme ještě, že binární stromy jsou specielním případem grafu a je analogie mezi průchodem stromu a prohledáváním grafu.
Na začátku prohledávání jsou všechny vrcholy obarveny bíle a jejich položka prechudce je nastavena na -1 právě jednou, což trvá Θ(|V|). Metoda DFS( ) je volána pro bílé vrcholy a tedy právě jednou pro každý vrchol, protože tento je při volání ihned obarven šedě. Cyklus for je vykonán pro všechny sousedy vrcholu, tedy tolikrát kolik z něho vychází hran. Počet jeho vykonání je tedy omezen součtem délek seznamů sousednosti, a tedy je O(|H|). Čas výpočtu prohledávání do hloubky potom je O( |V| + |H| ).
Vytvoření lesa stromů prohledáním orientovaného grafu do hloubky umožňuje zavést klasifikaci jeho hran.
1. Stromové hrany. Jsou hrany patřícím stromům lesa. Hrana (u,v) je stromová byl-li vrchol v objeven z vrcholu u.
2. Zpětné hrany. Jsou hrany (u,v), kde vrchol v je předkem vrcholu u, tj. vrchol v leží na cestě z kořene DFS stromu do vrcholu u. Hrana (u,u) je považována za zpětnou.
3. Dopředné hrany. Jsou hrany (u,v), kde vrchol u je předkem vrcholu v v DSF stromě.
4. Křižující hrany. Všechny ostatní hrany. Spojují vrcholy jednoho DSF stromu pokud jeden z nich není předkem druhého anebo vrcholy různých stromů lesa DSF stromů.
Z postupu prohledávaní plyne, že hranu (u,v) můžeme klasifikovat úpravou metody DFS( ). Když hranou poprvé procházíme potom:
1. Je-li vrchol v bílý, hrana je stromová.
2. Je-li vrchol v šedý, hrana je zpětná.
3. Je-li vrchol v černý a objeven(u) < objeven(v), hrana je dopřední.
4. Je-li vrchol v černý a objeven(u) > objeven(v), hrana je křižující.
V případě neorientovaného grafu je (u,v) a (v,u) tatáž hrana. Hrana je potom klasifikována podle prvního z jejich vyjádření, které nalezne algoritmus prohledávání do hloubky. Je možné ukázat, že při prohledávání neorientovaného grafu do hloubky, každá z jeho hran je buď stromová nebo zpětná.
Zpětné hrany jsou klíčem, k nalezení cyklů v grafu. Vznikne-li prohledáním grafu do hloubky zpětná hrana, graf obsahuje cyklus. Je-li (u,v) zpětná hrana, potom cesta z v do u a tato hrana tvoří cyklus. Obráceně lze dokázat, že je-li v grafu cyklus, jeho prohledáním do hloubky musí vzniknout zpětná hrana.