Przeszukiwanie grafu w głąb, znane również jako DFS (Depth-First Search), jest jednym z podstawowych i najbardziej powszechnych algorytmów grafowych. W przeciwieństwie do BFS, które eksploruje wszystkie węzły na danym poziomie przed przejściem do następnego, DFS zagłębia się w grafie, podążając wzdłuż ścieżki aż do osiągnięcia węzła bez nieodwiedzonych sąsiadów, a następnie wraca i kontynuuje poszukiwania z następnego węzła. DFS jest niezwykle przydatny w wielu zastosowaniach, takich jak wykrywanie cykli w grafach, znajdowanie składowych silnie spójnych czy rozwiązywanie problemów związanych z przeszukiwaniem drzew decyzyjnych. Jego prostota i efektywność sprawiają, że jest jednym z kluczowych algorytmów, które każdy programista powinien znać.

Podstawy działania DFS

DFS eksploruje graf, wybierając ścieżkę i podążając wzdłuż niej tak daleko, jak to możliwe, zanim cofnie się i spróbuje innej ścieżki. Można to porównać do eksploracji labiryntu, gdzie podążamy za jednym korytarzem aż do końca, a jeśli napotkamy ślepą uliczkę, wracamy i wybieramy inny korytarz. DFS można zaimplementować zarówno w wersji rekurencyjnej, jak i iteracyjnej. W wersji iteracyjnej DFS korzysta ze stosu, co odzwierciedla rekurencyjny charakter algorytmu.

Struktury danych używane w DFS

Podczas implementacji DFS używamy kilku podstawowych struktur danych:

• Stos: DFS jest algorytmem opartym na stosie. W wersji rekurencyjnej stos jest realizowany przez stos wywołań funkcji rekurencyjnych. W wersji iteracyjnej możemy użyć jawnego stosu, aby przechowywać węzły do odwiedzenia.
• Tablica odwiedzin: Tablica odwiedzin służy do śledzenia, które węzły zostały już odwiedzone, co zapobiega wielokrotnemu przetwarzaniu tych samych węzłów i unikaniu nieskończonych pętli w przypadku grafów cyklicznych.
• Graf: Graf jest zazwyczaj reprezentowany za pomocą listy sąsiedztwa lub macierzy sąsiedztwa, w zależności od preferencji i wymagań dotyczących pamięci oraz wydajności.

Przebieg algorytmu DFS

Przebieg algorytmu DFS można podzielić na następujące kroki:

1. Rozpocznij przeszukiwanie od węzła początkowego i oznacz go jako odwiedzony.
2. Dla każdego sąsiada węzła początkowego:
   • Jeśli sąsiad nie został jeszcze odwiedzony, przejdź do tego sąsiada i kontynuuj przeszukiwanie.
3. Gdy wszystkie sąsiednie węzły zostaną odwiedzone, cofnij się do poprzedniego węzła i sprawdź, czy są inne nieodwiedzone sąsiady. Jeśli nie, kontynuuj cofanie się, aż wszystkie węzły zostaną odwiedzone.

Implementacja DFS

Oto przykładowa implementacja algorytmu DFS w języku C++ z użyciem listy sąsiedztwa:

Rekurencyjna implementacja DFS

#include <iostream>
#include <vector>

class Graph {
private:
    int V;
    std::vector<std::vector<int>> adjList;
    void dfsUtil(int v, std::vector<bool>& visited) {
        visited[v] = true;
        std::cout << "Odwiedzony węzeł: " << v << std::endl;

        for (int neighbor : adjList[v]) {
            if (!visited[neighbor]) {
                dfsUtil(neighbor, visited);
            }
        }
    }
public:
    Graph(int V) : V(V) {
        adjList.resize(V);
    }

    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        adjList[v].push_back(u); // Usuń tę linię dla grafu skierowanego
    }

    void dfs(int start) {
        std::vector<bool> visited(V, false);
        dfsUtil(start, visited);
    }
};

int main() {
    Graph graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(0, 4);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);

    std::cout << "Przeszukiwanie grafu w głąb zaczynając od węzła 0:" << std::endl;
    graph.dfs(0);

    return 0;
}

Iteracyjna implementacja DFS

Iteracyjna implementacja DFS korzysta ze stosu, aby śledzić węzły do odwiedzenia:

