Tiefensuche in allen Programmiersprachen
Tiefensuche in Java
Gepostet: , Zuletzt aktualisiert:
Java ™ ist eine kompilierte Sprache, die für viele Zwecke verwendet wird, von eingebetteten Systemen über UI-Anwendungen bis hin zu Webservern.
Zur ImplementierungTiefensuche in Javascript
Gepostet: , Zuletzt aktualisiert:
JavaScript JavaScript ist eine interpretierte Skriptsprache, die zuvor hauptsächlich in Webseiten verwendet wurde (die in Browsern…
Zur ImplementierungTiefensuche in Python
Gepostet: , Zuletzt aktualisiert:
Python Python™ ist eine interpretierte Sprache, die für viele Zwecke verwendet wird, von der eingebetteten Programmierung bis zur Webentwicklung, wobei einer der größten Anwendungsfälle die Datenwissenschaft ist.
Zur ImplementierungTiefensuche in C
Gepostet: , Zuletzt aktualisiert:
C ist eine kompilierte Sprache, die für viele Zwecke verwendet wird, obwohl sie hauptsächlich in Systemen zu finden ist, in denen Wichtigkeit wichtig ist. Dies liegt daran, dass C viel Unterstützung auf niedriger Ebene für die Optimierung bietet, auf Kosten der Tatsache, dass einige der praktischen Abstraktionen, die andere Sprachen bieten, nicht vorhanden sind. C tritt daher hauptsächlich in Situationen auf, in denen die verfügbare Rechenleistung gering ist, wie beispielsweise eingebettete Systeme, oder in Situationen, in denen die erforderliche Rechenleistung hoch ist, wie z. B. Simulation oder Deep Learning.
Zur ImplementierungTiefensuche in R
Gepostet: , Zuletzt aktualisiert:
R R ist eine interpretierte Sprache, die erstmals 1993 veröffentlicht wurde und in den letzten Jahren erheblich an Popularität gewonnen hat…
Zur ImplementierungÜber den Algorithmus und die Programmiersprache in diesem Snippet:
Tiefensuche Algorithmus
Der Tiefensuche-Algorithmus (Depth-First Search, DFS) ist ein Algorithmus, mit dem ein Knoten in einem Baum gefunden wird. Dies bedeutet, dass der Algorithmus bei einer gegebenen Baumdatenstruktur den ersten Knoten in diesem Baum zurückgibt, der der angegebenen Bedingung entspricht (d. H. Gleich einem Wert ist). Die Kanten müssen ungewichtet sein. Dieser Algorithmus kann auch mit ungewichteten Diagrammen arbeiten, wenn ein Mechanismus zum Verfolgen bereits besuchter Knoten hinzugefügt wird.
Beschreibung des Algorithmus
Das Grundprinzip des Algorithmus besteht darin, mit einem Startknoten zu beginnen und dann das erste untergeordnete Element dieses Knotens zu betrachten. Anschließend wird das erste untergeordnete Element dieses Knotens (Enkel des Startknotens) usw. angezeigt, bis ein Knoten keine untergeordneten Elemente mehr hat (wir haben einen Blattknoten erreicht). Es geht dann eine Ebene höher und schaut auf das nächste Kind. Wenn keine Kinder mehr vorhanden sind, wird eine weitere Ebene erhöht, bis weitere Kinder gefunden werden oder der Startknoten erreicht wird. Wenn der Zielknoten nach der Rückkehr vom letzten untergeordneten Element des Startknotens nicht gefunden wurde, kann der Zielknoten nicht gefunden werden, da bis dahin alle Knoten durchlaufen wurden.
Im Einzelnen sind dies die folgenden Schritte:
- Für jedes Kind des aktuellen Knotens
- Wenn es sich um den Zielknoten handelt, kehren Sie zurück. Der Knoten wurde gefunden.
- Setzen Sie den aktuellen Knoten auf diesen Knoten und kehren Sie zu 1 zurück.
- Wenn keine untergeordneten Knoten mehr zu besuchen sind, kehren Sie zum übergeordneten Knoten zurück.
- Wenn der Knoten kein übergeordnetes Element hat (d. H. Es ist die Wurzel), kehren Sie zurück. Der Knoten wurde nicht gefunden.
Beispiel des Algorithmus
Betrachten Sie den folgenden Baum:
Die Schritte, die der Algorithmus für diesen Baum ausführt, wenn der Knoten 0 als Startpunkt angegeben wird, sind:
- Besuche Knoten 0
- Besuche Knoten 1
- Besuche Knoten 3
- Ging durch alle Kinder von 3 Jahren und kehrte zu seinen Eltern zurück.
- Besuche Knoten 4
- Ging durch alle Kinder von 4 Jahren und kehrte zu seinen Eltern zurück.
- Ging durch alle Kinder von 1 und kehrte zu seinem Elternteil zurück.
- Besuche Knoten 2
- Besuche Knoten 5
- Ging durch alle Kinder von 5 Jahren und kehrte zu seinen Eltern zurück.
- Besuche Knoten 6
- Den Knoten gefunden, den wir suchen!
Laufzeit des Algorithmus
Die Laufzeit der regulären Tiefensuche (DFS) beträgt O(|N|) (|N| = Anzahl der Knoten im Baum), da jeder Knoten höchstens einmal durchlaufen wird. Die Anzahl der Knoten ist gleich b^d, wobei b der Verzweigungsfaktor und d die Tiefe ist, sodass die Laufzeit als O(b^d) umgeschrieben werden kann.
Speicherkomplexität des Algorithmus
Die Speicherkomplexität der Tiefensuche (Depth-First Search, DFS) ist, wenn wir den Baum selbst ausschließen, O(d), wobei d die Tiefe ist, die auch die Größe des Aufrufstapels bei maximaler Tiefe ist. Wenn wir den Baum einschließen, entspricht die Speicherplatzkomplexität der Laufzeitkomplexität, da jeder Knoten gespeichert werden muss.