Tiefensuche-Algorithmus (DFS) in Python

Einführung

Bei der Tiefensuche (DFS) werden alle Knoten entlang eines Zweigs erkundet und zurückverfolgt. Stellen Sie sich das wie ein Labyrinth vor: DFS geht einen Weg entlang, bis es eine Sackgasse erreicht, bevor es seine Schritte zurückverfolgt, um einen anderen zu nehmen, richtig? Es ist dasselbe wie nach unten zu gehen, den Tunnel zu validieren und so weiter für alle Tunnel.

DFS ist nützlich für:

• Besuchen Sie jeden Knoten in einem Diagramm.
• Überprüfen, wie verschiedene Knoten verbunden sind.

Während DFS tief eintaucht, prüft eine andere Methode namens Breadth-First Search (BFS) alle Nachbarn auf der aktuellen Ebene, bevor sie tiefer vordringt. Beide Methoden sind wichtig, aber Depth First Search (DFS) hilft Ihnen, einen Pfad so weit wie möglich zu verfolgen, bevor Sie einen anderen ausprobieren.

Der Überblick

• DFS besucht einen einzelnen Pfad vollständig, bevor es zu einem Knoten mit einem nicht besuchten Pfad zurückkehrt.
• DFS-Recursive verwendet einen Aufrufstapel zur Verwaltung der Durchquerung und dringt tiefer in jeden Pfad ein.
• Verwendet einen separaten Stapel, um die Erkundung aufrechtzuerhalten. Daher kein Downside mit der Rekursionstiefe.
• Die zeitliche Komplexität von DFS beträgt O(V+E)O(V + E)O(V+E) und die räumliche Komplexität beträgt O(V)O(V)O(V).
• DFS ist für viele Dinge cool. Einige der gängigsten sind Pfadfindung, Zyklenerkennung, topologische Sortierung und Rätsellösung.
• Unterschied zwischen DFS und BFS: BFS erkundet zuerst jede Ebene und geht dann zur nächsten Ebene über, während DFS einen Zweig durchläuft und dann zum aktuellen wechselt.

Wie funktioniert die Tiefensuche (DFS)?

Der DFS-Algorithmus beinhaltet das Besuchen von Knoten so weit wie möglich, bevor man zurückgeht. Hier ist eine schrittweise Erklärung:

1. Startknoten: Die Suche beginnt im Fall eines Baums beim Wurzelknoten und im Fall eines Graphen bei einem beliebigen Knoten.
2. Besuchen: Knoten als besucht markieren.
3. Erkunden: Besuchen Sie für jeden benachbarten Knoten rekursiv den Knoten, wenn dieser noch nicht besucht wurde.
4. Zurück zur Übersicht: Wenn ein Knoten ohne nicht besuchte benachbarte Knoten erreicht wird, gehen Sie zum vorherigen Knoten zurück und setzen Sie den Vorgang fort.

Lesen Sie auch: Ein vollständiges Python-Tutorial zum Erlernen von Knowledge Science von Grund auf

Tiefensuche (DFS)-Algorithmus

DFS – Depth First Search ist ein rekursiver Algorithmus. Um ihn für einen Graphen zu implementieren, können wir entweder Rekursion oder implizite Rekursion verwenden mit Stapel.

Rekursive Implementierung

Die rekursive Implementierung von DFS nutzt den Aufrufstapel, um den Durchlaufstatus zu verwalten. Hier ist ein Python Implementierung:

Code:

def dfs_recursive(graph, node, visited):

    if node not in visited:

        print(node, finish=' ')

        visited.add(node)

        for neighbour in graph(node):

            dfs_recursive(graph, neighbour, visited)

# Instance utilization:

graph = {

    'A': ('B', 'C', 'D'),

    'B': ('E'),

    'C': ('G', 'F'),

    'D': ('H'),

    'E': ('I'),

    'F': ('J'),

    'G': ('Ok')

}

visited = set()

print("DFS traversal utilizing recursive method:")

dfs_recursive(graph, 'A', visited)

Iterative Umsetzung

Die iterative Implementierung verwendet einen expliziten Stapel, um die Durchquerung zu verwalten. Dies kann nützlich sein, um potenzielle Probleme mit der Rekursionstiefe in Sprachen zu vermeiden, die die Größe des Aufrufstapels begrenzen.

Code:

def dfs_iterative(graph, begin):

    visited = set()

    stack = (begin)

    whereas stack:

        node = stack.pop()

        if node not in visited:

            print(node, finish=' ')

            visited.add(node)

            stack.prolong(reversed(graph(node)))  # Add in reverse order to keep up the order of traversal

# Instance utilization:

graph = {

    'A': ('B', 'C', 'D'),

    'B': ('E'),

    'C': ('G', 'F'),

    'D': ('H'),

    'E': ('I'),

    'F': ('J'),

    'G': ('Ok')

}

print("nDFS traversal utilizing iterative method:")

dfs_iterative(graph, 'A')

Erläuterung

Die Codebeispiele beziehen sich auf den Graphen als Adjazenzliste. Jeder Knoten ist wie ein Schlüssel, der alle direkt mit ihm verbundenen Knoten auflistet. Um zu vermeiden, dass derselbe Knoten erneut aufgerufen wird, haben wir ein Set namens „besucht“, das den vorherigen Knoten speichert.

