Breite zuerst Vs Tiefe zuerst

Wenn Sie einen Baum / ein Diagramm durchlaufen, was ist der Unterschied zwischen Breite zuerst und Tiefe zuerst? Beliebige Codierungs- oder Pseudocode-Beispiele wären großartig.

   

Diese beiden Begriffe unterscheiden zwischen zwei verschiedenen Arten, einen Baum zu gehen.

Es ist wahrscheinlich am einfachsten, nur den Unterschied zu zeigen. Betrachte den Baum:

A / \ BC / / \ DEF 

Ein Tiefen- First-Traversal würde die Knoten in dieser Reihenfolge besuchen

 A, B, D, C, E, F 

Beachten Sie, dass Sie ein ganzes Bein hinunter gehen, bevor Sie weitergehen.

Eine breite erste Traversierung würde den Knoten in dieser Reihenfolge besuchen

 A, B, C, D, E, F 

Hier arbeiten wir den ganzen Weg über jedes Level bevor wir runter gehen.

(Beachten Sie, dass es in den Traversierungsbefehlen einige Unklarheiten gibt, und ich habe versucht, die “Lese” -Reihenfolge auf jeder Ebene des Baums beizubehalten. In jedem Fall könnte ich vor oder nach C zu B gelangen, und ebenso könnte ich dazu kommen E vor oder nach F. Dies kann oder kann nicht wichtig sein, hängt von Ihrer Anwendung ab …)


Beide Arten der Traversierung können mit dem Pseudocode erreicht werden:

 Store the root node in Container While (there are nodes in Container) N = Get the "next" node from Container Store all the children of N in Container Do some work on N 

Der Unterschied zwischen den beiden Durchquerungsbefehlen liegt in der Wahl des Container .

  • Verwenden Sie für die Tiefe zuerst einen Stapel. (Die rekursive Implementierung verwendet den Call-Stack …)
  • Verwenden Sie für die Breite zuerst eine Warteschlange.

Die rekursive Implementierung sieht so aus

 ProcessNode(Node) Work on the payload Node Foreach child of Node ProcessNode(child) /* Alternate time to work on the payload Node (see below) */ 

Die Rekursion endet, wenn Sie einen Knoten erreichen, der keine untergeordneten Elemente enthält, so dass endliche, azyklische Graphen garantiert enden.


An diesem Punkt habe ich noch ein wenig betrogen. Mit etwas Geschick können Sie die Knoten auch in dieser Reihenfolge bearbeiten :

 D, B, E, F, C, A 

Das ist eine Variation der Tiefe – zuerst, wo ich die Arbeit an jedem Knoten nicht mache, bis ich den Baum hinaufgehe. Ich habe jedoch die höheren Knoten auf dem Weg nach unten besucht, um ihre Kinder zu finden.

Diese Traversierung ist in der rekursiven Implementierung ziemlich natürlich (benutze die “Alternate time” -Zeile oben anstelle der ersten “Work” -Zeile), und nicht zu schwer, wenn du einen expliziten Stack verwendest, aber ich überlasse es als Übung.

Die Begriffe verstehen:

Dieses Bild sollte Ihnen die Idee über den Kontext geben, in dem die Wörter Breite und Tiefe verwendet werden.

Breite und Tiefe verstehen


Tiefensuche:

