Dfs

Mirosław Mortka

W przypadku przetwarzania grafów jedną z ważniejszych operacji jest systematyczne przechodzenie grafu w taki sposób, aby odwiedzić każdy wierzchołek oraz każdą krawędź jeden raz. Przechodzenie to może się odbywać w określonej kolejności wierzchołków. Dwie podstawowe metody przechodzenia grafów to BFS (ang. breadth first serach – przeszukiwanie wszerz) oraz DFS (ang. depth first serach – przeszukiwanie w głąb).

Algorytm DFS przypomina w swej zasadzie działania algorytm BFS z tym, że zamiast kolejki używamy stosu. Użycie algorytmu DFS nie gwarantuje uzyskania najkrótszych ścieżek w grafie nieważonym. Niemniej piękno jego implementacji wynika z tego, iż wykorzystując rekurencję nie musimy jawnie używać stosu.

Algorytm przeszukiwania w głąb wymaga przetworzenia wybranego sąsiada przed odwiedzeniem kolejnego wierzchołka. Nieodwiedzonych dotąd sąsiadów przetwarzanego wierzchołka typujemy jako kolejnych kandydatów do odwiedzenia, umieszczając ich na szczycie wierzchołków do przetworzenia (wywołanie rekurencyjne funkcji dla nowego wierzchołka) oraz zaznaczając jako odwiedzonych.

dfs.gif

Przykładowy kod programu w C++

// deklaracja tablicy złożonej z N_MAX wektorów
// na i-tej pozycji przechowuję w wektorze listę sąsiadów i-tego wierzchołka
vector <int> A[N_MAX]
// liczba wierzchołków n oraz liczba krawędzi k
int n, k;
// deklaracja tablicy złożonej z N_MAX elementów – informacja o przetworzeniu wierzchołka
bool odwiedzony[N_MAX]={0};

void dfs (int v)
{
     //zaznacz wierzchołek v jako odwiedzony 
     odwiedzony [v] = 1;
     //weź wszystkich nieodwiedzonych sąsiadów wierzcholka v
     for (int i=0; i<G[v].size(); i++)
     {
         int u = G[v][i]; //sasiad v 
         //jesli nieodwiedzony, odwiedzam
         if ( !odwiedzony [u] ) dfs(u);
     }
}
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License