Deutsch
Menü

Was ist Tiefensuche (Depth-First Search)?

Verfahren zum Durchsuchen eines Graphen oder Baums, das auf einem Pfad so weit wie möglich geht und bei einer Sackgasse zurückkehrt (Backtracking), um einen anderen Pfad zu versuchen. Es wird mit Rekursion oder einem Stack implementiert und für das Lösen von Labyrinthen, das Finden von Zusammenhangskomponenten und Zyklen sowie für die topologische Sortierung verwendet. Abgekürzt DFS.

Japanische Bezeichnung: 深さ優先探索

„Tiefensuche (Depth-First Search)“ kommt in 3 Übungsfragen aus 1 Themen vor, z. B. Datenstrukturen und Algorithmen.

Fachgebiet: Datenstrukturen und Algorithmen

Jetzt üben: Fragen zu Tiefensuche (Depth-First Search)

In einem ungerichteten Graphen sind die Nachbarn der Knoten A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Eine rekursive Tiefensuche beginnt bei Knoten A. Die Nachbarn werden in der angegebenen Reihenfolge geprüft, und sobald ein unbesuchter Knoten gefunden wird, geht die Suche zu ihm weiter. In welcher Reihenfolge werden die Knoten besucht?

  1. AA, B, C, D, E, F
  2. BA, B, D, E, C, F
  3. CA, B, D, E, F, C
Antwort und Erläuterung anzeigen

Antwort: C. A, B, D, E, F, C

Von A geht die Suche zu B und dann zu D, dem ersten unbesuchten Nachbarn von B. Der einzige Nachbar von D, nämlich B, ist bereits besucht; die Suche kehrt zu B zurück, geht weiter zu E, von E zum unbesuchten F und von F zu dessen Nachbarn C. Die Reihenfolge ist daher A, B, D, E, F, C. A, B, C, D, E, F ist die Reihenfolge der Breitensuche, die die nächstgelegenen Knoten zuerst besucht. A, B, D, E, C, F kehrt bei E um, ohne zum unbesuchten F zu gehen, und ist daher keine Reihenfolge einer Tiefensuche.

„Tiefensuche (Depth-First Search)“ in den Erläuterungen

Fragen mit „Tiefensuche (Depth-First Search)“ (3)

  1. In einem ungerichteten Graphen sind die Nachbarn der Knoten A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Eine rekursive Tiefensuche beginnt bei Knoten A. Die Nachbarn werden in der angegebenen Reihenfolge geprüft, und sobald ein unbesuchter Knoten gefunden wird, geht die Suche zu ihm weiter. In welcher Reihenfolge werden die Knoten besucht?
  2. In einem Graphen mit ungewichteten Kanten soll die kleinste Zahl von Kanten vom Startknoten zu jedem anderen Knoten bestimmt werden. Welche Kombination aus Suchverfahren und Datenstruktur ist geeignet?
  3. Für die Aufgaben A bis E gelten die Reihenfolgebedingungen „A vor C“, „B vor C“, „C vor D“, „B vor E“ und „E vor D“. Welche Reihenfolge erfüllt alle Bedingungen (ein Ergebnis der topologischen Sortierung)?

Verwandte Begriffe

Breitensuche (Breadth-First Search) Warteschlange (Queue) Rekursion Stack (Stapelspeicher) Binäre Suche (Binary Search) Binärer Heap (Binary Heap) Binärer Suchbaum (Binary Search Tree) Dijkstra-Algorithmus Dynamische Programmierung Greedy-Algorithmus

Zur Glossarübersicht