Strona główna » Algorytmy » Struktury Danych » 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ł	A	B	C	D	E	F	G	H	Komentarz
A	0, ☑	∞, ☐	∞, ☐	∞, ☐	∞, ☐	∞, ☐	∞, ☐	∞, ☐	[A] Przeglądamy sąsiadów A, czyli B, C, D
.B	0, ☑	A, ☑	A, ☐	A, ☐	∞, ☐	∞, ☐	∞, ☐	∞, ☐	[B] Przeglądamy sąsiadów B: E
..E	0, ☑	A, ☑	A, ☐	A, ☐	B, ☐	∞, ☐	∞, ☐	∞, ☐	[B] Przeglądamy sąsiadów B: E
..E	0, ☑	A, ☑	A, ☐	A, ☐	B, ☑	∞, ☐	∞, ☐	∞, ☐	[E] Brak sąsiadów, powrót do B
.B	0, ☑	A, ☑	A, ☐	A, ☐	B, ☑	∞, ☐	∞, ☐	∞, ☐	[B] Brak sąsiadów, powrót do A
A	0, ☑	A, ☑	A, ☐	A, ☐	B, ☑	∞, ☐	∞, ☐	∞, ☐	[A] Przeglądanie kolejnego sąsiada: C
.C	0, ☑	A, ☑	A, ☑	A, ☐	B, ☑	∞, ☐	∞, ☐	∞, ☐	[C] Brak sąsiadów, powrót do A
A	0, ☑	A, ☑	A, ☑	A, ☐	B, ☑	∞, ☐	∞, ☐	∞, ☐	[A] Przeglądanie ostatniego sąsiada: D
.D	0, ☑	A, ☑	A, ☑	A, ☑	B, ☑	D, ☐	∞, ☐	D, ☐	[D] Przeglądanie sąsiadów D: F, H
..F	0, ☑	A, ☑	A, ☑	A, ☑	B, ☑	D, ☑	∞, ☐	D, ☐	[F] Brak sąsiadów, powrót do D
.D	0, ☑	A, ☑	A, ☑	A, ☑	B, ☑	D, ☑	∞, ☐	D, ☐	[D] Przeglądanie kolejnego sąsiada H
..H	0, ☑	A, ☑	A, ☑	A, ☑	B, ☑	D, ☑	H, ☐	D, ☑	[H] Przeglądanie sąsiada G
...G	0, ☑	A, ☑	A, ☑	A, ☑	B, ☑	D, ☑	H, ☑	D, ☑	[G] Brak nieodwiedzonych sąsiadów, powrót do H
..H	0, ☑	A, ☑	A, ☑	A, ☑	B, ☑	D, ☑	H, ☑	D, ☑	[G] Brak nieodwiedzonych sąsiadów, powrót do D
.D	0, ☑	A, ☑	A, ☑	A, ☑	B, ☑	D, ☑	H, ☑	D, ☑	[D] Brak nieodwiedzonych sąsiadów, powrót do A
A	0, ☑	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ł	A	B	C	D	E	F	G	H
Poprzednik	0	A	A	A	B	D	H	D

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++

Python

static dane[] DFS(int[,] macierz, int start) {
dane[] tab = new dane[macierz.GetLength(0)];
for (int i = 0; i < macierz.GetLength(0); i++) {
tab[i].odwiedzony = false;
tab[i].poprzednik = -1;
}
odwiedzWezel(macierz, ref tab, start);
for (int i = 0; i < macierz.GetLength(0); i++)
if (!tab[i].odwiedzony)
odwiedzWezel(macierz, ref tab, i);
return tab;
}

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

C++

Python

static void odwiedzWezel(int[,] macierz, ref dane[] tab, int u) {
tab[u].odwiedzony = true;
for (int i = 0; i < macierz.GetLength(0); i++) {
if (macierz[u, i] > 0 && !tab[i].odwiedzony) {
tab[i].poprzednik = u;
odwiedzWezel(macierz, ref tab, i);
}
}
}

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

Python

static void wypiszdane(int i, dane d) {
Console.Write("{0}\t", i);
if (!d.odwiedzony) {
Console.Write("nieodwiedzony");
} else {
if (d.poprzednik == -1)
Console.Write("brak");
else Console.Write("{0}", d.poprzednik);
}
Console.WriteLine();
}
static void Main(string[] args) {
Console.Write("Podaj ile jest wierzchołków w grafie\n n = ");
int n = Convert.ToInt32(Console.ReadLine());
Console.Write("Podaj węzeł początkowy\n s = ");
int s = Convert.ToInt32(Console.ReadLine());
int[,] macierz = new int[n, n];
for (int i = 0; i < n; i++) {
string[] str = Console.ReadLine().Split(' ');
for (int j = 0; j < n; j++) {
macierz[i, j] = Convert.ToInt32(str[j]);
}
}
dane[] tab = DFS(macierz, s);
Console.WriteLine("Węzeł\tPoprzednik");
for (int i = 0; i < n; i++)
wypiszdane(i, tab[i]);
Console.ReadKey();
}

Kod źródłowy Implementacja