Breite zuerst gegen Tiefe zuerst

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.

Ted Smith
quelle
6
Haben Sie Wikipedia überprüft ( Tiefe zuerst , Breite zuerst )? Auf diesen Seiten finden Sie Codebeispiele sowie viele hübsche Bilder.
Rmeador
Ich hatte diesen Gedanken auch, aber dann sind die Beispiele etwas schöner als die auf Wikipedia gefundenen ....
jonnybazookatone

Antworten:

291

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:

    A
   / \
  B   C
 /   / \
D   E   F

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

A, B, D, C, E, F

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

A, B, C, D, E, F

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:

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 Durchquerungsordnungen liegt in der Wahl von 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 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 :

D, B, E, F, C, A

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.

dmckee --- Ex-Moderator Kätzchen
quelle
@dmckee Danke! Ich glaube, Sie meinten "Arbeiten an der Nutzlast am Knoten", oder?
Batbrat
4
Es kann erwähnenswert sein, dass Sie die Tiefenversion ändern können, um das Präfix ( 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, Adie 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.
Theraot
@ Theraot danke für das Hinzufügen! Ja, ich kenne diese Art von Durchquerungen und weiß, warum Infix nur für Binärbäume sinnvoll ist.
Batbrat
Wie kann man entscheiden, welche Lösung eine bessere räumliche oder zeitliche Komplexität aufweist?
Igor Ganapolsky
1
@IgorGanapolsky Sollte grundsätzlich für beide gleich sein (schließlich verwenden sie im Wesentlichen den gleichen Code). Eine interessantere Frage wäre, wie sie sich auf den Cache und den Arbeitssatz auswirken, aber ich denke, das hängt von der Morphologie des Baums ab.
dmckee --- Ex-Moderator Kätzchen
95

Die Begriffe verstehen:

Dieses Bild soll Ihnen eine Vorstellung davon geben, in welchem ​​Kontext die Wörter Breite und Tiefe verwendet werden.

Breite und Tiefe verstehen


Tiefensuche:

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 Stackzu merken, wohin es gehen soll, wenn es eine Sackgasse erreicht.

  • Zu befolgende 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 schieben Sie ihn auf den Stapel.
    2. Wenn Sie Regel 1 nicht befolgen 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 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:

Breitensuche

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

Yogesh Umesh Vaity
quelle
6
Würde ich noch zehn Stimmen haben, würde ich das tun.
Snr
@snr Sie könnten ein Kopfgeld vergeben;)
Schnee
@Schnee, wenn Sie seine Anweisungen sagen, kann ich. Ich weiß nicht, wie ich es machen soll.
Snr
Vielen Dank @snr, ich freue mich sehr über mein erstes Kopfgeld. Ich schätze sehr.
Yogesh Umesh Vaity
1
Danke @Snow, ich bin froh, dass ihr meine Antwort nützlich gefunden habt.
Yogesh Umesh Vaity
4

Angesichts dieses Binärbaums:

Geben Sie hier die Bildbeschreibung ein

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"

- 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:
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:

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 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

msyinmei
quelle
2

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.

user5193682
quelle
1
Sie können sie mit einem ähnlichen Algorithmus implementieren. Verwenden Sie einfach Stack für DFS und Queue für BFS. Das Problem mit BFS ist, dass Sie alle bisher gesehenen Knoten im Auge behalten müssen. DFS in der Physik. Ich stelle mir alternative Universen vor und du willst eins mit dem Leben, alle Kinder der Wurzel, sind verschiedene Urknalle und du gehst bis zum Tod des Universums, kein Leben? Sie kehren zur letzten Gabelung zurück und versuchen eine weitere Runde, bis alle erschöpft sind und Sie zum nächsten Urknall gehen und neue physikalische Gesetze für das neue Universum festlegen. super intuitiv. Ein gutes Problem ist es, einen Weg mit dem Pferd in einem Schachbrett zu finden.
Juanmf