Tiefensuche (DFS)
Gehen Sie in ein Labyrinth, laufen Sie weiter, bis Sie in einer Sackgasse stehen, gehen Sie dann zur letzten Abzweigung zurück und versuchen Sie den nächsten Weg. Genauso erkundet die Tiefensuche einen Graphen. Sie ist einer der einfachsten Graphalgorithmen, und ihr Stapel verrät mehr, als man erwarten würde.
Die Idee
Ein Graph ist eine Menge von Knoten, die durch Kanten verbunden sind: Räume und Türen, Webseiten und Links, Aufgaben und die Aufgaben, von denen sie abhängen. Die Tiefensuche besucht jeden Knoten, den sie von einem Start aus erreichen kann, aber in einer bestimmten Reihenfolge: Sie macht immer bei dem Knoten weiter, den sie zuletzt erreicht hat. Dazu führt sie einen Stapel der Knoten, in denen sie gerade steckt. Ein neuer Knoten kommt oben drauf, und ein Knoten kommt erst wieder herunter, wenn alles um ihn herum erkundet ist.
Schritt für Schritt
Legen Sie den Start auf den Stapel und geben Sie ihm die Besuchsnummer 1. Betrachten Sie den nächsten Nachbarn des obersten Knotens. Wurde er noch nicht gesehen, geben Sie ihm die nächste Besuchsnummer, merken Sie sich den Knoten, von dem er erreicht wurde, und legen Sie ihn oben auf den Stapel. Wurde er schon gesehen, überspringen Sie ihn. Hat der oberste Knoten keine Nachbarn mehr zu prüfen, ist er abgeschlossen: Nehmen Sie ihn herunter und machen Sie mit dem Knoten darunter weiter. Hören Sie auf, wenn der Stapel leer ist oder das Ziel erreicht ist.
Ein Beispiel
Nehmen Sie einen Graphen mit den Kanten A–B, A–C, B–D, C–D, C–E und D–F, starten Sie bei A und prüfen Sie die Nachbarn in alphabetischer Reihenfolge. Von A geht die Suche zu B, von B zu D, von D zu C und von C zu E, also ist der Stapel A, B, D, C, E. Unterwegs sieht C den Knoten A, der noch auf dem Stapel liegt: Die Kante C–A schließt den Zyklus A, B, D, C. E hat nichts Neues, also ist E abgeschlossen, dann C, und die Suche geht zurück zu D, wo noch F wartet. Die Besuchsreihenfolge ist A, B, D, C, E, F. Mit E als Ziel endet die DFS mit dem Weg A → B → D → C → E, vier Kanten, obwohl A → C → E nur zwei braucht.
Wofür sie gut ist
Der Stapel ist immer ein Weg vom Start zum aktuellen Knoten, deshalb passt die DFS gut zu Labyrinthen und Rätseln: Sie ist die Idee hinter dem Backtracking. In einem ungerichteten Graphen schließt eine Kante zu einem Knoten, der noch auf dem Stapel liegt, einen Zyklus. In einem gerichteten Graphen ergibt die Liste der Knoten in umgekehrter Reihenfolge ihres Abschlusses eine topologische Ordnung, sodass jede Aufgabe nach den Aufgaben kommt, von denen sie abhängt. Die Tiefensuche findet auch Zusammenhangskomponenten, Brücken und Artikulationspunkte, und ihre zufällige Variante ist ein klassischer Weg, Labyrinthe zu erzeugen.
Geschichte
Im 19. Jahrhundert beschrieb der französische Mathematiker Charles Pierre Trémaux eine Methode, aus jedem Labyrinth herauszufinden, indem man Gänge markiert: eine Tiefensuche mit Kreide. 1972 und 1973 zeigten Robert Tarjan und John Hopcroft, dass die DFS viele Graphenprobleme in linearer Zeit löst, von starken Zusammenhangskomponenten bis zum Test, ob sich ein Graph ohne Kreuzungen zeichnen lässt. Unter anderem für diese Arbeit erhielten sie 1986 den Turing Award.
Ausprobieren
Öffnen Sie die App und drücken Sie Schritt. Der Knoten, dessen Nachbarn gerade geprüft werden, ist hervorgehoben, Knoten auf dem Stapel sind blau und abgeschlossene Knoten grün, jeder mit seiner Besuchsnummer. Der Stapel wird unter dem Graphen angezeigt, vom Start bis zum obersten Knoten. Achten Sie in der Statuszeile auf die Kanten, die einen Zyklus schließen, und wählen Sie ein Ziel, um zu sehen, wie lang der gefundene Weg im Vergleich zur Breitensuche sein kann.
Häufig gestellte Fragen
Welche Zeitkomplexität hat die DFS?
O(V + E) für V Knoten (englisch vertices) und E Kanten (edges): Jeder Knoten kommt einmal auf den Stapel und wieder herunter, und jede Kante wird von beiden Enden aus geprüft. Für den Stapel und die Markierungen braucht sie O(V) zusätzlichen Speicher.
Warum nutzt die DFS einen Stapel?
Weil beim Stapel das, was zuletzt hineinkommt, zuerst herauskommt: So macht die Suche beim neuesten Knoten weiter und geht danach zum vorigen zurück. Rekursion macht dasselbe mit dem Aufrufstapel des Programms. Mit einer Warteschlange stattdessen würde sich die Suche Ring für Ring ausbreiten: Das ist die Breitensuche.
Ist eine rekursive DFS ein Problem für große Graphen?
Das kann sein: Ein langer Weg bedeutet tiefe Rekursion, und viele Sprachen begrenzen, wie tief Aufrufe gehen können. Ein expliziter Stapel in einer Schleife umgeht diese Grenze und besucht die Knoten in derselben Reihenfolge.
Wo wird die DFS eingesetzt?
Beim Lösen von Labyrinthen und Rätseln durch Backtracking, beim Finden von Zyklen, beim Ordnen von Aufgaben nach ihren Abhängigkeiten (topologische Sortierung), beim Finden von Zusammenhangskomponenten und starken Zusammenhangskomponenten, beim Erzeugen von Labyrinthen und in Compilern und Build-Werkzeugen, die Abhängigkeitsgraphen durchlaufen.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Tiefensuche ausprobieren