Strona główna » Algorytmy » Artykuły » Przeszukiwanie w Głąb (DFS)
 

Przeszukiwanie w Głąb (DFS)

Cel

Przeszukiwanie grafu w głąb (DFS) jest używane w badaniu spójności grafu (prostego oraz skierowanego). Ponadto algorytm ten jest wykorzystywany w wielu innych algorytmach np. sortowaniu topologicznym. W tym artykule zostanie wyjaśniona podstawowa implementacja tego algorytmu.

Algorytm

Przeszukiwanie w głąb (DFS) jest to algorytm rekurencyjny. Do działania potrzebna jest tablica o tylu elementach ile jest węzłów w przekazanym grafie, gdzie można przechować informację czy dany element został odwiedzony oraz jaki jest jego poprzednik. Działanie algorytmu jest następujące: przygotuj tablicę, a następnie dla każdego nieodwiedzonego węzła odwiedź go. Odwiedzenie węzła polega na przypisaniu temu węzłowi, że został odwiedzony, a następnie należy odwiedzić wszystkich jego sąsiadów.

Istnieje możliwość zastosowania algorytmu DFS dla dowolnego wierzchołka. Należy pamiętać, że z wierzchołka 1 i 2 uzyska się dwa różne wyniki. Jeśli algorytm ma rozpocząć przeszukiwanie od innego wierzchołka niż pierwszego w grafie to należy wpierw odwiedzić określony wierzchołek startowy zanim zacznie się przchodzić wszystkie po kolei.

Przykład

Poniższy przykład pokaże działanie algorytmu DFS dla poniższego grafu:

Punktem początkowym jest zaznaczony punkt A. W tabeli została przedstawiona aktualna kolejka oraz właściwości poszczególnych obiektów:

WęzełABCDEFGHKomentarz
A0, ☑∞, ☐∞, ☐∞, ☐∞, ☐∞, ☐∞, ☐∞, ☐[A] Przeglądamy sąsiadów A, czyli B, C, D
.B0, ☑A, ☑A, ☐A, ☐∞, ☐∞, ☐∞, ☐∞, ☐[B] Przeglądamy sąsiadów B: E
..E0, ☑A, ☑A, ☐A, ☐B, ☐∞, ☐∞, ☐∞, ☐[B] Przeglądamy sąsiadów B: E
..E0, ☑A, ☑A, ☐A, ☐B, ☑∞, ☐∞, ☐∞, ☐[E] Brak sąsiadów, powrót do B
.B0, ☑A, ☑A, ☐A, ☐B, ☑∞, ☐∞, ☐∞, ☐[B] Brak sąsiadów, powrót do A
A0, ☑A, ☑A, ☐A, ☐B, ☑∞, ☐∞, ☐∞, ☐[A] Przeglądanie kolejnego sąsiada: C
.C0, ☑A, ☑A, ☑A, ☐B, ☑∞, ☐∞, ☐∞, ☐[C] Brak sąsiadów, powrót do A
A0, ☑A, ☑A, ☑A, ☐B, ☑∞, ☐∞, ☐∞, ☐[A] Przeglądanie ostatniego sąsiada: D
.D0, ☑A, ☑A, ☑A, ☑B, ☑D, ☐∞, ☐D, ☐[D] Przeglądanie sąsiadów D: F, H
..F0, ☑A, ☑A, ☑A, ☑B, ☑D, ☑∞, ☐D, ☐[F] Brak sąsiadów, powrót do D
.D0, ☑A, ☑A, ☑A, ☑B, ☑D, ☑∞, ☐D, ☐[D] Przeglądanie kolejnego sąsiada H
..H0, ☑A, ☑A, ☑A, ☑B, ☑D, ☑H, ☐D, ☑[H] Przeglądanie sąsiada G
...G0, ☑A, ☑A, ☑A, ☑B, ☑D, ☑H, ☑D, ☑[G] Brak nieodwiedzonych sąsiadów, powrót do H
..H0, ☑A, ☑A, ☑A, ☑B, ☑D, ☑H, ☑D, ☑[G] Brak nieodwiedzonych sąsiadów, powrót do D
.D0, ☑A, ☑A, ☑A, ☑B, ☑D, ☑H, ☑D, ☑[D] Brak nieodwiedzonych sąsiadów, powrót do A
A0, ☑A, ☑A, ☑A, ☑B, ☑D, ☑H, ☑D, ☑[A] Brak nieodwiedzonych sąsiadów, koniec algorytmu

