Tiefensuche (DFS) ist ein Algorithmus, um einen Baum, Baumstruktur oder Graphen zu überqueren oder zu suchen. Man fängt an der Wurzel an (einen Knoten als die Wurzel im Graph-Fall auswählend), und erforscht so weit möglich entlang jedem Zweig vor dem Zurückverfolgen.

Eine Version der Tiefensuche wurde im 19. Jahrhundert vom französischen Mathematiker Charles Pierre Tremaux als eine Strategie untersucht, für Irrgärten zu lösen.

Formelle Definition

Formell ist DFS eine uninformierte Suche, die durch die Erweiterung des ersten Kinderknotens des Suchbaums fortschreitet, der erscheint und so das Gehen tiefer und tiefer, bis ein Absicht-Knoten gefunden wird, oder bis es einen Knoten schlägt, der keine Kinder hat. Dann die Suchrückzüge, zum neusten Knoten zurückkehrend, hat es nicht beendet zu erforschen. In einer nichtrekursiven Durchführung werden alle frisch ausgebreiteten Knoten zu einem Stapel für die Erforschung hinzugefügt.

Eigenschaften

Die Analyse der Zeit und Raums von DFS unterscheidet sich gemäß seinem Anwendungsgebiet. In der theoretischen Informatik wird DFS normalerweise verwendet, um einen kompletten Graphen zu überqueren, und nimmt O (V + E), geradlinig in der Größe des Graphen Zeit in Anspruch. In diesen Anwendungen verwendet es auch Raum O (V) im Grenzfall, um den Stapel von Scheitelpunkten auf dem aktuellen Suchweg sowie dem Satz von bereits besuchten Scheitelpunkten zu versorgen. So, in dieser Einstellung, sind die Grenzen der Zeit und Raums dasselbe bezüglich der Breitensuche, und dessen Wahl dieser zwei Algorithmen, um zu verwenden, weniger von ihrer Kompliziertheit und mehr von den verschiedenen Eigenschaften der Scheitelpunkt-Einrichtung abhängt, die die zwei Algorithmen erzeugen.

Für Anwendungen von DFS, um Probleme in der künstlichen Intelligenz jedoch zu suchen, ist der zu suchende Graph häufig entweder zu groß, um vollständig oder sogar unendlich zu besuchen, und DFS kann unter der Nichtbeendigung leiden, wenn die Länge eines Pfads im Suchbaum unendlich ist. Deshalb wird die Suche nur für eine beschränkte Tiefe, und wegen der beschränkten Speicherverfügbarkeit durchgeführt man verwendet normalerweise Datenstrukturen nicht, die den Satz aller vorher besuchten Scheitelpunkte nachgehen. In diesem Fall ist die Zeit noch in der Zahl von ausgebreiteten Scheitelpunkten und Rändern geradlinig (obwohl diese Zahl nicht dasselbe als die Größe des kompletten Graphen ist, weil einige Scheitelpunkte mehr gesucht werden dürfen als einmal und andere überhaupt nicht), aber die Raumkompliziertheit dieser Variante von DFS ist nur zur Tiefe-Grenze proportional, viel kleiner als der Raum, der erforderlich ist, um zu derselben Tiefe mit der Breitensuche zu suchen. Für solche Anwendungen leiht DFS auch sich viel besser zu heuristischen Methoden, einen wahrscheinlich aussehenden Zweig zu wählen. Wenn eine passende Tiefe-Grenze nicht bekannt ist, wendet a priori, wiederholende tiefer werdende Tiefensuche DFS wiederholt mit einer Folge an, Grenzen zu vergrößern; in der Weise der künstlichen Intelligenz der Analyse, mit einem sich verzweigenden Faktor, der größer ist als einer, wiederholende tiefer werdende Zunahmen die Laufzeit durch nur einen unveränderlichen Faktor über den Fall, in dem die richtige Tiefe-Grenze wegen des geometrischen Wachstums der Zahl von Knoten pro Niveau bekannt ist.

DFS kann auch verwendet werden, um eine Probe von Graph-Knoten zu sammeln. Jedoch wird unvollständiger DFS, ähnlich zu unvollständigem BFS, zu Knoten des hohen Grads beeinflusst.

Beispiel

Für den folgenden Graphen:

eine Tiefensuche, die an A anfängt, annehmend, dass die linken Ränder im gezeigten Graphen vor richtigen Rändern und dem Annehmen der Suche gewählt werden, erinnert sich an vorher besuchte Knoten und wird sie nicht wiederholen (da das ein kleiner Graph ist), wird die Knoten in der folgenden Ordnung besuchen: A, B, D, F, E, C, G. Die in dieser Suche überquerten Ränder bilden einen Baum von Trémaux, eine Struktur mit wichtigen Anwendungen in der Graph-Theorie.

Das Durchführen derselben Suche, ohne sich an vorher besuchte Knoten zu erinnern, läuft auf Besuch von Knoten auf die Ordnung A, B, D, F, E, A, B, D, F, E, usw. für immer, gefangen im A, B, D, F, E Zyklus und nie das Erreichen C oder G hinaus.

Das wiederholende Vertiefen ist eine Technik, um diese unendliche Schleife zu vermeiden, und würde alle Knoten erreichen.

Produktion einer Tiefensuche

Das natürlichste Ergebnis einer Tiefe die erste Suche eines Graphen (wenn es als eine Funktion aber nicht ein Verfahren betrachtet wird) ist ein Überspannen-Baum der während der Suche erreichten Scheitelpunkte. Gestützt auf diesem Überspannen-Baum können die Ränder des ursprünglichen Graphen in drei Klassen geteilt werden: Schicken Sie Ränder nach (oder "Entdeckungsränder"), die von einem Knoten des Baums einem seiner Nachkommen, Zurückränder hinweisen, die von einem Knoten bis einen seiner Vorfahren und bösen Rändern hinweisen, die keinen tun. Manchmal werden Baumränder, Ränder, die dem Überspannen-Baum selbst gehören, getrennt von Vorwärtsrändern klassifiziert. Es kann gezeigt werden, dass, wenn der ursprüngliche Graph dann ungeleitet ist, alle seine Ränder Baumränder oder Zurückränder sind.

