Tiefensuche

Ein Beispielgraph

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.

Stack mit den noch nicht besuchten bekannten Nachbarn: B, C.

Stack mit den noch nicht besuchten bekannten Nachbarn: C, D, E, C.

Stack mit den noch nicht besuchten bekannten Nachbarn: D, D, E, C.

Stack mit den noch nicht besuchten bekannten Nachbarn: E, D, E, C.

E wurde gefunden.

Algorithmen auf Graphen

Suche: Breitensuche | Tiefensuche

Kürzeste Wege: Dijkstra-Algorithmus | Bellman-Ford-Algorithmus

Minimale Spannbäume: Kruskal-Algorithmus | Prim-Algorithmus | Borůvka-Algorithmus