Algorytm kończy działanie, ponieważ wierzchołek A nie ma już więcej sąsiadów, a wszystkie pozostałe wierzchołki zostały już odwiedzone. Z tego można wywnioskować, że graf jest spójny, ponieważ z wierzchołka A zostały osiągnięte wszystkie inne wierzchołki. Na koniec została uzyskana następująca tablica:

WęzełABCDEFGH
Poprzednik0AAABDHD

Na jej podstawie można prześledzić działanie algorytmu. Należy pamiętać, że znalezione tutaj drogi z pewnego wierzchołka do innego wcale nie muszą być najkrótsze. Przy takim zadaniu należy zastosować wtedy algorytm BFS.

Implementacja

Algorytm zostanie podzielony na dwie części: funkcję DFS(), która przygotuje tablicę i zainicjuje odwiedzanie oraz funkcję odwiedzWezel(), która będzie rekurencyjnie przechodziła po grafie dalej.

DFS

Poniżej została przedstawiona funkcja DFS(), która przyjmuje dwa argumenty: macierz - macierz sąsiedztwa grafu oraz start - wierzchołek początkowy od którego ma zostać rozpoczęte przeszukiwanie.

  1. dane* DFS(int** macierz, int n, int start) {
  2.   dane* tab = new dane[n];
  3.   for (int i = 0; i < n; i++) {
  4.     tab[i].odwiedzony = false;
  5.     tab[i].poprzednik = -1;
  6.   }
  7.   odwiedzWezel(macierz, n, tab, start);
  8.   for (int i = 0; i < n; i++)
  9.     if (!tab[i].odwiedzony)
  10.       odwiedzWezel(macierz, n, tab, i);
  11.   return tab;
  12. }

(2.) Inicjalizacja tablicy i (3. - 6.) jej początkowe ustawienie. Następnie (7.) odwiedź węzeł początkowy, a potem (8. - 10.) pozostałe, nieodwiedzone wierzchołki alfabetycznie. Na koniec (11.) zwróć obliczoną tablice.

Odwiedzanie wierzchołka

Odwiedzenie wierzchołka polega na przypisaniu, że został odwiedzony (bez tego rekurencja byłaby nieskończona), a następnie odwiedza wszystkich nieodwiedzonych sąsiadów wierzchołka przypisując im, że poprzednikiem jest aktualnie odwiedzony wierzchołek.

  1. void odwiedzWezel(int** macierz, int n, dane* tab, int u) {
  2.   tab[u].odwiedzony = true;
  3.   for (int i = 0; i < n; i++) {
  4.     if (macierz[u][i] > 0 && !tab[i].odwiedzony) {
  5.       tab[i].poprzednik = u;
  6.       odwiedzWezel(macierz, n, tab, i);
  7.     }
  8.   }
  9. }

(2.) Zaznacz, że wierzchołek został odwiedzony i (3.) wyszukaj sąsiadów, którzy (4.) nie zostali odwiedzeni, a następnie (5.) zaktualizuj ich poprzednika oraz (6.) odwiedź je.

Testowanie funkcji

Działanie napisanej funkcji można sprawdzić poniższym fragmentem kodu, który wczyta od użytkownika dane, a następnie wypisze wynik.

  1. void wypiszdane(int i, dane d) {
  2.   cout << i << "\t";
  3.   if (!d.odwiedzony) {
  4.     cout << "nieodwiedzony";
  5.   } else {
  6.     if (d.poprzednik == -1)
  7.       cout << "brak";
  8.     else cout << d.poprzednik;
  9.   }
  10.   cout << endl;
  11. }
  12. int main () {
  13.   int n, s;
  14.   cout << "Ile wierzcholkow ma graf?\n n = ";
  15.   cin >> n;
  16.   cout << "Podaj wierzcholek poczatkowy\n s = ";
  17.   cin >> s;
  18.   cout << "Podaj macierz:" << endl;
  19.   int** macierz = new int*[n];
  20.   for (int i = 0; i < n; i++) {
  21.     macierz[i] = new int[n];
  22.     for (int j = 0; j < n; j++)
  23.       cin >> macierz[i][j];
  24.   }
  25.   dane* tab = DFS(macierz, n, s);
  26.   cout << "Wezel\tPoprzednik" << endl;
  27.   for (int i = 0; i < n; i++)
  28.     wypiszdane(i, tab[i]);
  29.   system("pause");
  30.   return 0;
  31. }
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1