Algorytmy przeszukiwania wgłąb (DFS)

7.1 Zasady działania algorytmu DFS

Przeszukiwanie wgłąb (Depth-First Search, DFS) — to algorytm przeszukiwania grafu. Startuje z początkowego wierzchołka i idzie wgłąb grafu, aż osiągnie wierzchołek bez nieodwiedzonych sąsiadów, potem cofa się i kontynuuje proces z innymi wierzchołkami.

Kroki algorytmu:

1. Zaczynamy od wybranego początkowego wierzchołka i oznaczamy go jako odwiedzony.
2. Badamy pierwszego nieodwiedzonego sąsiada wierzchołka.
3. Powtarzamy kroki 1 i 2 dla tego sąsiada.
4. Jeśli wszyscy sąsiedzi bieżącego wierzchołka są odwiedzeni, wracamy do poprzedniego wierzchołka i kontynuujemy proces.
5. Proces powtarzamy, aż wszystkie wierzchołki dostępne z początkowego wierzchołka będą odwiedzone.

Wizualizacja:

Złożoność czasowa i przestrzenna DFS:

Złożoność czasowa:

O(V + E), gdzie V — liczba wierzchołków, E — liczba krawędzi.

Każdy węzeł i każda krawędź w grafie są odwiedzane raz.

Złożoność przestrzenna:

O(V), ponieważ stos wywołań lub jawny stos służy do przechowywania wierzchołków, a także tablice do przechowywania stanu (odwiedzone wierzchołki).

7.2 Implementacja DFS z użyciem rekurencji

Zacznijmy od implementacji DFS z wykorzystaniem rekurencji — kod będzie piękny i zwarty.

Rekurencyjna implementacja DFS:

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # Przetwarzanie węzła
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
# Przykład użycia:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_recursive(graph, 'A')

7.3 Implementacja DFS z użyciem stosu

Bez rekurencji kod będzie trochę dłuższy, ponieważ musimy dodatkowo przechowywać listę odwiedzonych wierzchołków.

Iteracyjna implementacja DFS (z użyciem stosu):

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
        
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Przetwarzanie węzła
        
            for neighbor in reversed(graph[vertex]):  # Odwrotny porządek dla poprawnej kolejności przeszukiwania
                if neighbor not in visited:
                    stack.append(neighbor)
        
# Przykład użycia:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_iterative(graph, 'A')

7.4 Przykłady zadań rozwiązywanych za pomocą DFS

Klasyczne przykłady zadań rozwiązywanych za pomocą DFS:

1. Znajdowanie ścieżki w labiryncie:

Wykorzystuje się do znalezienia ścieżki w labiryncie od punktu startowego do końcowego.

Zastosowanie:

W grach komputerowych i robotyce do nawigacji po labiryntach i złożonych przestrzeniach.

2. Sprawdzanie spójności grafu:

Sprawdzanie, czy graf jest spójny (czy istnieje ścieżka między dowolnymi dwoma wierzchołkami).

Zastosowanie:

W analizie sieci do sprawdzania spójności sieci.

3. Sortowanie topologiczne:

Używane do uporządkowania wierzchołków w skierowanym acyklicznym grafie (DAG) w taki sposób, że dla każdej krawędzi (u, v) wierzchołek u poprzedza wierzchołek v.

Zastosowanie:

W kompilatorach do uporządkowywania zależności i zadań.

4. Wykrywanie cykli w grafie:

Sprawdzanie, czy graf zawiera cykle.

Zastosowanie:

W analizie zależności do wykrywania cyklicznych zależności.

5. Generowanie labiryntów:

Wykorzystanie DFS do generowania losowych labiryntów.

Zastosowanie:

W aplikacjach rozrywkowych do tworzenia labiryntów.