Tiefensuche



Alles Wissen, das die Menschen im Laufe der Jahrhunderte über Tiefensuche angesammelt haben, ist jetzt im Internet verfügbar, und wir haben es für Sie auf möglichst zugängliche Weise zusammengestellt und geordnet. Wir möchten, dass Sie schnell und effizient auf alles zugreifen können, was Sie über Tiefensuche wissen möchten, dass Ihre Erfahrung angenehm ist und dass Sie das Gefühl haben, wirklich die Informationen über Tiefensuche gefunden zu haben, nach denen Sie gesucht haben.

Um unsere Ziele zu erreichen, haben wir uns nicht nur bemüht, die aktuellsten, verständlichsten und wahrheitsgetreuesten Informationen über Tiefensuche zu erhalten, sondern wir haben auch dafür gesorgt, dass das Design, die Lesbarkeit, die Ladegeschwindigkeit und die Benutzerfreundlichkeit der Seite so angenehm wie möglich sind, damit Sie sich auf das Wesentliche konzentrieren können, nämlich alle verfügbaren Daten und Informationen über Tiefensuche zu kennen, ohne sich um irgendetwas anderes kümmern zu müssen, das haben wir bereits für Sie erledigt. Wir hoffen, dass wir unser Ziel erreicht haben und dass Sie die gewünschten Informationen über Tiefensuche gefunden haben. Wir heißen Sie also willkommen und ermutigen Sie, die Erfahrung der Nutzung von scientiade.com weiterhin zu genießen.

Tiefensuche
Reihenfolge, in der die Knoten erweitert werden
Reihenfolge, in der die Knoten besucht werden
Klasse Suchalgorithmus
Datenstruktur Graph
Worst-Case- Leistung für explizite Graphen ohne Wiederholung durchlaufen, für implizite Graphen mit Verzweigungsfaktor b bis zur Tiefe d . gesucht
Raumkomplexität im schlimmsten Fall wenn der gesamte Graph ohne Wiederholung durchlaufen wird, O(längste gesuchte Pfadlänge) = für implizite Graphen ohne Eliminierung doppelter Knoten

Die Tiefensuche ( DFS ) ist ein Algorithmus zum Durchlaufen oder Durchsuchen von Baum- oder Graphdatenstrukturen . Der Algorithmus beginnt am Wurzelknoten (bei der Auswahl eines beliebigen Knotens als Wurzelknoten im Fall eines Graphen) und untersucht so weit wie möglich entlang jeder Verzweigung, bevor er zurückverfolgt wird.

Eine Version der Tiefensuche wurde im 19. Jahrhundert vom französischen Mathematiker Charles Pierre Trémaux als Lösungsstrategie für Labyrinthe untersucht .

Eigenschaften

Die Zeit und Raumanalyse von DFS ist je nach seinem Einsatzgebiet. In der theoretischen Informatik wird DFS normalerweise verwendet, um einen ganzen Graphen zu durchqueren und braucht Zeit , wobei |V| ist die Anzahl der Ecken und |E| die Anzahl der Kanten. Dies ist linear in der Größe des Diagramms. In diesen Anwendungen wird im schlimmsten Fall auch Platz verwendet , um den Stapel von Scheitelpunkten auf dem aktuellen Suchpfad sowie den Satz der bereits besuchten Scheitelpunkte zu speichern. Somit sind in dieser Einstellung die Zeit- und Raumgrenzen dieselben wie bei der Breitensuche und die Wahl, welcher dieser beiden Algorithmen verwendet wird, hängt weniger von ihrer Komplexität als mehr von den unterschiedlichen Eigenschaften der Vertex-Ordnungen ab, die die beiden Algorithmen erzeugen .

