imported>YMS: Sprache

2026-01-06T23:38:08Z

Sprache

Neue Seite

[[Datei:Depth-First-Search.gif|mini|250px|[[Animation]] der Tiefensuche in einem [[Baum (Datenstruktur)|Baum]]]]

'''Tiefensuche''' ({{enS|depth-first search}}, ''DFS'') ist in der [[Informatik]] ein Verfahren zum Suchen von [[Knoten (Graphentheorie)|Knoten]] in einem [[Graph (Graphentheorie)|Graphen]]. Sie zählt zu den uninformierten [[Suchalgorithmen]]. Im Gegensatz zur [[Breitensuche]] wird bei der Tiefensuche zunächst ein [[Weg (Graphentheorie)|Pfad]] vollständig in die Tiefe beschritten, bevor abzweigende Pfade beschritten werden<ref>{{Literatur |Autor=Volker Turau |Titel=Algorithmische Graphentheorie |Auflage=3 |Verlag=Oldenbourg Wissenschaftsverlag |Ort=München |Datum=2009 |ISBN=978-3-486-59057-9 |Seiten=94–98}}</ref>. Dabei sollen alle erreichbaren Knoten des Graphen besucht werden. Für Graphen mit potenziell wenigen, langen Pfaden bietet sich die [[beschränkte Tiefensuche]] an, bei der jeder Pfad nur bis zu einer bestimmten Tiefe beschritten wird.

Eine Verbesserung der Tiefensuche ist die [[iterative Tiefensuche]].

