Przeszukiwanie w głąb/Depth First Search

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Zasugerowano, aby ten artykuł zintegrować z artykułem Depth First Search.

DFS - (z ang. Depth First Search) jest to algorytm przeszukiwania grafu "w głąb". Przy przeszukiwaniu w głąb każdy wierzchołek grafu, oraz każda krawędź jest rozpatrywana dokładnie jeden raz (stąd złożoność algorytmu DFS O(n+m)). Algorytm DFS jest algorytmem rekurencyjnym. Funkcja wywołuje sama siebie, aż stwierdzi że odwiedziła już wszystkie wierzchołki grafu.

Opis działania algorytmu:

Na początku wszystkie wierzchołki grafu "pokolorowane" są na biało (tzn. są nieodwiedzone)
Zaczynamy przeszukiwanie od zadanego wierzchołka (np.1), kolorujemy go na szaro (został odwiedzony, ale nie zakończony)
Odwiedzamy wszystkich białych sąsiadów i kolorujemy ich na szaro.
Od każdego wierzchołka pokolorowanego na szaro odpalamy tę samą funkcję.
Jeśli wierzchołek nie ma białych sąsiadów, to kolorujemy go na czarno i "cofamy" się, aż wrócimy do wierzchołka wyjściowego.

Może się zdarzyć, że w ten sposób nie odwiedzimy wszystkich wierzchołków grafu. (np. graf 1->2, 3->4). Aby uniknąć takich problemów, wystarczy po sprawdzeniu wierzchołków od 1 uruchomić funkcję dfs dla wszystkich innych białych wierzchołków. Nie musimy się martwić o złożoność- jeśli do wierzchołka doszliśmy od punktu 1, to nie będziemy już rozpatrywać go ponownie dzięki uprzedniemu pokolorowaniu go na czarno.

[edytuj] Przykładowy zapis w pseudokodzie(wzorowanym na Pascalu)

graf zapisany jako macierz incydencji.

procedure DFS(k:longint);
 var j:longint;
begin
  czy[k]:=szary;  
   for j:=1 to V do
     if (t[k][j]) and (czy[j]=bialy) then DFS(j);      
  czy[k]:=czarny;
end;

begin 
 readln(V,E);   {wierzcholki, krawedzie}
 wczytaj_graf;
 for i:=1 to V do czy[i]:=bialy; {zeruj}
 for i:=1 to V do
  if czy[i]=bialy then DFS(i); 
end.

Zobacz też: problem najkrótszej ścieżki, algorytm Bellmana-Forda