Bei Anwendungen von DFS in Bezug auf bestimmte Domänen, wie beispielsweise die Suche nach Lösungen in künstlicher Intelligenz oder Web-Crawling, ist der zu durchquerende Graph oft entweder zu groß, um ihn vollständig zu besuchen, oder unendlich (DFS kann unter Nicht-Terminierung leiden ). In solchen Fällen wird nur bis zu einer begrenzten Tiefe gesucht ; aufgrund begrenzter Ressourcen, wie beispielsweise Speicher oder Plattenplatz, verwendet man typischerweise keine Datenstrukturen, um den Satz aller zuvor besuchten Scheitelpunkte zu verfolgen. Wenn die Suche in einer begrenzten Tiefe durchgeführt wird, ist die Zeit in Bezug auf die Anzahl der erweiterten Scheitelpunkte und Kanten immer noch linear (obwohl diese Zahl nicht der Größe des gesamten Graphen entspricht, da einige Scheitelpunkte mehr als einmal und andere durchsucht werden können überhaupt nicht), aber die Platzkomplexität dieser DFS-Variante ist nur proportional zur Tiefengrenze und daher viel kleiner als der Platzbedarf für die Suche in der gleichen Tiefe mit der Breitensuche. Für solche Anwendungen eignet sich DFS auch viel besser für heuristische Methoden zur Auswahl eines wahrscheinlich aussehenden Zweigs. Wenn eine geeignete Tiefengrenze nicht a priori bekannt ist, wendet die iterative Deepening-Tiefe-First-Suche DFS wiederholt mit einer Folge ansteigender Grenzen an. Im Analysemodus der künstlichen Intelligenz mit einem Verzweigungsfaktor größer als eins erhöht die iterative Vertiefung die Laufzeit nur um einen konstanten Faktor gegenüber dem Fall, in dem die korrekte Tiefengrenze aufgrund des geometrischen Wachstums der Anzahl von Knoten pro Ebene bekannt ist .

DFS kann auch verwendet werden, um eine Stichprobe von Graphknoten zu sammeln . Jedoch ist unvollständiges DFS, ähnlich wie unvollständiges BFS , in Richtung Knoten von hohem Grad verzerrt .

Beispiel

Für die folgende Grafik:

Ein ungerichteter Graph mit Kanten AB, BD, BF, FE, AC, CG, AE

eine Tiefensuche beginnend am Knoten A, vorausgesetzt, dass die linken Kanten im gezeigten Graphen vor den rechten Kanten gewählt werden, und unter der Annahme, dass sich die Suche an zuvor besuchte Knoten erinnert und sie nicht wiederholt (da dies ein kleiner Graph ist), wird visit die Knoten in der folgenden Reihenfolge: A, B, D, F, E, C, G. Die bei dieser Suche durchlaufenen Kanten bilden einen Trémaux-Baum , eine Struktur mit wichtigen Anwendungen in der Graphentheorie . Das Durchführen der gleichen Suche, ohne sich an zuvor besuchte Knoten zu erinnern, führt dazu, dass die Knoten in der Reihenfolge A, B, D, F, E, A, B, D, F, E usw. für immer besucht werden, gefangen in A, B, D, F-, E-Zyklus und nie C oder G erreichen.

Iterative Vertiefung ist eine Technik, um diese Endlosschleife zu vermeiden und würde alle Knoten erreichen.

Ausgabe einer Tiefensuche

Eine bequeme Beschreibung einer Tiefensuche eines Graphen erfolgt in Form eines Spannbaums der während der Suche erreichten Scheitelpunkte. Basierend auf diesem aufspannenden Baum lassen sich die Kanten des Originalgraphen in drei Klassen einteilen: Vorwärtskanten , die von einem Knoten des Baums auf einen seiner Nachkommen zeigen, Rückkanten , die von einem Knoten auf einen seiner Vorfahren zeigen, und Kreuzkanten , die beides nicht tun. Manchmal werden Baumkanten , also Kanten, die zum Spannbaum selbst gehören, getrennt von Vorwärtskanten klassifiziert. Wenn der ursprüngliche Graph ungerichtet ist, sind alle seine Kanten Baumkanten oder Hinterkanten.

DFS-Bestellung

Eine Aufzählung der Knoten eines Graphen wird als DFS-Ordnung bezeichnet, wenn es sich um die mögliche Ausgabe der Anwendung von DFS auf diesen Graphen handelt.

Sei ein Graph mit Ecken. Denn sei eine Liste von verschiedenen Elementen von , for , sei der größte solcher, der ein Nachbar von ist , falls ein solcher existiert, und sei anders.

Sei eine Aufzählung der Ecken von . Die Aufzählung soll eine DFS Ordnung sein (mit der Quelle ) , wenn für alle , ist der Scheitelpunkt , so daß maximal ist. Denken Sie daran, dass dies die Menge der Nachbarn von ist . Äquivalent ist eine DFS-Anordnung, wenn es für alle mit einen Nachbarn von gibt , der .

