Frage

Wenn Sie einen Baum / Grafik Verfahrgeschwindigkeit, was der Unterschied zwischen Breite erster und Tiefe zuerst? Jegliche Codierung oder Pseudo-Code Beispiele wäre toll.

War es hilfreich?

Lösung

Diese beiden Begriffe unterscheiden zwei verschiedene Möglichkeiten, einen Baum zu Fuß.

Es ist wohl am einfachsten nur um den Unterschied zu zeigen. Betrachten Sie den Baum: 

    A
   / \
  B   C
 /   / \
D   E   F

Tiefe ersten Traversal würden die Knoten in dieser Reihenfolge besuchen 

A, B, D, C, E, F

Beachten Sie, dass Sie den ganzen Weg gehen unten ein Bein, bevor er auf.

Breite erste Traversal würde den Knoten in dieser Reihenfolge besuchen 

A, B, C, D, E, F

Hier arbeiten wir den ganzen Weg über jeder Ebene vor nach unten gehen.

(Beachten Sie, dass es einige Unklarheiten in den Traversal Aufträge, und ich betrogen habe das „Lesen“, um auf jeder Ebene des Baumes zu halten. In jedem Fall konnte ich vor oder nach C nach B bekommen, und auch ich erhalten zu E könnte vor oder nach F. Diese oder keine Rolle kann, hängt von Ihnen Anwendung ...)

Beiden Arten von Traversal mit dem Pseudo-Code 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 Traversal Aufträge liegt in der Wahl der Container.

  • Tiefen einen Stapel verwenden. (Die rekursive Implementierung verwendet den Call-Stack ...)
  • Breiten erste 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, die keine Kinder haben, so ist gewährleistet, für ein Ende endlich, azyklische Graphen.

An diesem Punkt habe ich betrogen noch ein wenig. Mit einer wenig Geschicklichkeit können Sie auch arbeits auf die Knoten in dieser Reihenfolge: 

D, B, E, F, C, A

, die eine Variation des Tiefen erstes ist, wo ich an jedem Knoten die Arbeit nicht tun, bis ich wieder auf den Baum zu Fuß. Ich habe aber besuchten der höhere Knoten auf dem Weg nach unten, ihre Kinder zu finden.

Diese Traversal ziemlich natürlich sind in der rekursiven Implementierung (verwenden Sie die „Alternate Zeit“ Zeile oberhalb anstelle der ersten „Work“ Linie) und nicht zu hart, wenn Sie einen expliziten Stack verwenden, aber ich werde es als eine Übung verlassen.

Andere Tipps

Das Verständnis der Begriffe:

Dieses Bild sollten Sie die Idee über den Kontext, in dem die Worte Breite und Tiefe verwendet.

Verstehen Breite und Tiefe

Tiefensuche:

Tiefensuche

  • Depth-first-Suchalgorithmus wirkt, als ob er will, so weit weg bekommen vom Startpunkt so schnell wie möglich.

  • Es verwendet im Allgemeinen eine Stack zu erinnern, wo es gehen soll, wenn es in eine Sackgasse erreicht.

  • Regeln folgen: Push ersten Eckpunkt A auf den Stack

    1. Wenn möglich, besuchen einen benachbarten unvisited Vertex, markieren Sie ihn als besucht, und schieben Sie es auf den Stapel.
    2. Wenn Sie nicht die Regel 1 folgen können, dann, wenn möglich, öffnet sich ein Eckpunkt, den Stapel aus.
    3. Wenn Sie nicht die Regel 1 oder Regel 2 folgen kann, 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 : Depth-first Suchanfragen werden häufig in Simulationen von Spielen verwendet (und spielähnlichen Situationen in die wahre Welt). In einem typischen Spiel können Sie eine von mehreren möglichen Aktionen wählen. Jede Wahl führt zu weiteren Möglichkeiten, von denen jede führt Entscheidungen zu fördern, und so weiter in einer ständig wachsenden baumförmige grafische Darstellung der Möglichkeiten.

Breitensuche:

Breitensuche

  • Die Breitensuche Algorithmus mag so nahe wie möglich zu bleiben zum Ausgangspunkt.
  • Diese Art der Suche ist in der Regel implementiert, um eine Queue verwendet wird.
  • Regeln folgen: Stellen Sie den aktuellen Vertex Vertex A Ausgang
    1. die nächste unvisited Vertex besuchen (falls vorhanden), die dem aktuellen Vertex benachbart ist, markieren Sie es, und es in die Warteschlange ein.
    2. Wenn Sie nicht aus Regel tragen können 1, weil es nicht mehr unvisited Eckpunkte sind, entfernen Sie einen Knoten aus der Warteschlange (wenn möglich) und der aktuelle Scheitelpunkt machen.
    3. Wenn Sie nicht aus Regel 2 tragen 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 : Breitensuche zuerst alle Ecken findet, die eine Kante entfernt vom Startpunkt sind , dann alle Ecken, die zwei Kanten entfernt sind, und so weiter. Dies ist nützlich, wenn Sie versuchen, den kürzesten Weg von der Startecke zu einem gegebenen Knoten zu finden.

Hoffentlich sollte für das Verständnis der Breite-First und Depth-First-Suche genug sein. Für weitere Lesung würde ich das Graphs Kapitel von einem ausgezeichneten Datenstrukturen Buch von Robert Lafore empfehlen.

Vor diesem Hintergrund binärer Baum:

Breite Erste Traversal:
Traverse über jede Ebene von links nach rechts.

"Ich bin G, meine Kinder sind D und I, meine Enkelkinder sind B, E, H und K, ihre Enkelkinder 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

Tiefer Erste Traversal:
Traversal ist nicht über den gesamten Ebenen zu einer Zeit getan. Stattdessen taucht Traversierung in die Tiefe (von der Wurzel zum Blatt) des Baumes zuerst. Allerdings ist es etwas komplexer als nur nach oben und unten.

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 (aka, warum wir kümmern):
Ich habe es wirklich genossen diese einfache Quoren Erklärung der Tiefe Erste Traversal Methoden und wie sie häufig verwendet werden:
"In-Order Traversal Werte gedruckt werden [um die BST (binärer Suchbaum)]"
„Pre-Order Traversal wird verwendet, um eine Kopie des [binären Suchbaumes] zu schaffen.“
„Nachordnungsdurchquerung wird verwendet, um den [binären Suchbaum] zu löschen.“
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

ich denke, es wäre interessant, beide in einer Art und Weise zu schreiben, die nur durch ein paar Zeilen Code Schalen Ihnen einen Algorithmus oder andere geben würde, so dass Sie sehen, dass Ihr dillema nicht so stark ist, wie es scheint sein auf den ersten.

Ich persönlich mag die Interpretation von BFS als eine Landschaft überschwemmen: die niedrigen Höhenlagen zuerst überflutet werden, und nur dann würden die hochgelegenen Gebiete folgen. Wenn Sie die Landschaft Höhen vorstellen als Isolinien, wie wir in der Geographie Büchern zu sehen, ist es einfach zu sehen, dass BFS alle Bereiche unter der einheitlichen Isolinie zugleich füllt, so wie dies mit der Physik wäre. So eine ziemlich intuitive Idee des Algorithmus gibt Höhen als Abstand oder skalierte Kosten zu interpretieren.

diese mit im Auge, können Sie leicht die Idee hinter Breite anpassen zunächst den minimalen Spanning-Tree leicht zu finden suchen, um, kürzesten Weg, und auch viele andere Minimierungsalgorithmen.

Ich habe nicht jede intuitive Interpretation von DFS sehen noch (nur die Standard man über das Labyrinth, aber es ist nicht so mächtig wie die BFS ein und Überschwemmungen), so dass für mich scheint es, dass BFS mit physikalischen Phänomenen besser zu korrelieren scheint, wie beschrieben oben, während DFS korreliert besser mit Entscheidungen dillema auf rationale Systemen (dh Menschen oder Computer zu entscheiden, welche auf einem Schachspiel machen bewegen oder aus einem Labyrinth zu gehen).

Also, für mich den Unterschied zwischen Lügen auf dem besten natürliches Phänomen ihr Ausbreitungsmodell entspricht (quert) im wirklichen Leben.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top