• Rekursives DFS: Die Funktion dfs_recursive ruft sich selbst für jeden nicht besuchten Nachbarn des aktuellen Knotens auf und taucht tief in jeden Pfad ein.
• Iteratives DFS: Die Funktion dfs_iterative verwendet einen Stapel (eine Liste, in der Sie Elemente hinzufügen und entfernen), um zu verwalten, welche Knoten als nächstes besucht werden sollen. Dieser Stapel funktioniert wie der Aufrufstapel in der rekursiven Methode und hilft dabei, die Reihenfolge der Besuche zu verfolgen.

Beide Methoden stellen sicher, dass alle Teile des Diagramms untersucht werden, sie gehen dabei jedoch unterschiedlich vor.

Zeitliche und räumliche Komplexität

Hier ist die Zeit- und Platzkomplexität von DFS:

• Zeitliche Komplexität: Die zeitliche Komplexität von DFS ist O(V + E), wobei V und E die Anzahl der Knoten bzw. Kanten sind. Im schlimmsten Fall wird jeder Knoten und jede Kante einmal durchsucht.
• Raumkomplexität: Die Speicherkomplexität wäre O(V), da wir die besuchten Knoten verfolgen müssen. Bei der Rekursion würden wir einen Rekursionsstapel ausführen oder Knoten iterativ in den Stapel einfügen.

Anwendungen der Tiefensuche (DFS)

Tiefensuche (DFS) hat zahlreiche Anwendungen in der Informatik und bei realen Problemen:

• Wegfindung: DFS wäre nützlich, um einen Pfad zwischen zwei Knoten in einem Diagramm zu finden.
• Zykluserkennung: Es hilft beim Erkennen von Zyklen in einem Diagramm und ist in verschiedenen Bereichen nützlich, beispielsweise bei der Abhängigkeitsauflösung.
• Anwendungsfälle für topologische Sortierung: Planen Sie die Aufgaben so, dass jede Aufgabe von den anderen abhängt und in linearer Reihenfolge ausgeführt werden muss.
• Graphendurchquerung und verbundene Komponenten: DFS in einem ungerichteten Graphen, um alle verbundenen Komponenten zu identifizieren.
• Labyrinth- und Rätsellösung: Lösen Sie komplexe Labyrinthe und Rätsel, indem Sie jeden möglichen Weg durchqueren.

Beispiel aus der Praxis

Angenommen, Sie müssen alle Pfade in einem Computernetzwerk finden, damit die Daten korrekt übertragen werden. DFS ist ein Algorithmus, der eine Tiefensuche in einem Graphen durchführt. Damit können Sie von einem bestimmten Pc aus beginnen und Verbindungen bis zum Ende verfolgen. Wenn keine weiteren Verbindungen mehr verfolgt werden können, müssen Sie zurückgehen.

Code:

def find_paths(graph, begin, finish, path=()):

    path = path + (begin)

    if begin == finish:

        return (path)

    if begin not in graph:

        return ()

    paths = ()

    for node in graph(begin):

        if node not in path:

            new_paths = find_paths(graph, node, finish, path)

            for p in new_paths:

                paths.append(p)

    return paths

# Instance utilization:

community = {

    'Computer1': ('Computer2', 'Computer3'),

    'Computer2': ('Computer4'),

    'Computer3': ('Computer4', 'Computer5'),

    'Computer4': ('Computer6'),

    'Computer5': ('Computer6'),

    'Computer6': ()

}

begin="Computer1"

finish = 'Computer6'

print(f"All paths from {begin} to {finish}:")

paths = find_paths(community, begin, finish)

for path in paths:

    print(" -> ".be a part of(path))

DFS gegen BFS

Während DFS tief in einen Graphen eintaucht, untersucht BFS alle Nachbarn eines Knotens, bevor es zur nächsten Ebene übergeht. Beide haben ihre Vorteile:

• DFS: Verwendet weniger Speicher und kann einen Pfad finden, ohne alle Knoten zu erkunden.
• BFS: Garantiert das Finden des kürzesten Pfads in einem ungewichteten Graphen.

Abschluss

DFS (Depth-First Search) ist ein leistungsstarkes Dienstprogramm zum Durchlaufen von Graphen und deren Verwendung in Baumproblemen. DFS ist nützlich beim Lösen von Rätseln, beim Finden des Weges in einem Labyrinth oder beim Organisieren von Aufgaben. Es gibt zwei Möglichkeiten, DFS zu verwenden:

• Rekursives DFS: Hierbei werden Funktionsaufrufe verwendet, um zu verfolgen, woher Sie im Diagramm kommen.
• Iterative DFS: Verwenden eines Stapels zum Verarbeiten der Schritte.

Die beiden Methoden garantierten eine vollständige Abdeckung des Graphen; jeder Knoten wurde untersucht. Hier ist eine Liste, wie DFS Pfade finden, Zyklen erkennen, Aufgaben sortieren und Komponenten in einem Graphen verbinden kann. Wenn Sie sich Wissen über DFS aneignen, können Sie schwierige Probleme lösen. Nachdem Sie die Beispiele gesehen haben, können Sie DFS in Ihrem Code untersuchen.

Suchen Sie additionally nach Python-Kursen on-line? Wenn ja, erkunden Sie – Einführung in Python Heute!

Häufig gestellte Fragen