- Aktuell
- Auf dem Stapel
- Abgeschlossen
- Weg
Tiefensuche (DFS)
Die Tiefensuche erkundet einen Graphen wie jemand, der mit einer Hand an der Wand durch ein Labyrinth geht: Sie folgt einem Weg, so weit er führt, und geht erst zurück, wenn es nichts Neues mehr gibt. Dafür nutzt sie einen Stapel. Klicken Sie auf einen Knoten, um dort zu starten, wählen Sie bei Bedarf ein Ziel, und gehen Sie die Suche Schritt für Schritt durch: Sie sehen, wie der Stapel wächst und schrumpft, wie jeder Knoten seine Besuchsnummer bekommt und welche Kanten einen Zyklus schließen. Drücken Sie Abspielen, um der Suche zuzusehen, oder Schritt und Zurück, um Schritt für Schritt vorzugehen. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Klicken Sie auf einen Knoten, um ihn zum Start zu machen; stellen Sie den Klick auf Ziel um und klicken Sie auf einen anderen Knoten, um einen Weg dorthin zu suchen. Die Zahl auf jedem Knoten gibt an, als wievielter er besucht wurde, und die Reihe unter dem Graphen ist der Stapel, vom Start bis zum obersten Knoten. Neuer Graph erzeugt einen anderen Graphen; wählen Sie, wie viele Knoten und Kanten er hat. Wenn das Feld ausgewählt ist, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.
Wie es funktioniert
- Klicken Sie auf einen Knoten, um ihn zum Start zu machen. Um einen Weg zu suchen, stellen Sie den Klick auf Ziel um und klicken Sie auf einen anderen Knoten.
- Drücken Sie Abspielen, oder gehen Sie mit Schritt und Zurück schrittweise vor. Ziehen Sie den Schrittregler, um an eine beliebige Stelle der Suche zu springen.
- Beobachten Sie den Stapel unter dem Graphen und die Besuchsnummer auf jedem Knoten. Neuer Graph erzeugt einen anderen Graphen zum Ausprobieren.
So funktioniert die Tiefensuche
Legen Sie den Startknoten auf den Stapel. Dann wiederholen Sie: Betrachten Sie den nächsten Nachbarn des obersten Knotens auf dem Stapel. Ein Nachbar, der noch nicht gesehen wurde, bekommt die nächste Besuchsnummer, merkt sich den Knoten, von dem er erreicht wurde, und kommt oben auf den Stapel, sodass die Suche dort weitermacht. Hat der oberste Knoten keine Nachbarn mehr zu prüfen, ist er abgeschlossen und kommt vom Stapel, und die Suche geht zum Knoten darunter zurück. Ist der Stapel leer, wurde jeder erreichbare Knoten besucht.
Was der Stapel verrät
Weil die Suche immer beim neuesten Knoten weitermacht, ist der Stapel immer ein Weg vom Start zum gerade betrachteten Knoten. Wird das Ziel erreicht, ist der Stapel ein Weg dorthin, meist aber nicht der kürzeste: Den findet die Breitensuche. In einem ungerichteten Graphen schließt eine Kante zu einem Knoten, der noch auf dem Stapel liegt, einen Zyklus, sofern es nicht der Knoten ist, von dem man gerade kam. Die gemerkten Knoten bilden einen Baum, den Tiefensuchbaum, und die Reihenfolge, in der die Knoten abgeschlossen werden, ist der Schlüssel zur topologischen Sortierung.
Häufig gestellte Fragen
Was ist die Tiefensuche?
Eine Methode, einen Graphen von einem Startknoten aus zu erkunden: Sie folgt einem Weg so tief wie möglich und geht erst zurück, um einen anderen Zweig zu versuchen, wenn es nichts Neues mehr gibt. Sie nutzt einen Stapel oder Rekursion, um sich den Rückweg zu merken.
Findet die Tiefensuche den kürzesten Weg?
Nein. Sie findet einen Weg zum Ziel, wenn es einen gibt, aber dieser Weg kann viel länger als nötig sein, weil sich die DFS auf den ersten Zweig festlegt, den sie versucht. Für die wenigsten Kanten nehmen Sie die Breitensuche, und wenn Kanten Längen haben, den Dijkstra-Algorithmus.
Was ist der Unterschied zwischen DFS und BFS?
Die Tiefensuche nutzt einen Stapel und geht einen Weg tief entlang, bevor sie zurückgeht. Die Breitensuche nutzt eine Warteschlange und breitet sich gleichmäßig aus, Ring für Ring. Beide besuchen jeden erreichbaren Knoten in einer Zeit, die mit der Zahl der Knoten plus Kanten wächst; die BFS findet kürzeste Wege, während die DFS die natürliche Wahl für Zyklen, Labyrinthe und topologische Sortierung ist.
Wie findet die DFS einen Zyklus?
Wenn die Suche in einem ungerichteten Graphen auf eine Kante zu einem Knoten trifft, der noch auf dem Stapel liegt, und dieser Knoten nicht der ist, von dem sie gerade kam, schließt die Kante einen Zyklus. In der App meldet das die Statuszeile, wenn es passiert.
Wird mein Graph irgendwohin gesendet?
Nein. Der Graph wird in Ihrem Browser erzeugt und durchsucht, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor