Tiefensuche (DFS)
Durchsucht einen Graphen, indem sie einem Weg so tief wie möglich folgt und dann zur letzten Abzweigung zurückgeht. Der Stapel auf dem Bildschirm ist genau dieser Weg.
- O(V + E)
- Speicher O(V)
- Stapel
V und E: die Anzahl der Knoten (vertices) und Kanten (edges). O(V + E) heißt: Jeder Knoten und jede Kante wird nur konstant oft bearbeitet.
Stapel: Was zuletzt hinzukommt, geht zuerst. DFS macht immer beim zuletzt erreichten Knoten weiter.
Weitere Begriffe auf dieser Seite
- Knoten: ein Punkt des Graphen, hier als Kreis mit einem Buchstaben gezeichnet.
- Kante: eine Linie, die zwei Knoten verbindet. Hier kann man sie in beide Richtungen entlanggehen.
- Nachbarn: die Knoten, die über eine Kante mit einem Knoten verbunden sind. Sie werden in alphabetischer Reihenfolge geprüft.
Probieren Sie es aus: Wählen Sie den Graphen mit Zyklen. Jede gestrichelte Kante führt zurück zu einem Knoten, der schon auf dem Stapel liegt oder erledigt ist: Diese Kante schließt einen Zyklus.
So funktioniert es
Die Tiefensuche ruft sich selbst für den ersten Nachbarn auf, den sie noch nicht gesehen hat, dann für dessen ersten neuen Nachbarn und so weiter. Hat ein Knoten keine neuen Nachbarn mehr, endet sein Aufruf, und die Suche geht einen Schritt zurück, um dort den nächsten Nachbarn zu probieren. Die offenen Aufrufe bilden einen Stapel, und dieser ist immer der Weg vom Start zum aktuellen Knoten. Die Zahl neben einem Knoten zeigt, als wievielter er besucht wurde.
Wann es sich eignet
Nutzen Sie die Tiefensuche, um herauszufinden, was überhaupt erreichbar ist, um Zyklen zu finden, um durch ein Labyrinth zu gehen oder um voneinander abhängige Aufgaben in eine Reihenfolge zu bringen. Den kürzesten Weg findet sie nicht.