Ok, das ist mein erster Beitrag auf Stack Overflow. Ich lese seit einiger Zeit und bewundere die Seite wirklich. Ich hoffe, dass dies akzeptabel ist. Also habe ich die ganze Zeit über Intro to Algorithms (Cormen. MIT Press) gelesen und bin dabei, die Graphalgorithmen zu verstehen. Ich habe die formalen Algorithmen studiert, die für die Breite und Tiefe der ersten Suche in sehr feinen Details ausgelegt sind.
Hier ist der Pseudo-Code für die Tiefensuche:
%Vor%Dieser Algorithmus ist rekursiv und geht von mehreren Quellen aus (wird jeden Knoten im nicht verbundenen Graphen entdecken). Es verfügt über mehrere Eigenschaften, die bei den meisten sprachspezifischen Implementierungen fehlen. Es unterscheidet zwischen 3 verschiedenen "Farben" von Vertices. Es malt zunächst alle weiß, dann werden sie, wenn sie "entdeckt" werden (besucht in DFS-VISIT), grau dargestellt. Der DFS-VISIT-Algorithmus führt eine Schleife aus, die sich rekursiv auf der Adjazenzliste des aktuellen Eckpunkts aufruft und nur einen Eckpunkt schwarz zeichnet, wenn er keine Kanten mehr zu einem weißen Knoten hat.
Es werden auch zwei andere Attribute jedes Eckpunkts beibehalten. u.d und u.f sind die Zeitstempel bis zum Zeitpunkt, an dem der Eckpunkt entdeckt wurde (grau dargestellt) oder wenn ein Eckpunkt fertiggestellt ist (schwarz gezeichnet). Wenn ein Knoten zum ersten Mal gezeichnet wird, hat er einen Zeitstempel von eins und wird für jedes Mal, wenn ein anderer gemalt wird (egal ob grau oder schwarz), auf den nächsten ganzzahligen Wert erhöht. u.π wird ebenfalls beibehalten, was nur ein Zeiger auf den Knoten ist, von dem Sie entdeckt wurden.
%Vor%* EDIT 31.10.12 * Das ist peinlich, dass mein Algorithmus so lange falsch war, es würde in den meisten Fällen funktionieren, aber nicht alle. Ich habe gerade ein beliebtes Frageabzeichen für die Frage bekommen und ich habe gesehen, wo Irfy das Problem in seiner Antwort unten entdeckt hat. Ich repariere es hier nur für jeden, der das in Zukunft braucht.
Sieht jemand einen Fehler mit dem obigen Algorithmus? Ich bin bei weitem kein Experte für Graphentheorie, aber ich denke, dass ich Rekursion und Iteration ziemlich gut beherrsche und ich glaube, das sollte genauso funktionieren. Ich möchte es funktionell dem rekursiven Algorithmus gleichsetzen. Es sollte alle Attribute des ersten Algorithmus beibehalten, auch wenn sie nicht benötigt werden.
Als ich mit dem Schreiben anfing, dachte ich nicht, dass ich eine dreifache Schleife hätte, aber so wurde es. Ich habe andere iterative Algorithmen gesehen, als ich mich in Google umgeschaut habe, die nur eine doppelt verschachtelte Schleife haben, jedoch scheinen sie nicht von mehreren Quellen auszugehen. (d. h., sie werden nicht jeden Scheitelpunkt eines nicht verbundenen Graphen entdecken)
Beide Algorithmen sind in Ordnung. Die zweite ist eine direkte Übersetzung von rekursiv zu stack-basiert. Alle mutierenden Zustände sind im Stapel gespeichert. G ändert sich niemals während der Ausführung des Algorithmus.
Die Algorithmen erzeugen einen aufspannenden Baum für jede getrennte Region, basierend auf der Reihenfolge, in der der Algorithmus jeden Knoten besucht hat. Die Bäume werden sowohl mit Bezug auf die übergeordneten Knoten ( u.π ) als auch als Segmentbäume ( u.d und u.f ) dargestellt.
Ein untergeordnetes Objekt hat einen Verweis auf seinen übergeordneten Knoten (oder NULL , wenn es sich um ein Stammverzeichnis handelt) sowie über den Bereich ( child.d .. child.f ) im Bereich des übergeordneten Elements.
Bearbeiten: Ich habe einen Fehler in der Übersetzung gefunden. Sie schieben nicht wirklich den aktuellen Zustand in den Stapel, sondern ein zukünftiges Methodenargument. Darüber hinaus färben Sie nicht die Popup-Knoten GRAY und setzen das Feld f .
Hier ist eine Umschreibung des ursprünglichen ersten Algorithmus:
%Vor%Es gibt wahrscheinlich ein paar Stellen, die optimiert werden könnten, aber zumindest jetzt funktionieren sollten.
Ergebnis:
%Vor%Ich glaube, ich habe es geschafft, einen viel einfacheren Pseudocode zu schreiben.
aber zuerst ein paar Bemerkungen, um die Dinge ein wenig klar zu machen:
Der Algorithmus basiert auf der folgenden Beobachtung: Ein Scheitelpunkt wird beim Besuch in den Stapel geschoben. und entfernt (gepoppt) nur, wenn wir alle seine Nachkommen untersucht (schwärzen).
%Vor%Sie haben einen schwerwiegenden Fehler in Ihrem nicht-rekursiven Code.
Nachdem Sie überprüft haben, ob v WHITE ist, markieren Sie nie GRAY , bevor Sie pushen. Daher wird es immer wieder als WHITE von anderen nicht besuchten Knoten angezeigt, was zu mehreren Verweisen auf diese% co_de führt % Knoten, der zum Stapel geschoben wurde. Dies ist möglicherweise ein katastrophaler Fehler (könnte Endlosschleifen oder ähnliches verursachen).
Außerdem setzen Sie v nicht für Root-Knoten. Dies bedeutet, dass die geschachtelten Mengenmodelle Attribute .d s und .d s nicht korrekt sind. (Wenn Sie nicht wissen, was .f s und .d s sind, lesen Sie diesen Artikel, es war sehr aufschlussreich für mich in den Tagen. Der .f des Artikels ist Ihre left und .d ist Ihr right .)
Ihre innere .f muss im Grunde die gleiche sein wie die äußere if minus die Schleifen, plus die Elternreferenz. Das ist:
Korrigiere das und es sollte ein echtes Äquivalent sein.
In der nicht-rekursiven Version benötigen wir eine andere Farbe, die den Zustand im rekursiven Stapel widerspiegelt. Also fügen wir eine Farbe = RED hinzu, um anzuzeigen, dass alle Kinder des Knotens auf den Stapel geschoben wurden. Ich nehme auch an, dass der Stack eine peek () -Methode hat (die sonst mit pop und sofort push simuliert werden könnte)
Daher sollte die aktualisierte Version des ursprünglichen Posts wie folgt aussehen:
%Vor%Ich glaube, dass es mindestens einen Fall gibt, in dem die rekursive und die Stapelversion nicht funktional äquivalent sind. Betrachten wir den Fall eines Dreiecks - die Knoten A, B und C, die miteinander verbunden sind. Mit dem rekursiven DFS wäre nun der Vorgängergraph, den man mit der Quelle A erhalten würde, entweder A- & gt; B- & gt; C OR A- & gt; C- & gt; B (A- & gt; B bedeutet A ist der Elternteil von B in der Tiefe ersten Baum).
Wenn Sie jedoch die Stack-Version von DFS, Eltern von sowohl B als auch C, verwenden, wird immer als A aufgezeichnet. Es kann niemals der Fall sein, dass Eltern von B C ist oder umgekehrt (was immer der Fall ist) für rekursives DFS). Dies liegt daran, dass wir bei der Untersuchung der Adjazenzliste eines beliebigen Eckpunkts (hier A) alle Mitglieder der Adjazenzliste (hier B und C) auf einmal durchgehen .
Dies kann relevant werden, wenn Sie versuchen, mit Hilfe von DFS Artikulationspunkte in einer Grafik zu finden [1]. Ein Beispiel wäre, dass die folgende Aussage nur gilt, wenn wir die rekursive Version von DFS verwenden.
Ein Wurzelknoten ist genau dann ein Artikulationspunkt, wenn er mindestens zwei Kinder im Tiefenbaum.
In einem Dreieck gibt es offensichtlich keinen Artikulationspunkt, aber das Stack-DFS gibt immer noch zwei untergeordnete Elemente für jeden Quellknoten im Depth-First-Baum (A hat Kinder B und C). Nur wenn wir den Depth-First-Tree mit rekursivem DFS erstellen, gilt die obige Aussage als richtig.
[1] Einführung in die Algorithmen, CLRS - Problem 22-2 (Zweite und Dritte Ausgabe)
Tags und Links algorithm graph-algorithm graph depth-first-search