DFS (Depth First Traversal) in der Datenstruktur: Was ist, Bestellung und Anwendungen

Bedeutung von DFS in der Datenstruktur

DFS in der Datenstruktur, auch bekannt als Tiefendurchlauf, ist ein rekursiver Algorithmus, der hauptsächlich zum Durchsuchen aller Scheitelpunkte eines Diagramms oder einer Baumdatenstruktur verwendet wird. Traversal ist das Besuchen jedes Knotens eines Graphen. Der Algorithmus beginnt am Wurzelknoten (der ein beliebiger Knoten als Wurzelknoten in einem Diagramm sein kann) und geht so weit wie möglich entlang jeder Verzweigung, bevor er zurückverfolgt wird.

Die Idee ist, von der Wurzel oder einem beliebigen Knoten aus zu beginnen und den Knoten markiert zu lassen. Danach müssen Sie zu dem angrenzenden Knoten gehen, der nicht markiert ist, und diese Schleife fortsetzen, bis es keinen unmarkierten angrenzenden Knoten gibt. Gehen Sie dann zurück und untersuchen Sie die anderen Knoten, die nicht markiert sind, und durchqueren Sie sie. Der letzte Schritt besteht darin, die Knoten innerhalb des Pfads zu drucken.

Algorithmus

Formulieren Sie eine rekursive Funktion, die den Index des Knotens und ein besuchtes Array verwendet.

1. Lassen Sie den aktuellen Knoten als besucht markiert und drucken Sie ihn dann aus.
2. Durchlaufen Sie alle angrenzenden und nicht markierten Noten und rufen Sie die rekursive Funktion mit dem Index des angrenzenden Knotens auf.

Erkunden Sie unsere beliebten Softwareentwicklungskurse

Eigenschaften

Die Analyse von Zeit und Raum in der DFS in Datenstruktur variiert je nach Anwendungsbereich. Theoretisch wird DFS hauptsächlich verwendet, um einen vollständigen Graphen zu kreuzen, und benötigt Zeit O(|V|+|E|), wobei |V| zeigt die Anzahl der Scheitelpunkte und |E| gibt die Anzahl der Kanten an. Dieser Graph ist linear.

In diesen Anwendungen wird der Raum O(|V|) auch als letzter Ausweg verwendet, um den Stapel von Scheitelpunkten, die auf dem Suchpfad gespeichert sind, und den Satz von bereits besuchten Scheitelpunkten zu halten. Daher ähneln die Zeit- und Raumbegrenzungseinstellungen der Breitensuche. Dabei sind die beiden verwendeten Algorithmen weniger abhängig von ihrer Komplexität als vielmehr von den unterschiedlichen Eigenschaften der von den beiden Algorithmen erzeugten Scheitelpunktordnungen.

Wenn es um Anwendungen von DFS in der Datenstruktur geht, die sich auf bestimmte Domänen beziehen, wie das Finden von Lösungen beim Web-Crawling oder KI, ist der Graph, der durchlaufen werden muss, möglicherweise zu umfangreich, um ihn vollständig zu besuchen. In solchen Fällen wird die Suche nur bis zu einer eingeschränkten Tiefe durchgeführt; aufgrund begrenzter Ressourcen wie Speicherplatz oder Arbeitsspeicher. Datenstrukturen werden normalerweise nicht verwendet, um die Menge aller zuvor besuchten Scheitelpunkte zu verfolgen. Eine Suche, die bis zu einer begrenzten Tiefe durchgeführt wird, macht die Zeit immer noch linear, wenn es um die Einheit von erweiterten Kanten und Scheitelpunkten geht.

Denken Sie jedoch daran, dass diese Zahl nicht die gleiche Größe wie der gesamte Graph hat, da einige der Scheitelpunkte möglicherweise mehrmals gesucht werden und andere nicht.

In solchen Fällen greift die DFS auch auf heuristische Methoden zurück, um einen vielversprechenderen Zweig auszuwählen. Wenn schließlich die geeignete Tiefengrenze nicht bestimmt werden kann, wird a priori eine iterative Vertiefungs-DFS wiederholt über eine Folge von wachsenden Grenzen angewendet.

Lernen Sie Softwareentwicklungskurse online von den besten Universitäten der Welt. Verdienen Sie Executive PG-Programme, Advanced Certificate-Programme oder Master-Programme, um Ihre Karriere zu beschleunigen.

Tiefensuchalgorithmus

Jeder Scheitelpunkt eines Graphen in einer Standard-DFS-Implementierung ist in eine von zwei Kategorien unterteilt:

1. Nicht besucht
2. hat besucht

Der Algorithmus wird verwendet, um jeden Scheitelpunkt zu lokalisieren und als besucht zu markieren und gleichzeitig Zyklen zu vermeiden.

So funktioniert der DFS-Algorithmus:

1. Lege einen beliebigen Scheitelpunkt des Graphen auf einen Stapel.
2. Das Element ganz oben auf dem Stapel sollte der besuchten Liste hinzugefügt werden.
3. Erstellen Sie eine Liste benachbarter Knoten dieses Knotens und fügen Sie diejenigen hinzu, die nicht in der besuchten Liste oben auf dem Stapel enthalten sind.
4. Wiederholen Sie die vorherigen Schritte, bis der Stapel leer ist.

DFS-Bestellung

Scheitelreihenfolgen: Es gibt vier Möglichkeiten, die Scheitelpunkte eines Graphen oder Baums in DFS linear anzuordnen:

1. Die Liste der Scheitelpunkte, die so angeordnet sind, wie sie zuerst vom DFS-Algorithmus besucht wurden, wird als Vorbestellung bezeichnet. Es ist eine prägnante Art, den Fortschritt der Suche zu beschreiben.
2. Die Liste der Scheitelpunkte in der Reihenfolge, in der sie zuletzt vom Algorithmus besucht wurden, wird als Nachbestellung bezeichnet.
3. Die Liste der Scheitelpunkte in der Reihenfolge, die ihrem ersten Besuch entgegengesetzt ist, ist eine umgekehrte Vorordnung. Daher sollte es nicht mit der Nachbestellung verwechselt werden.
4. Die Liste der Scheitelpunkte in der Reihenfolge, die ihrem letzten Besuch entgegengesetzt ist, ist eine umgekehrte Nachordnung. Es sollte nicht mit einer Vorbestellung verwechselt werden.

Zusätzlich gibt es eine In-Ordering und Reverse In-Ordering für binäre Bäume.

Tiefensuche oder DFS für ein Diagramm

Die DFS für einen Graphen ist fast dieselbe wie die DFS für einen Baum. Der einzige Unterschied besteht darin, dass die Graphen im Gegensatz zu Bäumen Zyklen haben können. Ein Knoten kann mehrmals besucht werden, und um die Verarbeitung des Knotens zu vermeiden, wird ein boolesches besuchtes Array verwendet.

Ausgabe einer Tiefensuche

Die Tiefensuche lässt sich einfacher als aufspannender Baum der bei der Suche bereits erreichten Scheitelpunkte darstellen. Basierend auf diesem aufspannenden Baum werden die ursprünglichen Graphkanten in drei Klassen eingeteilt: die Vorwärtskanten, wo der Knoten des Baums auf einen seiner Nachkommen zeigt, die Hinterkanten, wo der Knoten auf einen seiner Vorfahren zeigt, und Kreuzkanten , die keine der vorherigen Funktionen ausführt.

Anwendungen von Depth First Traversal (DFS)

Die Tiefensuche wird in den folgenden Algorithmen als Baustein verwendet:

• Suche nach angeschlossenen Komponenten.
• Finden von 2-(Eckpunkt oder Kante)-verbundenen Komponenten.
• Die Brücken des Graphen finden.
• Finden von 3-(Scheitel oder Kante)-verbundenen Komponenten.
• Topologische Sortierung.
• Komponenten finden, die stark verbunden sind.
• Herausfinden, ob eine Art der einen oder anderen Art in einem Stammbaum ähnlich ist.
• Ebenheitsprüfung.
• Produzieren von Wörtern, um den Grenzsatz einer beliebigen Gruppe zu bestimmen.
• Rätsel lösen, die nur eine Lösung haben, wie Labyrinthe.
• Labyrinth- Generation .
• Suche nach Bi-Konnektivität in Graphen.

DFS-Pseudocode und Implementierung in Python

Die Funktion init() wird auf jedem Knoten im Pseudocode unten ausgeführt, um sicherzustellen, dass alle Scheitelpunkte besucht werden. Dies ist besonders wichtig, da Diagramme verschiedene nicht verbundene Bereiche haben können.

Hier ist der Pseudocode:

DFS(G, u)

u.besucht = wahr

für jedes v ∈ G.Adj[u]

if v.besucht == falsch

DFS(G,v)

drin() {

Für jedes u ∈ G

u.besucht = falsch

Für jedes u ∈ G

DFS(G,u)

}

Hier ist die DFS-Implementierung in Python:

Grafik = {

'5' : ['3','7'],

'2' : ['1', '3'],

'6' : ['7'],

'3' : [],

'4' : ['6'],

'7' : []

}

besucht = gesetzt()

def dfs(besucht, Graph, Knoten):

wenn Knoten nicht besucht:

Drucken (Knoten)

besucht.add (Knoten)

für Nachbar in graph[Knoten]:

dfs(besucht, Graph, Nachbar)

print("Das ist das DFS:")

dfs(besucht, graph, '5')

Ausgabe:

Das ist die DFS: 5

Erkunden Sie unsere beliebten Softwareentwicklungskurse

Die Komplexität der Tiefensuche

John Reif untersuchte die rechnerische Komplexität der Tiefensuche. Genauer gesagt, in einem Graphen ist die gegebene Tatsache G, sei O die Standardordnung, die durch den repetitiven DFS-Algorithmus bestimmt wird. G repräsentiert den Graphen und O repräsentiert die ordnende Ausgabe des redundanten DFS-Algorithmus. Diese Ausgabe wird als lexikografische DFS-Ordnung bezeichnet.

Fazit

Das Hauptziel des DFS-Algorithmus besteht darin, jeden einzelnen Scheitelpunkt zu besuchen, der Zyklen in Zielgraphen vermeidet. Wenn Sie sich mit fortgeschrittenen Implementierungen von Suchvorgängen oder Bestellvorgängen befassen möchten, sollten Sie unbedingt einen erstklassigen und ganzheitlichen Kurs in Tiefensuche und Datenstruktur belegen.

upGrad bietet einige erstklassige DFS-Kurse wie Master of Science in Computer Science und Specialization in Big Data an .

Wenn Sie Schwierigkeiten haben, Ihren nächsten Schritt zu tun, und nach Expertenrat suchen, versucht upGrad Mentorship , Ihnen Einzelsitzungen mit den besten Karriereberatern und Experten der Branche anzubieten.