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.
- Zeit O(V + E)
- Speicher O(V)
- nutzt einen Stapel
Was bedeutet das?
- 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.
- Warteschlange: Wer zuerst kommt, geht zuerst. BFS nimmt immer den Knoten, der am längsten gewartet hat.
- Stapel: Was zuletzt hinzukommt, geht zuerst. DFS macht immer beim zuletzt erreichten Knoten weiter.
- 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.
- auf dem Stapel
- aktuell
- erledigt
- Kante des Suchbaums
- übersprungene Kante
Start bei A. Auf Abspielen drücken oder die Suche Schritt für Schritt durchgehen.
Leertaste: abspielen oder pausieren. Pfeiltasten links/rechts: Schritt. Pos1 und Ende: springen.
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.