Was ist der Unterschied zwischen Breite zuerst und Tiefe zuerst, wenn Sie einen Baum / eine Grafik durchqueren? Alle Codierungs- oder Pseudocode-Beispiele wären großartig.
171
Was ist der Unterschied zwischen Breite zuerst und Tiefe zuerst, wenn Sie einen Baum / eine Grafik durchqueren? Alle Codierungs- oder Pseudocode-Beispiele wären großartig.
Antworten:
Diese beiden Begriffe unterscheiden zwischen zwei verschiedenen Arten, auf einem Baum zu laufen.
Es ist wahrscheinlich am einfachsten, nur den Unterschied aufzuzeigen. Betrachten Sie den Baum:
Eine Tiefe erste Traversal würde besuchen Sie die Knoten in dieser Reihenfolge
Beachten Sie, dass Sie ein Bein ganz nach unten gehen, bevor Sie weitermachen .
Eine breite erste Durchquerung würde den Knoten in dieser Reihenfolge besuchen
Hier arbeiten wir den ganzen Weg über jedes Level, bevor wir runter gehen.
(Beachten Sie, dass die Durchlaufreihenfolgen einige Unklarheiten aufweisen, und ich habe betrogen, um die "Lesereihenfolge" auf jeder Ebene des Baums beizubehalten. In beiden Fällen könnte ich vor oder nach C zu B gelangen, und ich könnte auch zu E vor oder nach F. Dies kann wichtig sein oder auch nicht, hängt von Ihrer Anwendung ab ...)
Beide Arten der Durchquerung können mit dem Pseudocode erreicht werden:
Der Unterschied zwischen den beiden Durchquerungsordnungen liegt in der Wahl von
Container
.Die rekursive Implementierung sieht so aus
Die Rekursion endet, wenn Sie einen Knoten erreichen, der keine untergeordneten Knoten hat. Sie endet also garantiert für endliche azyklische Diagramme.
Zu diesem Zeitpunkt habe ich noch ein wenig betrogen. Mit ein wenig Klugheit können Sie die Knoten auch in dieser Reihenfolge bearbeiten :
Dies ist eine Variation von Tiefe zuerst, bei der ich die Arbeit nicht an jedem Knoten erledige, bis ich wieder den Baum hinauf gehe. Ich habe jedoch besucht den höheren Knoten auf dem Weg nach unten , ihre Kinder zu finden.
Diese Durchquerung ist in der rekursiven Implementierung ziemlich natürlich (verwenden Sie die Zeile "Alternative Zeit" oben anstelle der ersten Zeile "Arbeit") und nicht zu schwer, wenn Sie einen expliziten Stapel verwenden, aber ich lasse es als Übung.
quelle
A, B, D, C, E, F
- das erste, das angezeigt wird), das Infix (D, B, A, E, C, F
- zum Sortieren verwendet: als AVL-Baum hinzufügen und dann das Infix lesen) oder das Postfix (D, B, E, F, C, A
die alternative präsentierte) Durchquerung zu erhalten. Die Namen werden durch die Position angegeben, an der Sie die Wurzel verarbeiten. Es ist zu beachten, dass Infix nur für Binärbäume wirklich Sinn macht. @batbrat das sind die Namen ... angesichts der Zeit, seit du gefragt hast, weißt du es wahrscheinlich schon.Die Begriffe verstehen:
Dieses Bild soll Ihnen eine Vorstellung davon geben, in welchem Kontext die Wörter Breite und Tiefe verwendet werden.
Tiefensuche:
Der Tiefensuchalgorithmus verhält sich so, als ob er so schnell wie möglich vom Startpunkt entfernt werden möchte.
Im Allgemeinen wird a verwendet, um sich
Stack
zu merken, wohin es gehen soll, wenn es eine Sackgasse erreicht.Zu befolgende Regeln: Schieben Sie den ersten Scheitelpunkt A auf den
Stack
Java-Code:
Anwendungen : Tiefensuchen werden häufig in Simulationen von Spielen (und spielähnlichen Situationen in der realen Welt) verwendet. In einem typischen Spiel können Sie eine von mehreren möglichen Aktionen auswählen. Jede Auswahl führt zu weiteren Auswahlmöglichkeiten, von denen jede zu weiteren Auswahlmöglichkeiten führt, und so weiter zu einem sich ständig erweiternden baumförmigen Diagramm von Möglichkeiten.
Breitensuche:
Queue
.Java-Code:
Anwendungen : Bei der Breitensuche werden zuerst alle Scheitelpunkte gefunden, die eine Kante vom Startpunkt entfernt sind, dann alle Scheitelpunkte, die zwei Kanten entfernt sind, und so weiter. Dies ist nützlich, wenn Sie versuchen, den kürzesten Pfad vom Startscheitelpunkt zu einem bestimmten Scheitelpunkt zu finden.
Hoffentlich sollte dies ausreichen, um die Suche nach Breite und Tiefe zuerst zu verstehen. Für die weitere Lektüre würde ich das Kapitel Graphs aus einem hervorragenden Datenstrukturbuch von Robert Lafore empfehlen.
quelle
Angesichts dieses Binärbaums:
Breite erste Durchquerung:
Durchqueren Sie jedes Level von links nach rechts.
"Ich bin G, meine Kinder sind D und ich, meine Enkel sind B, E, H und K, ihre Enkel sind A, C, F"
Tiefe erste Durchquerung:
Durchquerung Durchquerung wird nicht über ganze Ebenen gleichzeitig durchgeführt. Stattdessen taucht die Durchquerung zuerst in die TIEFE (von der Wurzel bis zum Blatt) des Baumes ein. Es ist jedoch etwas komplexer als nur auf und ab.
Es gibt drei Methoden:
Verwendung (auch bekannt als "Warum interessiert uns das?"):
Ich habe diese einfache Quora-Erklärung der Depth First Traversal-Methoden und ihrer allgemeinen Verwendung sehr genossen:
"In-Order Traversal druckt Werte [in der Reihenfolge für die BST (binärer Suchbaum)]. "
" Durchlaufen der Vorbestellung wird verwendet, um eine Kopie des [binären Suchbaums] zu erstellen. "
"Postorder Traversal wird verwendet, um den [binären Suchbaum] zu löschen."
https://www.quora.com/Was-ist-die-Verwendung-vor-bestellung-und-post-bestellung-überquerung-binärbäume-in-computing
quelle
Ich denke, es wäre interessant, beide so zu schreiben, dass Sie nur durch Umschalten einiger Codezeilen den einen oder anderen Algorithmus erhalten, sodass Sie feststellen, dass Ihr Dillema nicht so stark ist, wie es zunächst scheint .
Ich persönlich mag die Interpretation von BFS als Überflutung einer Landschaft: Die Gebiete in geringer Höhe werden zuerst überflutet, und erst dann würden die Gebiete in großer Höhe folgen. Wenn Sie sich die Landschaftshöhen als Isolinien vorstellen, wie wir sie in Geografiebüchern sehen, ist es leicht zu erkennen, dass BFS alle Bereiche unter derselben Isolinie gleichzeitig ausfüllt, genau wie dies bei der Physik der Fall wäre. Die Interpretation von Höhen als Entfernung oder skalierte Kosten gibt daher eine ziemlich intuitive Vorstellung des Algorithmus.
In diesem Sinne können Sie die Idee hinter der Breitensuche leicht anpassen, um den minimalen Spannbaum, den kürzesten Weg und viele andere Minimierungsalgorithmen leicht zu finden.
Ich habe noch keine intuitive Interpretation von DFS gesehen (nur die Standardinterpretation über das Labyrinth, aber es ist nicht so mächtig wie die BFS und die Überschwemmung), daher scheint es für mich, dass BFS besser mit den oben beschriebenen physikalischen Phänomenen zu korrelieren scheint DFS korreliert besser mit Dillema-Entscheidungen auf rationalen Systemen (dh Menschen oder Computer entscheiden, welche Bewegung sie bei einem Schachspiel machen oder aus einem Labyrinth herausgehen).
Für mich liegt der Unterschied zwischen dem Naturphänomen, das am besten zu seinem Ausbreitungsmodell (Transversing) im wirklichen Leben passt.
quelle