Tiefensuche
Die Tiefensuche ist ein Algorithmus, um ein Element in einem Graphen zu suchen, ohne irgendwelche Informationen über dessen Verbindungen zu anderen Knoten zu haben.
Der Algorithmus beginnt bei einem Startknoten, besucht zunächst einen seiner noch nicht besuchten Nachbarn, dann einen von dessen noch nicht besuchten Nachbarn, dann einen von dessen noch nicht besuchten Nachbarn usw., bis er an einen Knoten gerät, dessen Nachbarn alle schon besucht worden sind. Falls dies geschieht, wird die Kette von besuchten Knoten rückwärts abgearbeitet, bis ein Knoten mit noch unbesuchten Nachbarn gefunden wird. Über diesen wird wieder eine Tiefensuche durchgeführt, bis der ganze Graph abgearbeitet ist.
Die Liste der noch zu besuchenden Knoten kann bei der Breitensuche als Stack modelliert werden.
Die betrachteten Knoten und Kanten bilden nach dem Ende einer Tiefensuche einen Spannbaum mit dem Startknoten als Wurzel, allerdings nicht zwingend einen minimalen.
Beispiel
Das Objekt E soll vom Startknoten aus gefunden werden.
Weblinks
Suche: Breitensuche | Tiefensuche
Kürzeste Wege: Dijkstra-Algorithmus | Bellman-Ford-Algorithmus
Minimale Spannbäume: Kruskal-Algorithmus | Prim-Algorithmus | Borůvka-Algorithmus
