Tiefensuche
Algorithmus zur systematischen Erkundung von Graphen und Bäumen
Tiefensuche Die Tiefensuche ist ein Algorithmus zur vollständigen Durchsuchung von Graphen oder Bäumen, bei dem die Erkundung jeweils so tief wie möglich in einen Zweig erfolgt, bevor andere Zweige untersucht werden.
Das Wichtigste auf einen Blick
- Tiefensuche ist ein rekursiver oder stack-basierter Algorithmus zur Graphdurchsuchung.
- Sie besucht Knoten in einem Graphen, indem sie jeweils so tief wie möglich in einen Zweig vordringt.
- Tiefensuche kann zur Pfadsuche, Zykluserkennung und Topologischen Sortierung verwendet werden.
- Der Algorithmus eignet sich für gerichtete und ungerichtete Graphen sowie für Bäume.
- Die Implementierung erfolgt meist rekursiv oder mit einem expliziten Stack.
- Die Laufzeit liegt in der Größenordnung von O(V + E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist.
Überblick: Tiefensuche
Die Tiefensuche (englisch: Depth-First Search, DFS) ist ein fundamentaler Algorithmus in der Graphentheorie und Informatik. Sie wird eingesetzt, um alle Knoten eines Graphen oder Baumes systematisch zu besuchen und zu verarbeiten. Dabei folgt die Suche einem Pfad so weit wie möglich in die Tiefe, bevor sie zurückkehrt und andere Pfade erkundet. Dies macht die Tiefensuche besonders geeignet für Aufgaben wie das Finden von Pfaden, das Erkennen von Zyklen oder das Durchsuchen von Baumstrukturen.
Was ist Tiefensuche?
Die Tiefensuche ist ein Algorithmus zur systematischen Erkundung aller Knoten eines Graphen oder Baumes. Dabei wird von einem Startknoten ausgehend jeweils ein Nachfolger besucht, bis kein unbesuchter Nachfolger mehr vorhanden ist. Dann wird zurückgegangen und andere Pfade werden erkundet.
Funktionsweise der Tiefensuche
Der Algorithmus beginnt an einem Startknoten und besucht rekursiv oder iterativ benachbarte Knoten, die noch nicht besucht wurden. Dabei wird ein Pfad so lange verfolgt, bis keine weiteren unbesuchten Nachbarn existieren. Anschließend wird zum vorherigen Knoten zurückgekehrt, um andere Pfade zu erkunden.
Implementierungsmöglichkeiten
Die Tiefensuche kann entweder rekursiv implementiert werden, wobei der Aufrufstack die zu besuchenden Knoten verwaltet, oder iterativ mit einem expliziten Stack als Hilfsdatenstruktur. Beide Varianten erreichen das gleiche Ergebnis.
Vergleich rekursive und iterative Tiefensuche
| Kriterium | Rekursive Implementierung | Iterative Implementierung |
|---|---|---|
| Speicherverbrauch | Nutzt den Aufrufstack | Nutzt expliziten Stack |
| Einfachheit | Einfacher zu verstehen und zu schreiben | Etwas komplexer, aber kontrollierbarer |
| Stack Overflow Risiko | Kann bei sehr großen Graphen auftreten | Weniger anfällig für Stack Overflow |
Anwendungsbereiche der Tiefensuche
Tiefensuche wird in vielen Bereichen eingesetzt, darunter: Finden von Pfaden in Graphen, Erkennung von Zyklen, Bestimmung zusammenhängender Komponenten, Topologische Sortierung in gerichteten Graphen, und als Basisalgorithmus in Künstlicher Intelligenz für Suchprobleme.
Beispiel: Tiefensuche in einem ungerichteten Graphen
Gegeben sei ein ungerichteter Graph mit Knoten A bis E. Startet man die Tiefensuche bei Knoten A, so werden die Knoten in der Reihenfolge A, B, D, E, C besucht, indem jeweils ein Pfad so tief wie möglich verfolgt wird, bevor zurückgegangen wird.
Vorteile und Nachteile der Tiefensuche
| Vorteile | Einfache Implementierung | Geringer Speicherbedarf bei flachen Graphen | Geeignet zur Zykluserkennung |
|---|---|---|---|
| Nachteile | Kann Stack Overflow verursachen | Findet nicht zwingend kürzeste Pfade | Nicht optimal für breite Graphen |
Wichtig
Tiefensuche unterscheidet sich von der Breitensuche darin, dass sie jeweils einen Pfad so tief wie möglich verfolgt, während Breitensuche alle Nachbarn einer Ebene zuerst besucht.
Zusatzinformationen
Begriff: Tiefensuche
Englischer Begriff: Depth-First Search (DFS)
Anwendungsgebiete: Graphentheorie, Informatik, Künstliche Intelligenz, Netzwerkanalyse
Algorithmustyp: Graphdurchsuchungsalgorithmus
Komplexität: O(V + E)
Datenstruktur: Stack (implizit durch Rekursion oder explizit)
Einsatzbereiche: Pfadsuche, Zykluserkennung, Topologische Sortierung, Komponentenbestimmung
Synonyme und alternative Bezeichnungen
Häufige Fragen zu Tiefensuche
Was ist der Unterschied zwischen Tiefensuche und Breitensuche?
Die Tiefensuche verfolgt einen Pfad so tief wie möglich, bevor sie zurückkehrt, während die Breitensuche alle Nachbarn einer Ebene zuerst besucht, bevor sie tiefer geht.
Kann Tiefensuche in gerichteten Graphen verwendet werden?
Ja, Tiefensuche funktioniert sowohl in gerichteten als auch in ungerichteten Graphen.
Wie erkennt man mit Tiefensuche Zyklen in einem Graphen?
Während der Tiefensuche kann ein Knoten, der bereits im aktuellen Suchpfad besucht wurde, auf einen Zyklus hinweisen.
Welche Datenstruktur wird bei der Tiefensuche verwendet?
Die Tiefensuche verwendet einen Stack, entweder implizit durch Rekursion oder explizit als Datenstruktur.
Ist Tiefensuche immer die beste Wahl für Pfadsuche?
Nein, Tiefensuche findet nicht unbedingt den kürzesten Pfad. Für kürzeste Pfade sind Algorithmen wie Breitensuche oder Dijkstra besser geeignet.
Wie hoch ist die Laufzeit der Tiefensuche?
Die Laufzeit beträgt O(V + E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten im Graphen ist.
Kann Tiefensuche in der Künstlichen Intelligenz eingesetzt werden?
Ja, Tiefensuche wird in der KI für Suchprobleme und zur Exploration von Zustandsräumen verwendet.
Quellen & weiterführende Informationen
Quellenvorschläge und Nachweise zum Artikel. Bitte externe Inhalte eigenständig prüfen.
- 01Introduction to Algorithms ↗
Standardwerk zur Algorithmik mit ausführlicher Beschreibung der Tiefensuche
https://mitpress.mit.edu/books/introduction-algorithms - 02Graph Search, Shortest Paths, and Data Structures ↗
Lehrmaterial zur Graphdurchsuchung mit Tiefensuche
https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lectures/lecture3.pdf - 03Depth-First Search (DFS) Algorithm ↗
Praktische Einführung und Beispiele zur Tiefensuche
https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
Diese Seite in Zahlen
Alle Werte in diesem Abschnitt beziehen sich ausschließlich auf diesen Artikel.
Wissensplattform in Zahlen
Diese Werte beziehen sich auf die gesamte Plattform und alle veröffentlichten Artikel.