Procedury przeglądania grafu w głąb (DFS) i wszerz (BFS) są bardzo często wykorzystywane w innych, bardziej złożonych algorytmach (np. badania spójności).
W strategii DFS wybrany wierzchołek należy umieścić na stosie, zaznaczyć jako odwiedzony a następnie przejść do jego następnika. Następnik również umieszczamy na stosie, zaznaczamy jako odwiedzony przechodzimy do jego następnika. Jak widać procedurę można wywoływać rekurencyjnie. Jeśli dojdziemy do takiego wierzchołka, że nie ma on krawędzi incydentych z nieodwiedzonymi wierzchołkami, należy usunąć go ze stosu i pobrać ze stosu kolejny wierzchołek do przeszukania. W praktyce stosuje się zasadę, że jeśli przeszukiwany wierzchołek jest połączony krawędziami z wieloma wierzchołkami, wybiera się do przeszukania wierzchołek o najmniejszej liczbie porządkowej. Dlatego szukając kolejny nieodwiedzony następnik należy rozpoczynać od końca macierzy. Przeszukiwanie DFS wykorzystuje się do badania spójności grafu. Jeśli procedura wywołana dla pierwszego wierzchołka "dotrze" do wszystkich wierzchołków grafu to graf jest spójny.
Aby przeszukać graf wszerz (BFS) należy zamiast stosu wykorzystać kolejkę do przechowywania wierzchołków a kolejnych nieodwiedzonych następników szukać od początku macierzy.
Oto przykładowy graf: Przykład:

Przeszukiwanie w głąb (DFS):
Zaczynamy od wierzchołka 1, odwiedzamy go i wrzucamy na stos wszystkie jego następniki, w kolejności od tego z największym indeksem:
Odwiedzone: 1; Stos: 3, 2;
Bierzemy wierzchołek ze stosu, odwiedzamy go i znów wrzucamy wszystkie jego nieodwiedzone jeszcze następniki na stos:
Odwiedzone: 1, 2; Stos: 3, 5, 4;
Bierzemy wierzchołek ze stosu, odwiedzamy go, jedynym następnikiem 4 jest 1, ale ten wierzchołek już odwiedzaliśmy więc nie wrzucamy nic na stos:
Odwiedzone: 1, 2, 4; Stos: 3, 5;
Bierzemy wierzchołek ze stosu, odwiedzamy go, jedynym następnikiem 5 jest 4, ale ten wierzchołek już odwiedzaliśmy więc nie wrzucamy nic na stos:
Odwiedzone: 1, 2, 4, 5; Stos: 3;
Bierzemy wierzchołek ze stosu, odwiedzamy go, jedynym następnikiem 3 jest 6, ten wierzchołek jeszcze nie jest odwiedzony więc wrzucamy go na stos:
Odwiedzone: 1, 2, 4, 5, 3; Stos: 6;
Bierzemy wierzchołek ze stosu, odwiedzamy go, wierzchołek 6 nie ma następników, więc nie ma czego wrzucić na stos:
Odwiedzone: 1, 2, 4, 5, 3, 6; Stos: ;
Stos jest pusty zatem zakończyliśmy przeszukiwanie grafu w głąb.

Przeszukiwanie w szerz (BFS):
Zaczynamy od wierzchołka 1, odwiedzamy go i wrzucamy do kolejki wszystkie jego następniki, w kolejności od tego z najmniejszym indeksem:
Odwiedzone: 1; Kolejka: 2, 3;
Bierzemy wierzchołek z kolejki, odwiedzamy go i znów wrzucamy wszystkie jego nieodwiedzone jeszcze następniki do kolejki:
Odwiedzone: 1, 2; Kolejka: 3, 4, 5;
Bierzemy wierzchołek z kolejki, odwiedzamy go, jedynym następnikiem 3 jest 6 więc wrzucamy go do kolejki:
Odwiedzone: 1, 2, 3; Kolejka: 4, 5, 6;
Bierzemy wierzchołek z kolejki, odwiedzamy go, jedynym następnikiem 4 jest 1, ale ten wierzchołek już odwiedzaliśmy więc nie wrzucamy go do kolejki:
Odwiedzone: 1, 2, 3, 4; Kolejka: 5, 6;
Bierzemy wierzchołek z kolejki, odwiedzamy go, jedynym następnikiem 5 jest 4, ale ten wierzchołek już odwiedzaliśmy więc nie wrzucamy go do kolejki:
Odwiedzone: 1, 2, 3, 4, 5; Kolejka: 6;
Bierzemy wierzchołek z kolejki, odwiedzamy go, wierzchołek 6 nie ma następników, więc nie ma czego wrzucić do kolejki:
Odwiedzone: 1, 2, 3, 4, 5, 6; Kolejka: ;
Kolejka jest pusta zatem zakończyliśmy przeszukiwanie grafu w szerz.

Komentarze