Scheitelpunkt-Einrichtung

Es ist auch möglich, die Tiefensuche zu verwenden, um die Scheitelpunkte des ursprünglichen Graphen (oder Baum) geradlinig zu bestellen. Es gibt drei allgemeine Weisen, das zu tun:

• Eine Voreinrichtung ist eine Liste der Scheitelpunkte in der Ordnung, dass sie zuerst durch den Tiefensuche-Algorithmus besucht wurden. Das ist eine kompakte und natürliche Weise, den Fortschritt der Suche zu beschreiben, wie früher in diesem Artikel getan wurde. Eine Voreinrichtung eines Ausdruck-Baums ist der Ausdruck in der polnischen Notation.
• Eine Posteinrichtung ist eine Liste der Scheitelpunkte in der Ordnung, dass sie besucht durch den Algorithmus letzt waren. Eine Posteinrichtung eines Ausdruck-Baums ist der Ausdruck in der polnischen Rücknotation.
• Eine Rückseite, die postbestellt, ist die Rückseite einer Posteinrichtung, d. h. eine Liste der Scheitelpunkte in der entgegengesetzten Ordnung ihres letzten Besuchs. Rückseite, die postbestellt, ist nicht dasselbe als Voreinrichtung. Zum Beispiel, wenn man den geleiteten Graphen sucht

:

: am Knoten A beginnend, besucht man die Knoten in der Folge, um Listen entweder Ein B D B Ein C A oder Ein C D C Ein B zu erzeugen (abhängig davon, ob der Algorithmus beschließt, B oder C zuerst zu besuchen). Bemerken Sie, dass Wiederholung in der Form des Zurückverfolgens zu einem Knoten besucht, um zu überprüfen, ob es noch verlassene Nachbarn hat, werden hier eingeschlossen (selbst wenn, wie man findet, es niemanden hat). So ist die mögliche Voreinrichtung Ein B D C und Ein C D B (Ordnung durch das leftmost Ereignis des Knotens in der obengenannten Liste), während die mögliche Rückposteinrichtung Ein C B D und Ein B C D (Ordnung durch das niedrigstwertige Ereignis des Knotens in der obengenannten Liste) ist. Rückseite, die postbestellt, erzeugt ein topologisches Sortieren von irgendwelchem hat acyclic Graphen geleitet. Diese Einrichtung ist auch in der Kontrollfluss-Analyse nützlich, weil es häufig einen natürlichen linearization des Kontrollflusses vertritt. Der Graph könnte oben den Fluss der Kontrolle in einem Codebruchstück wie vertreten

wenn (A) dann {\

B

} sonst {\

C

}\

D

: und es ist natürlich, diesen Code in der Ordnung Als einen B C D oder Einen C B D, aber nicht natürlich zu betrachten, um die Ordnung Ein B D C oder Ein C D B zu verwenden.

Pseudocode

Eingang: Ein Graph G und ein Scheitelpunkt v G

Produktion: Ein Beschriften der Ränder im verbundenen Bestandteil von v als Entdeckungsränder und Zurückränder

1 Verfahren DFS (G, v):

2 Etikett v, wie erforscht

,

3 für alle Ränder e in G.incidentEdges (v) tun

4, wenn Rand e dann unerforscht

ist

5 w  G.opposite (v, e)

6, wenn Scheitelpunkt w dann unerforscht

ist

7 Etikett e als ein Entdeckungsrand

8 rekursiv Anruf DFS (G, w)

9 sonst

10 Etikett e als ein Zurückrand

Anwendungen

Algorithmen, die Tiefensuche als ein Baustein verwenden, schließen ein:

• Entdeckung verbundener Bestandteile.
• Das topologische Sortieren.
• Die Entdeckung 2-(Rand oder Scheitelpunkt) - verbundene Bestandteile.
• Die Entdeckung 3-(Rand oder Scheitelpunkt) - verbundene Bestandteile.
• Die Entdeckung der Brücken eines Graphen.
• Die Entdeckung stark verbundener Bestandteile.
• Planarity, der prüft
• Rätsel mit nur einer Lösung wie Irrgärten lösend. (DFS kann angepasst werden, um alle Lösungen eines Irrgartens durch nur einschließlich Knoten auf dem aktuellen Pfad im besuchten Satz zu finden.)
• Irrgarten-Generation kann eine randomized Tiefensuche verwenden.
• Die Entdeckung biconnectivity in Graphen.

Siehe auch

• Breitensuche
• Suchen Sie Spiele

Referenzen

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen, die Zweite Ausgabe. MIT Presse und McGraw-Hügel, 2001. Internationale Standardbuchnummer 0-262-03293-7. Abschnitt 22.3: Tiefensuche, Seiten 540-549.

Links

• Tiefe die erste Erklärung und das Beispiel
• C ++ Zunahme-Graph-Bibliothek: Tiefensuche
• Tiefensuche-Zeichentrickfilm (für einen geleiteten Graphen)
• Tiefe zuerst und Breite suchen zuerst: Erklärung und Code
• QuickGraph, Tiefe sucht zuerst Beispiel für.Net
• Tiefensuche-Algorithmus hat Erklärung (Java und C ++ Durchführungen) illustriert
• YAGSBPL - Ein Schablone-basierter C ++ Bibliothek für den Graphen sucht und planend