Scheitelpunkt-Bestellungen

Es ist auch möglich, die Tiefensuche zu verwenden, um die Scheitelpunkte eines Graphen oder Baums linear zu ordnen. Dafür gibt es vier Möglichkeiten:

  • Eine Vorsortierung ist eine Liste der Scheitelpunkte in der Reihenfolge, in der sie zuerst vom Tiefensuchalgorithmus besucht wurden. Dies ist eine kompakte und natürliche Art, den Fortschritt der Suche zu beschreiben, wie es zuvor in diesem Artikel getan wurde. Eine Vorsortierung eines Ausdrucksbaums ist der Ausdruck in polnischer Notation .
  • Eine Nachsortierung ist eine Liste der Scheitelpunkte in der Reihenfolge, in der sie zuletzt vom Algorithmus besucht wurden. Eine Nachordnung eines Ausdrucksbaums ist der Ausdruck in umgekehrter polnischer Notation .
  • Eine umgekehrte Vorsortierung ist die Umkehrung einer Vorsortierung, dh eine Liste der Knoten in der entgegengesetzten Reihenfolge ihres ersten Besuchs. Die umgekehrte Vorbestellung ist nicht gleichbedeutend mit der Nachbestellung.
  • Eine Reverse Postordering ist die Umkehrung einer Postordering, dh eine Liste der Knoten in der entgegengesetzten Reihenfolge ihres letzten Besuchs. Reverse Postordering ist nicht dasselbe wie Preordering.

Für binäre Bäume gibt es zusätzlich In-Ordering und Reverse-In-Ordering .

Wenn beispielsweise der gerichtete Graph unten, beginnend bei Knoten A, durchsucht wird, ist die Abfolge der Durchquerungen entweder ABDBACA oder ACDCABA (die Wahl, zuerst B oder C von A aus zu besuchen, ist Sache des Algorithmus). Beachten Sie, dass wiederholte Besuche in Form von Backtracking zu einem Knoten, um zu überprüfen, ob er noch nicht besuchte Nachbarn hat, hier eingeschlossen sind (selbst wenn festgestellt wird, dass er keine hat). Somit sind die möglichen Vorbestellungen ABDC und ACDB, während die möglichen Nachbestellungen DBCA und DCBA sind und die möglichen umgekehrten Nachbestellungen ACBD und ABC D sind.

Ein gerichteter Graph mit Kanten AB, BD, AC, CD

Reverse Postordering erzeugt eine topologische Sortierung jedes gerichteten azyklischen Graphen . Diese Reihenfolge ist auch bei der Kontrollflussanalyse nützlich, da sie oft eine natürliche Linearisierung der Kontrollflüsse darstellt. Das obige Diagramm könnte den Kontrollfluss im Codefragment unten darstellen, und es ist natürlich, diesen Code in der Reihenfolge ABCD oder ACBD zu betrachten, aber nicht natürlich, die Reihenfolge ABDC oder ACD B zu verwenden.

if (A) then {
    B
} else {
    C
}
D

Pseudocode

Eingabe : Ein Graph G und eine Ecke v von G

Ausgabe : Alle von v erreichbaren Scheitelpunkte als entdeckt markiert

Eine rekursive Implementierung von DFS:

procedure DFS(G, v) is
    label v as discovered
    for all directed edges from v to w that are in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)

Die Reihenfolge, in der die Scheitelpunkte von diesem Algorithmus entdeckt werden, wird als lexikographische Reihenfolge bezeichnet .

Eine nicht-rekursive Implementierung von DFS mit Platzkomplexität im schlimmsten Fall , mit der Möglichkeit doppelter Scheitelpunkte auf dem Stapel:

procedure DFS_iterative(G, v) is
    let S be a stack
    S.push(v)
    while S is not empty do
        v = S.pop()
        if v is not labeled as discovered then
            label v as discovered
            for all edges from v to w in G.adjacentEdges(v) do 
                S.push(w)
Ein ungerichteter Graph mit Kanten AB, BD, BF, FE, AC, CG, AE

Diese beiden Varianten von DFS besuchen die Nachbarn jedes Knotens in entgegengesetzter Reihenfolge: der erste Nachbar von v, der von der rekursiven Variante besucht wird, ist der erste in der Liste benachbarter Kanten, während in der iterativen Variante der erste besuchte Nachbar ist die letzte in der Liste der angrenzenden Kanten. Die rekursive Implementierung besucht die Knoten aus dem Beispielgraphen in der folgenden Reihenfolge: A, B, D, F, E, C, G. Die nicht-rekursive Implementierung besucht die Knoten wie folgt: A, E, F, B, D , C, G.

Die nicht-rekursive Implementierung ähnelt der Breitensuche , unterscheidet sich jedoch in zweierlei Hinsicht davon:

  1. es verwendet einen Stack anstelle einer Warteschlange, und
  2. es verzögert die Überprüfung, ob ein Scheitelpunkt entdeckt wurde, bis der Scheitelpunkt aus dem Stapel entfernt wird, anstatt diese Überprüfung vor dem Hinzufügen des Scheitelpunkts durchzuführen.

Wenn G ein Baum ist , führt das Ersetzen der Warteschlange des Breitensuchalgorithmus durch einen Stapel zu einem Tiefensuchalgorithmus. Für allgemeine Graphen würde das Ersetzen des Stapels der iterativen Tiefensuche-Implementierung durch eine Warteschlange auch einen Breitensuchalgorithmus erzeugen, wenn auch ein etwas nicht standardmäßiger.

Eine andere mögliche Implementierung der iterativen Tiefensuche verwendet einen Stapel von Iteratoren der Liste von Nachbarn eines Knotens anstelle eines Stapels von Knoten. Dies ergibt den gleichen Durchlauf wie bei rekursivem DFS.

procedure DFS_iterative(G, v) is
    let S be a stack
    S.push(iterator of G.adjacentEdges(v))
    while S is not empty do
        if S.peek().hasNext() then
            w = S.peek().next()
            if w is not labeled as discovered then
                label w as discovered
                S.push(iterator of G.adjacentEdges(w))
        else
            S.pop() 

Anwendungen

Zu den Algorithmen, die die Tiefensuche als Baustein verwenden, gehören:

Komplexität

Die Rechenkomplexität von DFS wurde von John Reif untersucht . Genauer gesagt gegeben, eine grafische Darstellung , lassen Sie die Bestellung durch den Standard rekursive DFS - Algorithmus berechnet werden. Diese Reihenfolge wird als lexikographische Tiefensuchreihenfolge bezeichnet. John Reif betrachtete die Komplexität der Berechnung der lexikographischen Tiefensuchreihenfolge, wenn ein Graph und eine Quelle gegeben sind. Eine Entscheidungsversion des Problems (das Testen, ob ein Scheitelpunkt u in dieser Reihenfolge vor einem Scheitelpunkt v auftritt ) ist P- vollständig , was bedeutet, dass es ein Albtraum für die parallele Verarbeitung ist.

Eine Tiefensuchreihenfolge (nicht unbedingt die lexikographische) kann durch einen randomisierten parallelen Algorithmus in der Komplexitätsklasse RNC berechnet werden . Bis 1997 war es unbekannt, ob eine Tiefendurchquerung durch einen deterministischen parallelen Algorithmus in der Komplexitätsklasse NC konstruiert werden konnte .

Siehe auch

Anmerkungen

Verweise

Externe Links

Opiniones de nuestros usuarios

Katja Sturm

Die Informationen über Tiefensuche sind sehr interessant und zuverlässig, wie der Rest der Artikel, die ich bisher gelesen habe, und das sind schon viele, denn ich warte seit fast einer Stunde auf mein Tinder-Date und er ist nicht aufgetaucht, also denke ich, er hat mich versetzt. Ich nutze diese Gelegenheit, um ein paar Sterne für die Firma zu hinterlassen und auf mein beschissenes Leben zu scheißen

Sven Ott

Richtig. Sie liefert die notwendigen Informationen über Tiefensuche., Richtig

Carmen Rose

Ich weiß nicht, wie ich zu diesem Artikel über Tiefensuche gekommen bin, aber er hat mir sehr gut gefallen, Der Eintrag über Tiefensuche ist der, den ich gesucht habe