Tiefensuche

  • Der Tiefensuchalgorithmus verhält sich so, als wolle er so schnell wie möglich vom Ausgangspunkt wegkommen.

  • Es verwendet im Allgemeinen einen Stack zu merken, wohin es gehen soll, wenn es eine Sackgasse erreicht.

  • Folgende Regeln: Schieben Sie den ersten Scheitelpunkt A auf den Stack

    1. Wenn möglich, besuchen Sie einen benachbarten, nicht besuchten Scheitelpunkt, markieren Sie ihn als besucht und drücken Sie ihn auf den Stapel.
    2. Wenn Sie Regel 1 nicht befolgen können, sollten Sie, wenn möglich, einen Eckpunkt vom Stapel entfernen.
    3. Wenn Sie Regel 1 oder Regel 2 nicht befolgen können, sind Sie fertig.
  • Java-Code:

     public void searchDepthFirst() { // Begin at vertex 0 (A) vertexList[0].wasVisited = true; displayVertex(0); stack.push(0); while (!stack.isEmpty()) { int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek()); // If no such vertex if (adjacentVertex == -1) { stack.pop(); } else { vertexList[adjacentVertex].wasVisited = true; // Do something stack.push(adjacentVertex); } } // Stack is empty, so we're done, reset flags for (int j = 0; j < nVerts; j++) vertexList[j].wasVisited = false; } 
  • Anwendungen : Tiefensuchvorgänge werden oft 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 wählen. Jede Wahl führt zu weiteren Entscheidungen, von denen jede zu weiteren Entscheidungen führt, und so weiter zu einem immer größer werdenden baumförmigen Graphen von Möglichkeiten.


Breiteste Suche:

Breiteste Suche

  • Der Breiten-Suchalgorithmus möchte so nah wie möglich am Startpunkt bleiben.
  • Diese Art von Suche wird im Allgemeinen unter Verwendung einer Queue implementiert.
  • Zu befolgende Regeln: Machen Sie ausgehend vom Scheitelpunkt A den aktuellen Scheitelpunkt
    1. Besuchen Sie den nächsten nicht besuchten Scheitelpunkt (falls vorhanden), der an den aktuellen Scheitelpunkt angrenzt, markieren Sie ihn und fügen Sie ihn in die Queue ein.
    2. Wenn Sie Regel 1 nicht ausführen können, weil es keine noch nicht besuchten Scheitelpunkte mehr gibt, entfernen Sie einen Scheitelpunkt (falls möglich) aus der Queue und machen Sie ihn zum aktuellen Scheitelpunkt.
    3. Wenn Sie Regel 2 nicht ausführen können, weil die Warteschlange leer ist, sind Sie fertig.
  • Java-Code:

     public void searchBreadthFirst() { vertexList[0].wasVisited = true; displayVertex(0); queue.insert(0); int v2; while (!queue.isEmpty()) { int v1 = queue.remove(); // Until it has no unvisited neighbors, get one while ((v2 = getAdjUnvisitedVertex(v1)) != -1) { vertexList[v2].wasVisited = true; // Do something queue.insert(v2); } } // Queue is empty, so we're done, reset flags for (int j = 0; j < nVerts; j++) vertexList[j].wasVisited = false; } 
  • Anwendungen : Bei der Breitensuche werden zuerst alle Scheitelpunkte gefunden, die eine Kante vom Startpunkt entfernt sind, dann alle Scheitelpunkte, die zwei Kanten entfernt sind, usw. Dies ist nützlich, wenn Sie versuchen, den kürzesten Pfad vom Startknoten zu einem bestimmten Knoten zu finden.

Hoffentlich sollte das ausreichen, um die Breitensuche zu verstehen. Zur weiteren Lektüre würde ich das Kapitel Graphen aus einem exzellenten Datenstrukturbuch von Robert Lafore empfehlen.

Ich denke, es wäre interessant, beide so zu schreiben, dass nur durch das Umschalten einiger Codezeilen der eine oder andere Algorithmus erhalten wird, so dass Sie sehen werden, dass Ihr Dilemma nicht so stark ist, wie es zunächst zu sein scheint .

Ich persönlich mag die Interpretation von BFS als Überflutung einer Landschaft: Die Gebiete in geringer Höhe werden zuerst überschwemmt, und erst dann folgen die Höhenregionen. Stellt man sich die Höhenlagen der Landschaft als Isolinien vor, wie man sie in Geographiebüchern sieht, so ist es leicht zu sehen, dass BFS die gesamte Fläche unter derselben Isolinie zur gleichen Zeit ausfüllt, genau wie dies bei der Physik der Fall wäre. Die Interpretation von Höhen als Entfernung oder skalierte Kosten ergibt somit eine ziemlich intuitive Vorstellung des Algorithmus.

In diesem Sinne können Sie einfach die Idee hinter der Breite der ersten Suche anpassen, um den minimalen Spannbaum, den kürzesten Pfad und auch viele andere Minimierungsalgorithmen zu finden.

Ich habe noch keine intuitive Interpretation von DFS gesehen (nur die Standard über das Labyrinth, aber es ist nicht so mächtig wie die BFS und Flooding), so scheint es für mich, dass BFS scheint besser korreliert mit physikalischen Phänomenen, wie oben beschrieben DFS korreliert besser mit der Auswahl dillema auf rationalen Systemen (dh Menschen oder Computer, die entscheiden, welchen Zug sie bei einem Schachspiel machen oder aus einem Irrgarten gehen).

Also, für mich ist der Unterschied zwischen Lügen, auf denen das natürliche Phänomen am besten zu ihrem Ausbreitungsmodell (Transversation) im wirklichen Leben passt.

Angesichts dieses binären Baumes:

Bildbeschreibung hier eingeben

Breite erste Traversale:
Überqueren Sie jede Ebene 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”

 - Level 1: G - Level 2: D, I - Level 3: B, E, H, K - Level 4: A, C, F Order Searched: G, D, I, B, E, H, K, A, C, F 

Tiefe erste Traversal:
Das Traversal wird nicht über ganze Levels hinweg durchgeführt. Stattdessen taucht Traversal zuerst in die TIEFE (von Wurzel zu Blatt) des Baumes. Es ist jedoch ein bisschen komplexer als einfach auf und ab.

Es gibt drei Methoden:

 1) PREORDER: ROOT, LEFT, RIGHT. You need to think of this as a recursive process: Grab the Root. (G) Then Check the Left. (It's a tree) Grab the Root of the Left. (D) Then Check the Left of D. (It's a tree) Grab the Root of the Left (B) Then Check the Left of B. (A) Check the Right of B. (C, and it's a leaf node. Finish B tree. Continue D tree) Check the Right of D. (It's a tree) Grab the Root. (E) Check the Left of E. (Nothing) Check the Right of E. (F, Finish D Tree. Move back to G Tree) Check the Right of G. (It's a tree) Grab the Root of I Tree. (I) Check the Left. (H, it's a leaf.) Check the Right. (K, it's a leaf. Finish G tree) DONE: G, D, B, A, C, E, F, I, H, K 2) INORDER: LEFT, ROOT, RIGHT Where the root is "in" or between the left and right child node. Check the Left of the G Tree. (It's a D Tree) Check the Left of the D Tree. (It's a B Tree) Check the Left of the B Tree. (A) Check the Root of the B Tree (B) Check the Right of the B Tree (C, finished B Tree!) Check the Right of the D Tree (It's a E Tree) Check the Left of the E Tree. (Nothing) Check the Right of the E Tree. (F, it's a leaf. Finish E Tree. Finish D Tree)... Onwards until... DONE: A, B, C, D, E, F, G, H, I, K 3) POSTORDER: LEFT, RIGHT, ROOT DONE: A, C, B, F, E, D, H, K, I, G 

Usage (aka, warum kümmern wir uns):
Ich habe diese einfache Quora-Erklärung der Methoden von Depth First Traversal und ihrer üblichen Verwendung sehr genossen:
“In-Order Traversal wird Werte [in der Reihenfolge für den BST (binary search tree)]” drucken
“Pre-Order Traversal wird verwendet, um eine Kopie des [binary search tree] zu erstellen.”
“Postorder traversal wird verwendet, um den [binary search tree] zu löschen.”
https://www.quora.com/What-ist-use-of-pre-order-and-post-order-traversal-of-binary-tree-in-computing