WikiDer > Tiefensuche

Depth-first search
Reihenfolge, in der die Knoten des Graphen angezeigt werden

Tiefensuche (DFS) ist ein Suchalgorithmus für die Suche nach a Baumstruktur oder ein Anzahl. Der Algorithmus beginnt bei der Wurzel (oder einem beliebigen Knoten in einem Diagramm) und wählt einen Zweig aus und durchsucht ihn so weit wie möglich, ohne zu den vorherigen Schritten zurückzukehren.

Überblick

Formal ist DFS eine uninformierte Suchmethode, die beim ersten untergeordneten Knoten beginnt und immer tiefer sucht, bis sie den Zielknoten findet oder bis keine untergeordneten Knoten mehr vorhanden sind. Wenn keine weiteren untergeordneten Knoten vorhanden sind, kehrt der Algorithmus zurück, bis er einen untergeordneten Knoten findet, der noch nicht durchsucht wurde. Bei einer nicht-rekursiven Implementierung werden alle offenen Knoten für eine spätere Untersuchung gestapelt.

Die räumliche Komplexität ist viel geringer als bei a Breitensuche. Die Zeitkomplexität beider Algorithmen hängt von der Anzahl der Knoten und der Anzahl der zu durchsuchenden Bögen (Verbindungen) ab. Beide Algorithmen sind O(|K| |B|), wobei K die Anzahl der Knoten und B die Anzahl der Bögen ist.

Iterative Tiefensuche

sehen Iterative vertiefende Tiefensuche für den Hauptartikel zu diesem Thema.

Beim Durchsuchen großer Graphen, die nicht vollständig in den Speicher passen, kann die Suche unendlich sein, da der Pfad unendlich lang erscheint. Die einfache Lösung, bereits besuchte Knoten einzufärben, ist nicht anwendbar, da nicht alle diese Knoten im Speicher gehalten werden können. Dies kann durch iteratives Erhöhen der Tiefe gelöst werden.

Siehe die Kategorie Tiefensuche von Wikimedia Commons für Mediendateien zu diesem Thema.