wake-up-neo.net

Breite zuerst Vs Tiefe zuerst

Was ist der Unterschied zwischen Breite zuerst und Tiefe zuerst, wenn ein Baum/eine Grafik überquert wird? Beliebige Codierungs- oder Pseudocodierungsbeispiele wären toll.

161
Ted Smith

Diese beiden Begriffe unterscheiden zwischen zwei verschiedenen Arten des Gehens auf einem Baum.

Es ist wahrscheinlich am einfachsten, nur den Unterschied aufzuzeigen. Betrachten Sie den Baum:

    A
   / \
  B   C
 /   / \
D   E   F

Eine Tiefe erste Durchquerung würde die Knoten in dieser Reihenfolge besuchen

A, B, D, C, E, F

Beachten Sie, dass Sie den ganzen Weg gehen nach unten ein Bein, bevor Sie weitermachen.

Eine Breite erste Durchquerung würde den Knoten in dieser Reihenfolge besuchen

A, B, C, D, E, F

Hier arbeiten wir den ganzen Weg quer jedes Level, bevor wir runter gehen.

(Beachten Sie, dass die Traversierungsbefehle etwas mehrdeutig sind, und ich habe betrogen, um die "Lesereihenfolge" auf jeder Ebene des Baums beizubehalten. In beiden Fällen konnte ich vor oder nach C nach B gelangen, und ich konnte auch nach E vor oder nach F. Dies kann oder kann nicht wichtig sein, hängt von Ihrer Anwendung ab ...)


Mit dem Pseudocode können beide Arten der Durchquerung 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 Traversierungsbefehlen liegt in der Wahl von Container.

  • Für Tiefe zuerst benutze einen Stapel. (Die rekursive Implementierung verwendet den Call-Stack ...)
  • Für Breite zuerst eine Warteschlange verwenden.

Die rekursive Implementierung sieht aus wie

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 Knoten hat, sodass die Endung für endliche, azyklische Graphen garantiert ist.


Zu diesem Zeitpunkt habe ich noch ein wenig geschummelt. Mit ein wenig Cleverness können Sie auch die Knoten in dieser Reihenfolge work-on:

D, B, E, F, C, A

das ist eine Variante von Depth-First, bei der ich die Arbeit nicht an jedem Knoten erledige, bis ich wieder auf dem Baum bin. Ich habe jedoch besucht die höheren Knoten auf dem Weg nach unten, um ihre Kinder zu finden.

Diese Überquerung ist in der rekursiven Implementierung ziemlich natürlich (verwenden Sie die Zeile "Alternate time" oben anstelle der ersten Zeile "Work") und nicht auch hart, wenn Sie einen expliziten Stack verwenden, sondern I werde es als übung belassen.

271
dmckee

Begriffe verstehen:

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

Understanding Breadth and Depth


Tiefensuche:

Depth-First Search

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

  • Im Allgemeinen wird ein Stack verwendet, um sich zu merken, wohin es gehen soll, wenn es eine Sackgasse erreicht.

  • Zu befolgende Regeln: Schieben Sie den ersten Scheitelpunkt A auf das Stack

    1. Besuchen Sie nach Möglichkeit einen benachbarten nicht besuchten Scheitelpunkt, markieren Sie ihn als besucht und legen Sie ihn auf den Stapel.
    2. Wenn Sie Regel 1 nicht folgen können, entfernen Sie nach Möglichkeit einen Scheitelpunkt vom Stapel.
    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 : Tiefensuchen werden häufig in Simulationen von Spielen (und spielerischen 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 immer größer werdenden baumförmigen Diagramm von Möglichkeiten.


Breitensuche:

Breadth-First Search

  • Der Breitensuchalgorithmus möchte so nah wie möglich am Startpunkt bleiben.
  • Diese Art der Suche wird im Allgemeinen mit einem Queue implementiert.
  • Zu befolgende Regeln: Startscheitelpunkt A zum aktuellen Scheitelpunkt machen
    1. Suchen Sie den nächsten nicht besuchten Scheitelpunkt (falls vorhanden), der neben dem aktuellen Scheitelpunkt liegt, markieren Sie ihn und fügen Sie ihn in die Warteschlange ein.
    2. Wenn Sie Regel 1 nicht ausführen können, weil es keine nicht besuchten Scheitelpunkte mehr gibt, entfernen Sie einen Scheitelpunkt aus der Warteschlange (falls möglich) 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;
    }
    
  • Applications : 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 Weg vom Startscheitelpunkt zu einem bestimmten Scheitelpunkt zu finden.

Hoffentlich sollte dies ausreichen, um die Suche nach Breite und Tiefe zu verstehen. Für die weitere Lektüre empfehle ich das Kapitel Graphen aus einem hervorragenden Datenstrukturbuch von Robert Lafore.

77

Angesichts dieses Binärbaums:

enter image description here

Breite erste Durchquerung:
Überquere 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 Durchquerung:
Der Durchlauf wird nicht ÜBER ganze Ebenen gleichzeitig durchgeführt. Stattdessen taucht der Traversal zuerst in die TIEFE (von der Wurzel zum Blatt) des Baumes ein. Es ist jedoch etwas komplexer als nur hoch und runter.

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

Verwendung (auch bekannt als, warum interessiert es uns?):
Mir hat diese einfache Quora-Erklärung der Depth First Traversal-Methoden und ihrer allgemeinen Verwendung sehr gut gefallen:
"In-Order Traversal gibt Werte aus [in der Reihenfolge des BST (binärer Suchbaum)]"
"Durchlaufen vorbestellen 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-von-Vorbestellungs-und-Nachbestellungsdurchsuchung-von-Baumcomputern

3
msyinmei

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 Dillem 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 mit geringer Höhe werden zuerst überflutet, und erst dann werden die Gebiete mit großer Höhe folgen. Wenn Sie sich die Landschaftshöhen als Isolinien vorstellen, wie wir es in den Geografiebüchern sehen, ist es leicht zu sehen, 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 liefert daher eine ziemlich intuitive Vorstellung des Algorithmus.

Vor diesem Hintergrund können Sie die Idee der Breitensuche leicht anpassen, um den minimalen Spannbaum, den kürzesten Pfad und viele andere Minimierungsalgorithmen zu finden.

Ich habe noch keine intuitive Interpretation von DFS gesehen (nur die Standardinterpretation über das Labyrinth, aber sie ist nicht so mächtig wie die BFS und das Fluten), daher scheint es für mich, dass BFS besser mit den oben beschriebenen physikalischen Phänomenen korreliert, während DFS korreliert besser mit Entscheidungen, die auf rationalen Systemen getroffen werden (dh Menschen oder Computer entscheiden, welche Schritte bei einem Schachspiel oder beim Verlassen eines Labyrinths unternommen werden).

Für mich liegt der Unterschied darin, welches Naturphänomen am besten zu ihrem Ausbreitungsmodell (Transversing) im wirklichen Leben passt.

2
user5193682