== Arbeitsweise ==
{{Siehe auch|Binärbaum#Tiefensuche|titel1 = Binärbaum - Tiefensuche}}
Die Tiefensuche ist ein uninformierter [[Suchalgorithmus]], welche durch Expansion des jeweils ersten auftretenden [[Nachfolger (Graphentheorie)|Nachfolgeknotens]] im [[Graph (Graphentheorie)|Graphen]] nach und nach vom Startknoten aus weiter in die Tiefe sucht. In welcher Reihenfolge die Nachfolger eines Knotens dabei bestimmt werden, hängt von der Repräsentation der [[Nachfolger (Mathematik)|Nachfolger]] ab. Bei der Repräsentation über eine [[Adjazenzliste]] mittels einer [[Verkettete Liste|verketteten Liste]] werden beispielsweise die Knoten in der Reihenfolge ihres Eintrags in dieser [[Liste (Datenstruktur)|Liste]] durchlaufen. Im oben angegebenen Bild wird implizit davon ausgegangen, dass die Nachfolger von links nach rechts ausgewählt werden.

Für [[Ungerichteter Graph|ungerichtete Graphen]] sieht das Verfahren wie folgt aus: Zuerst wird ein Startknoten <math> \left. u \right. </math> ausgewählt. Von diesem [[Knoten (Graphentheorie)|Knoten]] aus wird nun die erste [[Kante (Graphentheorie)|Kante]] <math> \left( u,v \right) </math> betrachtet und getestet, ob der gegenüberliegende Knoten <math> \left. v \right. </math> schon entdeckt wurde bzw. das gesuchte Element ist. Ist dies noch nicht der Fall, so wird [[Rekursion|rekursiv]] für diesen Knoten die Tiefensuche aufgerufen, wodurch wieder der erste [[Nachfolger (Mathematik)|Nachfolger]] dieses Knotens expandiert wird. Diese Art der Suche wird so lange fortgesetzt, bis das gesuchte Element entweder gefunden wurde oder die Suche bei einer [[Senke (Graphentheorie)|Senke]] im [[Graph (Graphentheorie)|Graphen]] angekommen ist und somit keine weiteren Nachfolgeknoten mehr untersuchen kann. An dieser Stelle kehrt der [[Algorithmus]] nun zum zuletzt expandierten Knoten <math> \left. u \right. </math> zurück und untersucht den nächsten Nachfolger des Knotens. Sollte es hier keine weiteren Nachfolger mehr geben, geht der Algorithmus wieder Schritt für Schritt zum jeweiligen [[Vorgänger (Graphentheorie)|Vorgänger]] zurück und versucht es dort erneut. Ein Beispiel für die Anwendung der Tiefensuche auf einen [[Baum (Graphentheorie)|Baum]] zeigt die [[Animation]].
[[Datei:Tree edges.svg|mini|Die vier Typen von [[Kante (Graphentheorie)|Kanten]], die vom Startknoten 1 des gezeigten [[Gerichteter Graph|gerichteten Graphen]] definiert werden. Die schwarzen Kanten zeigen den [[Baum (Graphentheorie)|Baum]], den die Tiefensuche durchläuft.]]
Die [[Kante (Graphentheorie)|Kanten]] des [[Graph (Graphentheorie)|Graphen]], die vom [[Algorithmus]] zum Durchlaufen des Graphen benutzt werden, werden als '''Baumkanten''' bezeichnet. Diejenigen Kanten, die nicht benutzt werden und von einem [[Knoten (Graphentheorie)|Knoten]] zu einem anderen Knoten im selben [[Teilbaum]] führen, der bei der Tiefensuche ''später besucht wird'', heißen '''Vorwärtskanten'''. Diejenigen Kanten, die nicht benutzt werden und von einem Knoten zu einem anderen Knoten im selben Teilbaum führen, der bei der Tiefensuche ''bereits vorher besucht wurde'', heißen '''Rückwärtskanten'''. Diejenigen Kanten, die „quer“ von einem Teilbaum zu einem anderen Teilbaum verlaufen, heißen '''Querkanten'''. Innerhalb des Tiefensuchbaums würde der [[Pfad (Graphentheorie)|Pfad]] zwischen zwei über eine Querkante verbundenen Knoten zunächst ein Auf- und dann ein Absteigen im [[Baum (Graphentheorie)|Baum]] erfordern. Vorwärtskanten, Rückwärtskanten, Querkanten und Baumkanten ergeben insgesamt die Kantenmenge des Graphen.
{|
|[[Datei:DepthFirstSearch graph cities de.svg|mini|350px|links|Eine [[Graphentheoretisch|graphentheoretische]] Landkarte von [[Deutschland]], [[Österreich]] und der [[Schweiz]] mit den Verbindungen zwischen einigen Städten. Dieses Beispiel ist ein ungerichteter Graph mit 10 Knoten.]]
|[[Datei:DepthFirstSearch tree cities de.gif|mini|350x350px|Der Baum, welcher entsteht, wenn man Tiefensuche auf die Landkarte anwendet und in Hannover startet. Dieser Baum hat die Höhe 6. Daher hat die Tiefensuche in diesem Fall die maximale [[Rekursionstiefe]] 6.]]
|}
Der Index der [[Rekursionstiefe]] der [[Rekursive Programmierung|rekursiven]] [[Methode (Programmierung)|Methode]] oder [[Prozedur (Programmierung)|Prozedur]] für die Tiefensuche entspricht dem [[Weg (Graphentheorie)|Knotenabstand]] des aktuell durchlaufenen [[Knoten (Graphentheorie)|Knotens]] vom Startknoten im in der rechten Abbildung gezeigten [[Baum (Graphentheorie)|Baum]]. Dieser Index müsste, um zum Beispiel auf der Konsole ausgegeben zu werden, in einer [[Variable (Programmierung)|Variablen]] gespeichert werden. Diese rekursive Methode oder Prozedur wird so oft aufgerufen, wie die Anzahl der Knoten des [[Graph (Graphentheorie)|Graphen]] ist. Die Rekursion bricht ab, wenn der aktuell durchlaufene Knoten nur Nachbarknoten hat, die schon vorher durchlaufen wurden.

Im Beispiel mit den Städten (siehe oben) gibt es folgende [[Rekursive Programmierung|rekursive]] Aufrufe:

* Hannover (Startknoten, '''Rekursionstiefe''' 0)
* Frankfurt (Nachbarknoten von Hannover, '''Rekursionstiefe''' 1)
* Zürich (Nachbarknoten von Frankfurt, '''Rekursionstiefe''' 2)
* München (Nachbarknoten von Zürich, '''Rekursionstiefe''' 3)
* Stuttgart (Nachbarknoten von München, '''Rekursionstiefe''' 4)
* Hamburg (Nachbarknoten von Stuttgart, '''Rekursionstiefe''' 5)
* Mannheim (Nachbarknoten von Hamburg, '''Rekursionstiefe''' 6)
* Dresden (Nachbarknoten von Stuttgart, '''Rekursionstiefe''' 5)
* Wien (Nachbarknoten von München, '''Rekursionstiefe''' 4)
* Berlin (Nachbarknoten von Wien, '''Rekursionstiefe''' 5)

Der [[Weg (Graphentheorie)|Knotenabstand]] bezieht sich immer auf den Startknoten. Im links dargestellten ungerichteten Graphen ist es Hannover. Bei [[Gerichteter Graph|gerichteten Graphen]] ist der [[Weg (Graphentheorie)|Knotenabstand]] zwischen zwei ''verschiedenen'' Knoten nicht ''unbedingt'' symmetrisch.

Der [[Baum (Graphentheorie)|Baum]], den die Tiefensuche durchläuft, ist ein [[Spannbaum]] des Graphen und hängt vom Startknoten ab. Es ist außerdem wichtig, ob es sich um einen [[Gerichteter Graph|gerichteten Graphen]] oder [[Ungerichteter Graph|ungerichteten Graphen]] handelt.

Der Knotenabstand und die [[Rekursionstiefe]] ist nur für [[Zusammenhängender Graph|zusammenhängende]] [[Graph (Graphentheorie)|Graphen]] definiert und hängt vom Startknoten ab. Für nicht zusammenhängende Graphen ist der Knotenabstand und die Rekursionstiefe nur innerhalb jeder [[Zusammenhang (Graphentheorie)|Zusammenhangskomponente]] definiert.

'''Hinweis''': Der in der Abbildung links oben mit den Städten gezeigte [[Graph (Graphentheorie)|Graph]] ist ein ''ungerichteter'' Graph. Die Reihenfolge der durchlaufenen [[Knoten (Graphentheorie)|Knoten]] ''kann'' sich ändern, wenn stattdessen ein anderer Startknoten oder ein [[gerichteter Graph]] genommen wird, der ''nicht'' symmetrisch ist.

== Algorithmen ==
# Bestimme den [[Knoten (Graphentheorie)|Knoten]], an dem die Suche beginnen soll
# Expandiere den Knoten und speichere der Reihenfolge nach den kleinsten/größten (optional) noch nicht erschlossenen Nachfolger in einem [[Stapelspeicher|Stack]]
# Rufe [[Rekursion|rekursiv]] für jeden der Knoten in dem Stack DFS auf
#* Falls das gesuchte Element gefunden wurde, brich die Suche ab und liefere ein Ergebnis
#* Falls es keine nicht erschlossenen [[Nachfolger (Mathematik)|Nachfolger]] mehr gibt, lösche den obersten Knoten aus dem Stack und rufe für den jetzt oberen Knoten im Stack DFS auf

'''DFS'''(node, goal)
{
if (node == goal)
{
return node;
}
else
{
stack := expand (node)
while (''stack is not empty'')
{
node' := pop(stack);
'''DFS'''(node', goal);
}
}
}

=== Erzeugen des Tiefensuchwaldes ===
Der folgende rekursive [[Algorithmus]] in [[Pseudocode]] erzeugt den Tiefensuchwald eines [[Graph (Graphentheorie)|Graphen]] G mittels Setzen von Discovery- und Finishing-Times und Färben der [[Knoten (Graphentheorie)|Knoten]]. In Anlehnung an [[Thomas H. Cormen|Cormen]] et al. werden zunächst alle Knoten weiß gefärbt. Anschließend startet die Tiefensuche per Definition beim alphabetisch kleinsten Knoten und färbt diesen grau. Danach wird, wie oben beschrieben [[Rekursion|rekursiv]] dessen weißer Nachbar betrachtet und grau gefärbt. Existiert kein weißer Nachbar mehr, kommt es zum [[Backtracking]], während dessen alle durchwanderten Knoten schwarz gefärbt werden.<ref>{{Literatur |Autor=Thomas H. Cormen, [[Charles Leiserson]], [[Ronald L. Rivest]], Clifford Stein |Titel=Algorithmen – Eine Einführung |Auflage=3 |Verlag=Oldenbourg Wissenschaftsverlag |Ort=München |Datum=2010 |ISBN=978-3-486-59002-9 |Seiten=613–622}}</ref>

'''DFS'''(G)
'''for each''' v of G // Alle Knoten weiß färben, Vorgänger auf nil setzen
{
col[v] = 'w';
pi[v] = nil;
}
time = 0;
'''for each''' u of G // Für alle weißen Knoten: DFS-visit aufrufen
{
if col[u] == 'w'
DFS-visit(u);
}

'''DFS-visit'''(u)
1 col[u] = 'g'; // Aktuellen Knoten grau färben
2 time++; // Zeitzähler erhöhen
3 d[u] = time; // Entdeckzeit des aktuellen Knotens setzen
4 '''for each''' v of Adj[u] // Für alle weißen Nachbarn des aktuellen Knotens
5 {
6 '''if''' col[v] == 'w'
7 {
8 pi[v] = u; // Vorgänger auf aktuellen Knoten setzen
9 DFS-visit(v); // DFS-visit aufrufen
10 }
11 '''if''' col[v] == 'g'
12 {
13 // Zyklus entdeckt
14 }
15 }
16 col[u] = 's'; // Aktuellen Knoten schwarz färben
17 time++;
18 f[u] = time; // Finishing-Time des aktuellen Knotens setzen
Den [[Zeitstempel]] (siehe Zeilen 2, 17, 18) kann man weiterhin für eine [[topologische Sortierung]] verwenden. Nachdem ein [[Knoten (Graphentheorie)|Knoten]] schwarz gefärbt wurde, wird er einer [[Liste (Datenstruktur)|Liste]], absteigend nach den Werten f[u] für die Zeitstempel, hinzugefügt und man erhält eine topologische Reihenfolge. Wird ein [[Zyklus (Graphentheorie)|Zyklus]] (siehe Zeile 9) entdeckt, ist dies nicht mehr möglich.

== Programmierung ==
Das folgende Beispiel in der [[Programmiersprache]] [[C-Sharp|C#]] zeigt die Implementierung der Tiefensuche für einen [[Gerichteter Graph|gerichteten Graphen]]. Der gerichtete Graph wird als [[Klasse (Objektorientierung)|Klasse]] ''DirectedGraph'' deklariert. Die Methode ''DepthFirstSearch'', die die Knoten durchläuft und in einer [[Liste (Datenstruktur)|Liste]] speichert, verwendet einfache [[Rekursive Programmierung|Rekursion]]. Bei der Ausführung des Programms wird die [[Methode (Programmierung)|Methode]] ''Main'' verwendet, die die Liste der markierten Knoten auf der Konsole ausgibt.<ref name=":0">GeeksforGeeks: [https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/ Depth First Search or DFS for a Graph]</ref><syntaxhighlight lang="c#">
using System;
using System.Collections.Generic;

// Deklariert die Klasse für die Knoten des Graphen
class Node
{
public int index;
public string value;
public List<Node> adjacentNodes = new List<Node>(); // Liste der Nachbarknoten
}

// Deklariert die Klasse für den gerichteten Graphen
class DirectedGraph
{
// Diese Methode verbindet die Knoten startNode und targetNode miteinander.
public void ConnectNodes(Node startNode, Node targetNode)
{
startNode.adjacentNodes.Add(targetNode);
}
}

class Program
{
// Diese Methode gibt die Liste der Knoten in der Form A, B, C, ... als Text zurück.
public static string ToString(List<Node> traversedNodes)
{
string text = "";
for (int i = 0; i < traversedNodes.Count; i++) // for-Schleife, die die Knoten durchläuft
{
text += traversedNodes[i].value + ", ";
}
text = text.Substring(0, text.Length - 2);
return text;
}

// Diese Methode durchläuft die Knoten des gerichteten Graphen mit einer Tiefensuche
public static void DepthFirstSearch(Node startNode, List<Node> traversedNodes)
{
traversedNodes.Add(startNode); // Fügt den aktuellen Knoten der Menge der markierten Knoten hinzu
foreach (Node node in startNode.adjacentNodes) // foreach-Schleife, die alle benachbarten Knoten des Knotens durchläuft
{
if (!traversedNodes.Contains(node)) // Wenn der Knoten noch nicht markiert wurde
{
DepthFirstSearch(node, traversedNodes); // Rekursiver Aufruf der Methode mit dem Nachbarknoten als Startknoten
}
}
}

// Hauptmethode, die das Programm ausführt
public static void Main(String[] args)
{
// Deklariert und initialisiert 4 Knoten
Node node1 = new Node{index = 0, value = "A"};
Node node2 = new Node{index = 1, value = "B"};
Node node3 = new Node{index = 2, value = "C"};
Node node4 = new Node{index = 3, value = "D"};

// Erzeugt einen gerichteten Graphen
DirectedGraph directedGraph = new DirectedGraph();

// Verbindet Knoten des Graphen miteinander
directedGraph.ConnectNodes(node1, node2);
directedGraph.ConnectNodes(node1, node3);
directedGraph.ConnectNodes(node2, node3);
directedGraph.ConnectNodes(node3, node1);
directedGraph.ConnectNodes(node3, node4);
directedGraph.ConnectNodes(node4, node4);

List<Node> traversedNodes = new List<Node>(); // Liste der Knoten für die Tiefensuche
DepthFirstSearch(node3, traversedNodes); // Aufruf der Methode
Console.WriteLine(ToString(traversedNodes)); // Ausgabe auf der Konsole

Console.ReadLine();
}
}
</syntaxhighlight>'''Hinweise''': Für die Nachbarknoten wurde eine [[Liste (Datenstruktur)|Liste]] als [[Datentyp]] verwendet, damit die Reihenfolge der durchlaufenen [[Knoten (Graphentheorie)|Knoten]] eindeutig ist und die Knoten in allen Ebenen von links nach rechts durchlaufen werden. Für den Datentyp [[Menge (Datenstruktur)|Menge]] zum Beispiel muss das nicht der Fall sein. Statt dem ''HashSet'' ([[Menge (Datenstruktur)|Menge]]) ''visitedNodes'' kann auch eine Liste oder ein Array vom Typ ''bool'' ([[Boolesche Variable]]) verwendet werden, wie im Einzelnachweis gezeigt.<ref name=":0" />

== Eigenschaften ==
Im Folgenden werden [[Speicherbedarf]] und [[Laufzeit (Informatik)|Laufzeit]] des Algorithmus in [[Landau-Symbole|Landau-Notation]] angegeben. Wir gehen außerdem von einem [[Gerichteter Graph|gerichteten Graphen]] aus.

=== Speicherplatz ===
Der [[Speicherbedarf]] des [[Algorithmus]] wird ohne den [[Speicherplatz]] für den [[Graph (Graphentheorie)|Graphen]], wie er übergeben wird, angegeben, denn dieser kann in verschiedenen Formen mit unterschiedlichem Speicherbedarf vorliegen, z. B. als [[verkettete Liste]], als [[Adjazenzmatrix]] oder als [[Inzidenzmatrix]].

Für die oben beschriebene Prozedur ''DFS(G)'' werden zunächst alle [[Knoten (Graphentheorie)|Knoten]] weiß gefärbt und die Referenzen für deren [[Vorgänger (Mathematik)|Vorgänger]] entfernt. Diese Informationen benötigt also für jeden Knoten konstanten [[Speicherplatz]], also <math>\mathcal{O}(1)</math>. Insgesamt ergibt sich ein linearer Speicherbedarf von <math>\mathcal{O}(\vert V \vert)</math>, abhängig von der Anzahl der Knoten <math>\vert V \vert</math> (englisch ''vertices''). Der Speicherbedarf der [[Variable (Programmierung)|Variable]] ''time'' ist mit konstantem <math>\mathcal{O}(1)</math> gegenüber <math>\mathcal{O}(\vert V \vert)</math> vernachlässigbar. Anschließend wird für jeden Knoten ''u'' die Prozedur ''DFS-visit(u)'' aufgerufen. Da es sich hierbei nur um Kontrollstrukturen handelt, tragen sie nicht zum Speicherbedarf bei.

Die Prozedur DFS-visit(u) arbeitet auf der bereits aufgebauten Speicherstruktur, in der alle [[Knoten (Graphentheorie)|Knoten]] abgelegt sind, und erweitert diese pro Knoten noch um die Entdeckzeit und die Finishing-Time, jeweils konstant <math>\mathcal{O}(1)</math>. Das ändert nichts am bisherigen linearen Speicherbedarf <math>\mathcal{O}(\vert V \vert)</math>. Da sonst in DFS-visit(u) keine weiteren Variablen mehr eingeführt werden, hat die Tiefensuche einen Speicherbedarf von <math>\mathcal{O}(\vert V \vert)</math>.

=== Laufzeit ===
Falls der Graph als [[Adjazenzliste]] gespeichert wurde, müssen im [[Worst Case]] alle möglichen [[Pfad (Graphentheorie)|Pfade]] zu allen möglichen [[Knoten (Graphentheorie)|Knoten]] betrachtet werden. Damit beträgt die [[Zeitkomplexität|Laufzeit]] von Tiefensuche <math>\mathcal{O}(\vert V \vert + \vert E \vert)</math>, wobei <math> \vert V \vert </math> für die Anzahl der Knoten und <math> \vert E \vert </math> für die Anzahl der [[Kante (Graphentheorie)|Kanten]] im [[Graph (Graphentheorie)|Graph]] stehen.<ref>{{Literatur |Autor=Thomas Ottmann, Peter Widmayer |Titel=Algorithmen und Datenstrukturen |Auflage=5 |Verlag=Spektrum Akademischer Verlag |Ort=Heidelberg |Datum=2012 |ISBN=978-3-8274-2803-5 |Seiten=589-668}}</ref>

=== Vollständigkeit ===
Falls ein [[Graph (Graphentheorie)|Graph]] unendlich groß ist oder kein Test auf [[Zyklus (Graphentheorie)|Zyklen]] durchgeführt wird, so ist die Tiefensuche nicht vollständig. Es kann also sein, dass ein Ergebnis – obwohl es existiert – nicht gefunden wird.

=== Optimalität ===
Tiefensuche ist insbesondere bei [[Monoton steigende Funktion|monoton steigenden]] Pfadkosten nicht optimal, da eventuell ein Ergebnis gefunden wird, zu welchem ein sehr viel längerer [[Pfad (Graphentheorie)|Pfad]] führt als zu einem alternativen Ergebnis. Dafür wird ein solches Ergebnis im Allgemeinen deutlich schneller gefunden als bei der in diesem Fall optimalen, aber sehr viel speicheraufwendigeren [[Breitensuche]]. Als Kombination von Tiefen- und Breitensuche gibt es die [[iterative Tiefensuche]].

== Anwendungen ==
[[Datei:MAZE 30x20 DFS.ogv|mini|[[Algorithmus]], der Tiefensuche verwendet, um einen [[Irrgarten]] zu erzeugen.]]
Die Tiefensuche ist indirekt an vielen komplexeren [[Algorithmus|Algorithmen]] für [[Graph (Graphentheorie)|Graphen]] beteiligt. Beispiele:

* Das Auffinden aller [[Starke Zusammenhangskomponente|starken Zusammenhangskomponenten]] eines Graphen.
* Das Ermitteln von 2-[[Zusammenhängender Graph|zusammenhängenden]] Komponenten.
* Das Ermitteln von 3-zusammenhängenden Komponenten.
* Das Ermitteln der [[Brücke (Graphentheorie)|Brücken]] eines Graphen.
* Einen Graphen testen, ob er ein [[planarer Graph]] ist.<ref>{{cite journal
| last1 = Hopcroft | first1 = John
| last2 = Tarjan | first2 = Robert E.
| doi = 10.1145/321850.321852
| issue = 4
| journal = [[Journal of the ACM|Journal of the Association for Computing Machinery]]
| pages = 549–568
| title = Efficient planarity testing
| volume = 21
| year = 1974
}}</ref><ref>{{cite journal
| last1 = de Fraysseix | first1 = H.
| last2 = Ossona de Mendez | first2 = P.
| last3 = Rosenstiehl | first3 = P.
| journal = International Journal of Foundations of Computer Science
| pages = 1017–1030
| title = Trémaux Trees and Planarity
| volume = 17
| year = 2006
| doi = 10.1142/S0129054106004248
| issue = 5| arxiv=math/0610935}}</ref>
* Bei einem [[Baum (Graphentheorie)|Baum]], der Abhängigkeiten darstellt, ergeben die sortierten finish-Zeiten (siehe [[Pseudocode]] oben) eine invers-[[topologische Sortierung]].
* Mit der Tiefensuche kann man Graphen in [[Laufzeit (Informatik)|Laufzeit]] <math>\mathcal{O}(\vert V \vert + \vert E \vert)</math> auf [[Kreis (Graphentheorie)|Kreise]] testen und im Falle von Kreisen die dazugehörige Kantenfolge ausgeben.<ref name="Krumke2012">{{Literatur |Autor=Sven Oliver Krumke, Hartmut Noltemeier |Titel=Graphentheoretische Konzepte und Algorithmen |Auflage=3 |Verlag=Springer Vieweg |Ort=Wiesbaden |Datum=2012 |ISBN=978-3-8348-1849-2 |Seiten=152-157}}</ref>
* Ein kreisfreier Graph kann mit der Tiefensuche in [[Laufzeit (Informatik)|Laufzeit]] <math>\mathcal{O}(\vert V \vert + \vert E \vert)</math> [[Topologische Sortierung|topologisch sortiert]] werden.<ref name="Krumke2012" />

* Das Lösen von Rätseln mit nur einer Lösung, z. B. [[Irrgarten|Irrgärten]]. Die Tiefensuche kann angepasst werden, um alle Lösungen für einen Irrgarten zu finden, indem nur [[Knoten (Graphentheorie)|Knoten]] auf dem aktuellen [[Pfad (Graphentheorie)|Pfad]] in die besuchte Menge aufgenommen werden.
* Für das Erzeugen eines [[Irrgarten]]s kann eine zufällige Tiefensuche verwendet werden.

== Literatur ==
* [[Stuart Russell]], [[Peter Norvig]]: [http://aima.cs.berkeley.edu/ ''Artificial Intelligence: A Modern Approach''.] 2. Auflage. Prentice Hall, 2002.
* Sven Oliver Krumke, Hartmut Noltemeier: ''Graphentheoretische Konzepte und Algorithmen''. 3. Auflage. Springer Vieweg, 2012, ISBN 978-3-8348-1849-2

== Weblinks ==
{{Commonscat|Depth-first search|Tiefensuche}}
{{Wikibooks|Algorithmensammlung: Graphentheorie: Tiefensuche|Tiefensuche|suffix=Implementierungen in der Algorithmensammlung}}
* [https://www-i1.informatik.rwth-aachen.de/~algorithmus/algo5.php Anschauliche Erklärung der Tiefensuche am Beispiel eines Labyrinths]

== Einzelnachweise ==
<references />

[[Kategorie:Graphsuchalgorithmus]]
[[Kategorie:Wikipedia:Artikel mit Video]]

Tiefensuche - Versionsgeschichte

imported>YMS: Sprache