Angenommen, Sie wollten eine Breitensuche eines Binärbaums rekursiv implementieren . Wie würden Sie vorgehen?
Ist es möglich, nur den Call-Stack als Zusatzspeicher zu verwenden?
Angenommen, Sie wollten eine Breitensuche eines Binärbaums rekursiv implementieren . Wie würden Sie vorgehen?
Ist es möglich, nur den Call-Stack als Zusatzspeicher zu verwenden?
Antworten:
(Ich gehe davon aus, dass dies nur eine Art Gedankenübung oder sogar eine Trick-Hausaufgabe / Interview-Frage ist, aber ich nehme an, ich könnte mir ein bizarres Szenario vorstellen, in dem Ihnen aus irgendeinem Grund kein Haufenplatz erlaubt ist [ein wirklich schlechter Brauch Speichermanager - einige bizarre Laufzeit- / Betriebssystemprobleme?], während Sie noch Zugriff auf den Stack haben ...)
Beim Durchlaufen der Breite zuerst wird traditionell eine Warteschlange verwendet, kein Stapel. Die Art einer Warteschlange und eines Stapels ist ziemlich gegensätzlich. Daher ist der Versuch, den Aufrufstapel (der ein Stapel ist, daher der Name) als Hilfsspeicher (eine Warteschlange) zu verwenden, zum Scheitern verurteilt, es sei denn, Sie tun dies etwas dumm Lächerliches mit dem Call Stack, das du nicht sein solltest.
Aus dem gleichen Grund fügt die Art jeder Nicht-Schwanz-Rekursion, die Sie zu implementieren versuchen, im Wesentlichen dem Algorithmus einen Stapel hinzu. Dies führt dazu, dass die erste Suche in einem Binärbaum nicht mehr breit ist und somit die Laufzeit und so weiter für traditionelles BFS nicht mehr vollständig gilt. Natürlich können Sie jede Schleife immer trivial in einen rekursiven Aufruf verwandeln, aber das ist keine sinnvolle Rekursion.
Es gibt jedoch Möglichkeiten, wie von anderen gezeigt, um etwas zu implementieren, das der Semantik von BFS folgt. Wenn die Vergleichskosten teuer sind, die Knotenüberquerung jedoch billig ist, können Sie wie bei @Simon Buchan einfach eine iterative Tiefensuche durchführen und nur die Blätter verarbeiten. Dies würde bedeuten, dass keine wachsende Warteschlange im Heap gespeichert ist, sondern nur eine lokale Tiefenvariable, und dass Stapel auf dem Aufrufstapel immer wieder aufgebaut werden, wenn der Baum immer wieder durchlaufen wird. Und wie @Patrick bemerkte, wird ein Binärbaum, der von einem Array unterstützt wird, normalerweise ohnehin in der Reihenfolge der Breite zuerst durchlaufen, sodass eine Suche in der Breite zuerst trivial wäre, auch ohne dass eine zusätzliche Warteschlange erforderlich wäre.
quelle
Wenn Sie ein Array zum Sichern des Binärbaums verwenden, können Sie den nächsten Knoten algebraisch bestimmen. Wenn
i
es sich um einen Knoten handelt, befinden sich seine untergeordneten Knoten unter2i + 1
(für den linken Knoten) und2i + 2
(für den rechten Knoten). Der nächste Nachbar eines Knotens ist gegeben durchi + 1
, esi
sei denn, es handelt sich um eine Potenz von2
Hier ist der Pseudocode für eine sehr naive Implementierung der Breitensuche in einem Array-gestützten binären Suchbaum. Dies setzt ein Array mit fester Größe und daher einen Baum mit fester Tiefe voraus. Es werden übergeordnete Knoten betrachtet und es kann ein unüberschaubar großer Stapel erstellt werden.
quelle
Ich konnte keinen Weg finden, dies vollständig rekursiv zu machen (ohne zusätzliche Datenstruktur). Wenn die Warteschlange Q jedoch als Referenz übergeben wird, können Sie die folgende rekursive Funktion für dumme Schwänze verwenden:
quelle
Bei der folgenden Methode wurde ein DFS-Algorithmus verwendet, um alle Knoten in einer bestimmten Tiefe abzurufen. Dies entspricht der Ausführung von BFS für diese Ebene. Wenn Sie die Tiefe des Baums herausfinden und dies für alle Ebenen tun, sind die Ergebnisse dieselben wie bei einem BFS.
Die Tiefe eines Baumes zu finden ist ein Kinderspiel:
quelle
level
Null ist.Eine einfache BFS- und DFS-Rekursion in Java: Drücken Sie einfach den Stammknoten
des Baums in den Stapel / die Warteschlange und rufen Sie diese Funktionen auf.
quelle
Ich fand einen sehr schönen rekursiven (sogar funktionalen) Breadth-First-Traversal-bezogenen Algorithmus. Nicht meine Idee, aber ich denke, es sollte in diesem Thema erwähnt werden.
Chris Okasaki erklärt seinen breitesten Nummerierungsalgorithmus aus ICFP 2000 unter http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html sehr deutlich mit nur 3 Bildern.
Die Scala-Implementierung von Debasish Ghosh, die ich unter http://debasishg.blogspot.de/2008/09/breadth-first-numbering-okasakis.html gefunden habe , lautet:
quelle
Der dumme Weg:
quelle
Hier ist eine kurze Scala- Lösung:
Die Idee , den Rückgabewert als Akkumulator zu verwenden, ist gut geeignet. Kann auf ähnliche Weise in anderen Sprachen implementiert werden. Stellen Sie nur sicher, dass Ihre rekursive Funktion die Liste der Knoten verarbeitet .
Auflistung der Testcodes (unter Verwendung des @ marco-Testbaums):
Ausgabe:
quelle
Hier ist eine Python-Implementierung:
quelle
Hier ist eine Scala 2.11.4-Implementierung von rekursivem BFS. Ich habe der Kürze halber die Tail-Call-Optimierung geopfert, aber die TCOd-Version ist sehr ähnlich. Siehe auch den Beitrag von @snv .
quelle
Das Folgende scheint mir mit Haskell ziemlich natürlich zu sein. Iterieren Sie rekursiv über Ebenen des Baums (hier sammle ich Namen in einer großen geordneten Zeichenfolge, um den Pfad durch den Baum anzuzeigen):
quelle
Hier ist eine rekursive BFS-Traversal-Python-Implementierung, die für ein Diagramm ohne Zyklus arbeitet.
quelle
Ich möchte meine Cent zur Top-Antwort hinzufügen , dass bfs rekursiv ausgeführt werden kann, wenn die Sprache so etwas wie Generator unterstützt.
Die Antwort von @ Tanzelax lautet zunächst:
In der Tat verhält sich der Stapel eines normalen Funktionsaufrufs nicht wie ein normaler Stapel. Die Generatorfunktion unterbricht jedoch die Ausführung der Funktion, sodass wir die Möglichkeit haben, die nächste Ebene der untergeordneten Knoten zu erhalten, ohne auf tiefere Nachkommen des Knotens einzugehen.
Der folgende Code ist rekursives bfs in Python.
Die Intuition hier ist:
quelle
Ich musste einen Heap-Traversal implementieren, der in einer BFS-Reihenfolge ausgegeben wird. Es ist eigentlich kein BFS, erfüllt aber die gleiche Aufgabe.
quelle
Sei v der Startpunkt
Sei G der fragliche Graph
Das Folgende ist der Pseudocode ohne Verwendung der Warteschlange
quelle
BFS für einen binären (oder n-ary) Baum kann wie folgt rekursiv ohne Warteschlangen ausgeführt werden (hier in Java):
Ein Beispiel für das Durchlaufen von Drucknummern 1-12 in aufsteigender Reihenfolge:
quelle
quelle
Hier ist eine JavaScript-Implementierung, die Breadth First Traversal mit Depth First-Rekursion vortäuscht. Ich speichere die Knotenwerte in jeder Tiefe innerhalb eines Arrays, innerhalb eines Hashs. Wenn bereits eine Ebene vorhanden ist (wir haben eine Kollision), drücken wir einfach auf das Array auf dieser Ebene. Sie können auch ein Array anstelle eines JavaScript-Objekts verwenden, da unsere Ebenen numerisch sind und als Array-Indizes dienen können. Sie können Knoten, Werte zurückgeben, in eine verknüpfte Liste konvertieren oder was auch immer Sie möchten. Der Einfachheit halber gebe ich nur Werte zurück.
Hier ist ein Beispiel für die tatsächliche erste Durchquerung der Breite unter Verwendung eines iterativen Ansatzes.
quelle
Das Folgende ist mein Code für die vollständig rekursive Implementierung der Breitensuche eines bidirektionalen Graphen ohne Verwendung von Schleife und Warteschlange.
quelle
C # -Implementierung eines rekursiven Breitensuchalgorithmus für einen Binärbaum.
Visualisierung von Binärbaumdaten
Wenn Sie möchten, dass der Algorithmus nicht nur mit dem Binärbaum, sondern auch mit Diagrammen funktioniert, die zwei und mehr Knoten haben können, die auf denselben anderen Knoten verweisen, müssen Sie das Selbstzyklus vermeiden, indem Sie die Liste der bereits besuchten Knoten halten. Die Implementierung sieht möglicherweise so aus.
Grafikdatenvisualisierung
quelle
Ich habe ein Programm mit c ++ erstellt, das auch in gemeinsamen und disjunkten Graphen funktioniert.
quelle