Przeszukiwanie w głąb (DFS)

Wprowadzenie

Przeszukiwanie w głąb (ang. Depth-First Search, DFS) to fundamentalny algorytm przeszukiwania grafów, który eksploruje graf tak głęboko jak to możliwe przed cofnięciem się (backtracking).

DFS jest podstawą wielu zaawansowanych algorytmów grafowych: - Wykrywanie cykli - Sortowanie topologiczne (DAG) - Znajdowanie silnie spójnych składowych (algorytm Tarjana, Kosaraju) - Rozwiązywanie labiryntów - Sprawdzanie osiągalności - Drzewa rozpinające

Idea algorytmu DFS

Koncepcja "w głąb"

DFS odwiedza wierzchołki idąc tak głęboko jak to możliwe wzdłuż każdej gałęzi przed cofnięciem się:

Graf:
        A
       / \
      B   C
     / \   \
    D   E   F

Kolejność BFS: A → B → C → D → E → F (warstwa po warstwie)
Kolejność DFS: A → B → D → E → C → F (w głąb!)

Kluczowa różnica: DFS najpierw wyczerpuje jedną gałąź, zanim przejdzie do następnej.

Struktura danych: Stos (LIFO)

DFS wykorzystuje stos (stack) lub rekurencję:

Iteracyjnie (stos): 1. Dodaj wierzchołek startowy na stos 2. Dopóki stos nie jest pusty: - Pop wierzchołek ze stosu - Odwiedź go - Push wszystkich nieodwiedzonych sąsiadów na stos

Rekurencyjnie: - Funkcja rekurencyjna sama w sobie używa stosu wywołań

Kluczowa właściwość: LIFO (Last In, First Out) powoduje "głębokie" przeszukiwanie.

Algorytm DFS - pseudokod

Wersja rekurencyjna

DFS(graf G, wierzchołek v):
    1. Oznacz v jako odwiedzony
    2. Dla każdego sąsiada u wierzchołka v:
        a. Jeśli u nie jest odwiedzony:
            - DFS(G, u)  // Rekurencyjnie

Wersja iteracyjna

DFS_iterative(graf G, wierzchołek start):
    1. Utwórz stos S
    2. Push start na S

    3. Dopóki S nie jest pusty:
        a. v = S.pop()
        b. Jeśli v nie jest odwiedzony:
            i.  Oznacz v jako odwiedzony
            ii. Dla każdego sąsiada u wierzchołka v:
                - Jeśli u nie jest odwiedzony:
                    Push u na S

Złożoność: - Czasowa: O(V + E) - Pamięciowa: O(V) - stos (głębokość) lub rekurencja

Implementacja DFS

Implementacja rekurencyjna

Implementacja iteracyjna

DFS krok po kroku - wizualizacja

Wyjście:

=== DFS krok po kroku ===

Krok 0: Start z wierzchołka A
  Stos: ['A']
  Odwiedzone: set()

Krok 1: Odwiedzam wierzchołek A
  Dodaję na stos: ['B', 'C']
  Stos: ['B', 'C']
  Odwiedzone: {'A'}

Krok 2: Odwiedzam wierzchołek C
  Dodaję na stos: ['F']
  Stos: ['B', 'F']
  Odwiedzone: {'A', 'C'}

Krok 3: Odwiedzam wierzchołek F
  Brak nowych sąsiadów
  Stos: ['B']
  Odwiedzone: {'A', 'C', 'F'}

Krok 4: Odwiedzam wierzchołek B
  Dodaję na stos: ['D', 'E']
  Stos: ['D', 'E']
  Odwiedzone: {'A', 'C', 'F', 'B'}

...

Zastosowania DFS

1. Wykrywanie cykli w grafie nieskierowanym

Wyjście:

Graf 1 ma cykl? False
Graf 2 ma cykl? True

2. Wykrywanie cykli w grafie skierowanym

Wyjście:

DAG ma cykl? False
Graf cykliczny ma cykl? True

3. Sortowanie topologiczne (Topological Sort)

Sortowanie topologiczne DAG-a to liniowe uporządkowanie wierzchołków takie, że dla każdej krawędzi (u, v), wierzchołek u pojawia się przed v.

Zastosowania: - Planowanie zadań z zależnościami - Kolejność kompilacji plików - Kolejność wykonywania instrukcji

Przykładowe wyjście:

Sortowanie topologiczne: ['B', 'D', 'A', 'C', 'E', 'H', 'F', 'G']

Weryfikacja (krawędzie):
  A → C: A przed C? True
  B → C: B przed C? True
  B → D: B przed D? True
  C → E: C przed E? True
  ...

4. Znajdowanie ścieżki w grafie

Uwaga: DFS nie gwarantuje najkrótszej ścieżki (w przeciwieństwie do BFS).

5. Sprawdzanie osiągalności

6. Silnie spójne składowe (Strongly Connected Components)

Składowa silnie spójna w grafie skierowanym to maksymalny podzbiór wierzchołków, gdzie każdy wierzchołek jest osiągalny z każdego innego.

Algorytm Kosaraju

Przykładowe wyjście:

Silnie spójne składowe (Kosaraju):
  SCC 1: {'A', 'B', 'E'}
  SCC 2: {'F', 'G'}
  SCC 3: {'C', 'D', 'H'}

Praktyczne zastosowanie: System zależności zadań

Wyjście:

=== System planowania zadań ===

Czy można wykonać wszystkie zadania? True

Kolejność wykonywania zadań:
  1. fundament
  2. sciany
  3. instalacja_wodna
  4. instalacja_elektryczna
  5. tynki
  6. podlogi
  7. malowanie

Wszystkie zależności 'malowanie': {'fundament', 'sciany', 'instalacja_elektryczna', 'instalacja_wodna', 'tynki'}

Porównanie DFS vs BFS - podsumowanie

Cecha DFS BFS
Struktura danych Stos (LIFO) lub rekurencja Kolejka (FIFO)
Kolejność W głąb (jedna gałąź do końca) Wszerz (warstwa po warstwie)
Najkrótsza ścieżka ❌ Nie ✅ Tak (nieważony)
Wykrywanie cykli ✅ Tak ⚠️ Możliwe, ale trudniejsze
Sortowanie topologiczne ✅ Tak ❌ Nie
Silnie spójne składowe ✅ Tak (Kosaraju, Tarjan) ❌ Nie
Pamięć O(h) gdzie h=głębokość O(w) gdzie w=szerokość
Implementacja Prostsza (rekurencja) Wymaga kolejki

Złożoność i optymalizacje

Złożoność

DFS dla grafu reprezentowanego jako lista sąsiedztwa: - Czas: O(V + E) - Każdy wierzchołek odwiedzany raz: O(V) - Każda krawędź przeglądana raz: O(E) - Pamięć: O(V) - Stos rekurencji lub jawny stos: O(V) w najgorszym przypadku

DFS dla grafu reprezentowanego jako macierz sąsiedztwa: - Czas: O(V²) - Dla każdego wierzchołka sprawdzamy wszystkie V wierzchołków - Pamięć: O(V)

Optymalizacje

Podsumowanie

Kluczowe cechy DFS

  • Stos (LIFO) lub rekurencja
  • Przeszukiwanie w głąb - wyczerpuje jedną gałąź przed przejściem do następnej
  • Złożoność O(V + E)
  • Wszechstronny - wiele zaawansowanych zastosowań

Kiedy używać DFS?

✅ Wykrywanie cykli ✅ Sortowanie topologiczne ✅ Silnie spójne składowe ✅ Backtracking (labirynty, puzzle) ✅ Przeszukiwanie drzewa decyzji

Co dalej?

Po opanowaniu DFS, następne kroki to:

  1. Lekcja 58: Algorytm Dijkstry
  2. Najkrótsza ścieżka w grafie ważonym
  3. Kolejka priorytetowa

  4. Optymalizacje (Fibonacci heap)

  5. Lekcja 59: Minimalne drzewo rozpinające

  6. Algorytm Prima
  7. Algorytm Kruskala

  8. Union-Find (Disjoint Set Union)

  9. Zaawansowane algorytmy grafowe:

  10. Algorytm Bellmana-Forda (ujemne wagi)
  11. Algorytm Floyda-Warshalla (wszystkie pary)
  12. Przepływy w sieciach (Ford-Fulkerson, Edmonds-Karp)

Zadania praktyczne

Zadanie 1: Wszystkie ścieżki

Zmodyfikuj DFS aby znalazł wszystkie ścieżki między dwoma wierzchołkami.

Zadanie 2: Mosty w grafie

Użyj DFS aby znaleźć mosty (krawędzie, których usunięcie zwiększa liczbę składowych spójnych).

Zadanie 3: Punkty artykulacji

Znajdź punkty artykulacji (wierzchołki, których usunięcie zwiększa liczbę składowych) używając DFS.

Zadanie 4: Labirynt

Zaimplementuj solver labiryntu używając DFS z backtrackingiem. Porównaj z BFS.

Następna lekcja: Algorytm Dijkstry - najkrótsza ścieżka w grafie ważonym

Wróć do spisu lekcji