#include <iostream>
#include <vector>
#include <stack>

class Graph {
private:
    int V;
    std::vector<std::vector<int>> adjList;
public:
    Graph(int V) : V(V) {
        adjList.resize(V);
    }

    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        adjList[v].push_back(u); // Usuń tę linię dla grafu skierowanego
    }

    void dfs(int start) {
        std::vector<bool> visited(V, false);
        std::stack<int> stack;
        stack.push(start);

        while (!stack.empty()) {
            int node = stack.top();
            stack.pop();

            if (!visited[node]) {
                visited[node] = true;
                std::cout << "Odwiedzony węzeł: " << node << std::endl;
            }

            for (auto it = adjList[node].rbegin(); it != adjList[node].rend(); ++it) {
                if (!visited[*it]) {
                    stack.push(*it);
                }
            }
        }
    }
};

int main() {
    Graph graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(0, 4);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);

    std::cout << "Przeszukiwanie grafu w głąb (iteracyjnie) zaczynając od węzła 0:" << std::endl;
    graph.dfs(0);

    return 0;
}

Zastosowania DFS

DFS znajduje zastosowanie w wielu problemach grafowych, takich jak:

1. Wykrywanie cykli w grafie

DFS może być używany do wykrywania cykli w grafach. W przypadku grafu skierowanego można łatwo zidentyfikować cykl, sprawdzając, czy odwiedzamy węzeł, który znajduje się już na stosie wywołań. W grafach nieskierowanych wykrywanie cykli polega na sprawdzaniu, czy istnieje krawędź do już odwiedzonego węzła, który nie jest rodzicem bieżącego węzła.

2. Znajdowanie składowych silnie spójnych

Składowe silnie spójne to podgrafy, w których każdy węzeł jest osiągalny z każdego innego węzła. Algorytmy takie jak algorytm Tarjana czy Kosaraju wykorzystują DFS do identyfikowania tych składowych w grafach skierowanych.

3. Generowanie drzew rozpinających

DFS może być używany do generowania drzew rozpinających w grafach, co jest przydatne w algorytmach minimalnego drzewa rozpinającego oraz w analizie struktury grafu.

4. Rozwiązywanie problemów labiryntowych

DFS jest często używany do rozwiązywania problemów labiryntowych i znajdowania ścieżek w grach, gdzie ważne jest zagłębienie się w jedną ścieżkę aż do jej końca przed sprawdzeniem innych możliwości.

Złożoność czasowa i przestrzenna DFS

Złożoność czasowa DFS wynosi O(V + E), gdzie V to liczba węzłów, a E to liczba krawędzi, ponieważ każdy węzeł i każda krawędź są przetwarzane dokładnie raz. Złożoność przestrzenna zależy od implementacji: w wersji rekurencyjnej stos wywołań może mieć maksymalną głębokość równą liczbie węzłów, co może prowadzić do problemów z przepełnieniem stosu w przypadku bardzo głębokich grafów. W wersji iteracyjnej musimy przechowywać węzły na jawnie zdefiniowanym stosie.

Ograniczenia i wyzwania DFS

DFS ma swoje ograniczenia, szczególnie w przypadku grafów o dużej średnicy lub w przypadku głębokich drzew, gdzie rekurencyjna implementacja może prowadzić do przepełnienia stosu. W takich sytuacjach wersja iteracyjna DFS jest preferowana. DFS nie jest również optymalnym rozwiązaniem dla problemów, które wymagają znalezienia najkrótszej ścieżki, ponieważ algorytm ten eksploruje ścieżki w sposób „zachłanny”, co może prowadzić do nieefektywnych rozwiązań w grafach z wieloma ścieżkami.

Podsumowanie

Przeszukiwanie grafu w głąb (DFS) to potężny i elastyczny algorytm, który jest szeroko stosowany w analizie grafów i rozwiązywaniu złożonych problemów. Jego rekurencyjny charakter i zdolność do eksploracji grafów w sposób głęboki sprawiają, że jest nieocenionym narzędziem w arsenale każdego programisty. Zrozumienie, jak działa DFS, oraz jego zastosowania w różnych scenariuszach, od wykrywania cykli po znajdowanie składowych spójnych, to kluczowy krok w nauce algorytmów grafowych i optymalizacji procesów przetwarzania danych.

Następny temat ==> Algorytm Floyda-Warshalla