Strona główna » Algorytmy » Struktury Danych » Przeszukiwanie w Głąb (DFS)
 

Przeszukiwanie w Głąb (DFS)

https://mattomatti.com/a0119

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.

C++C#
Python
  1. def DFS(macierz, start):
  2.   tab = []
  3.   for i in range(0, len(macierz)):
  4.     tab.append(dane(False, -1))
  5.   tab = odwiedzWezel(macierz, tab, start)
  6.   for i in range(0, len(macierz)):
  7.     if (not tab[i].odwiedzony):
  8.       tab = odwiedzWezel(macierz, tab, i)
  9.   return tab

(2.) Inicjalizacja tablicy i (3. - 4.) jej początkowe ustawienie. Następnie (5.) odwiedź węzeł początkowy, a potem (6. - 8.) pozostałe, nieodwiedzone wierzchołki alfabetycznie. Na koniec (9.) 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.

C++C#
Python
  1. def odwiedzWezel(macierz, tab, u):
  2.   tab[u].odwiedzony = True
  3.   for i in range(0, len(macierz)):
  4.     if (macierz[u][i] > 0 and not tab[i].odwiedzony):
  5.       tab[i].poprzednik = u
  6.       tab = odwiedzWezel(macierz, tab, i)
  7.   return tab

(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.

C++C#
Python
  1. def wypiszDane(i, d):
  2.   txt = str(i) + "\t"
  3.   if (not d.odwiedzony):
  4.     txt += "nieodwiedzony"
  5.   else:
  6.     if (d.poprzednik == -1):
  7.       txt += "brak"
  8.     else:
  9.       txt += str(d.poprzednik)
  10.   print(txt);
  11.  
  12. n = int(input('Podaj ile węzłów ma graf\n n = '))
  13. s = int(input('Podaj węzeł startowy\n s = '))
  14. print('Podaj elementy macierzy:')
  15. macierz = []
  16. for i in range(0, n):
  17.   tab = [int(x) for x in input().split()]
  18.   macierz.append(tab)
  19.  
  20. tab = DFS(macierz, s)
  21. for i in range(0, n):
  22.   wypiszDane(i, tab[i])
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1