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 Implementierung

    Tiefensuche in Javascript

    Gepostet: , Zuletzt aktualisiert:

    JavaScript JavaScript ist eine interpretierte Skriptsprache, die zuvor hauptsächlich in Webseiten verwendet wurde (die in Browsern…

    Zur Implementierung

    Tiefensuche 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 Implementierung

    Tiefensuche 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 Implementierung

    Tiefensuche 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:

  1. Für jedes Kind des aktuellen Knotens
  2. Wenn es sich um den Zielknoten handelt, kehren Sie zurück. Der Knoten wurde gefunden.
  3. Setzen Sie den aktuellen Knoten auf diesen Knoten und kehren Sie zu 1 zurück.
  4. Wenn keine untergeordneten Knoten mehr zu besuchen sind, kehren Sie zum übergeordneten Knoten zurück.
  5. 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: Baum für den Tiefensuchalgorithmus

Die Schritte, die der Algorithmus für diesen Baum ausführt, wenn der Knoten 0 als Startpunkt angegeben wird, sind:

  1. Besuche Knoten 0
  2. Besuche Knoten 1
  3. Besuche Knoten 3
  4. Ging durch alle Kinder von 3 Jahren und kehrte zu seinen Eltern zurück.
  5. Besuche Knoten 4
  6. Ging durch alle Kinder von 4 Jahren und kehrte zu seinen Eltern zurück.
  7. Ging durch alle Kinder von 1 und kehrte zu seinem Elternteil zurück.
  8. Besuche Knoten 2
  9. Besuche Knoten 5
  10. Ging durch alle Kinder von 5 Jahren und kehrte zu seinen Eltern zurück.
  11. Besuche Knoten 6
  12. 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.