Tiefensuche-Algorithmen (DFS)

7.1 Funktionsweise des DFS-Algorithmus

Tiefensuche (Depth-First Search, DFS) ist ein Algorithmus zur Durchquerung oder Suche in einem Graphen. Er beginnt bei einem Startknoten und geht in die Tiefe, bis er einen Knoten ohne unbesuchte Nachbarn erreicht, dann geht er zurück und setzt den Prozess mit anderen Knoten fort.

Schritte des Algorithmus:

1. Starte beim gewählten Startknoten und markiere ihn als besucht.
2. Untersuche den ersten unbesuchten Nachbarknoten.
3. Wiederhole Schritte 1 und 2 für diesen Nachbarknoten.
4. Wenn alle Nachbarn des aktuellen Knotens besucht sind, gehe zurück (backtrack) zum vorherigen Knoten und setze den Prozess fort.
5. Der Prozess wird fortgesetzt, bis alle Knoten besucht sind, die vom Startknoten aus erreichbar sind.

Visualisierung:

Zeit- und Speicherkomplexität von DFS:

Zeitkomplexität:

O(V + E), wobei V die Anzahl der Knoten ist und E die Anzahl der Kanten.

Jeder Knoten und jede Kante im Graphen wird einmal besucht.

Speicherkomplexität:

O(V), da ein Aufrufstapel oder ein expliziter Stapel zur Speicherung von Knoten verwendet wird, sowie Arrays zur Speicherung des Zustands (besuchte Knoten).

7.2 Umsetzung von DFS mit Rekursion

Lass uns zunächst DFS mit Rekursion umsetzen – der Code wird schön und kompakt sein.

Rekursive Umsetzung von DFS:

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # Verarbeitung des Knotens
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
# Beispiel der Verwendung:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_recursive(graph, 'A')

7.3 Umsetzung von DFS mit einem Stack

Ohne Rekursion wird der Code etwas länger, da wir zusätzlich eine Liste der besuchten Knoten speichern müssen.

Iterative Umsetzung von DFS (mit einem Stack):

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
        
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Verarbeitung des Knotens
        
            for neighbor in reversed(graph[vertex]):  # Rückwärtsordnung für die richtige Durchlaufreihenfolge
                if neighbor not in visited:
                    stack.append(neighbor)
        
# Beispiel der Verwendung:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_iterative(graph, 'A')

7.4 Beispielaufgaben, die mit DFS gelöst werden

Klassische Beispielaufgaben für DFS:

1. Pfadsuche im Labyrinth:

Wird verwendet, um einen Pfad im Labyrinth von einem Start- zu einem Endpunkt zu finden.

Anwendung:

In Videospielen und Robotik zur Navigation durch Labyrinthe und komplexe Räume.

2. Überprüfung der Graph-Verbindung:

Überprüfung, ob der Graph verbunden ist (ob es einen Pfad zwischen beliebigen zwei Knoten gibt).

Anwendung:

In der Netzwerk-Analyse zur Überprüfung der Netzwerkverbindung.

3. Topologische Sortierung:

Wird verwendet, um die Knoten eines gerichteten azyklischen Graphen (DAG) so anzuordnen, dass für jede Kante (u, v) der Knoten u vor dem Knoten v kommt.

Anwendung:

In Compilern zur Anordnung von Abhängigkeiten und Aufgaben.

4. Zyklen-Erkennung im Graphen:

Überprüfung, ob der Graph Zyklen enthält.

Anwendung:

In der Abhängigkeitsanalyse zur Erkennung von zyklischen Abhängigkeiten.

5. Labyrinth-Generierung:

Anwendung von DFS zur Generierung zufälliger Labyrinthe.

Anwendung:

In Spielen und Unterhaltungsanwendungen zur Erstellung von Labyrinthen.