Largeur d'abord vs profondeur d'abord

172

Lorsque vous parcourez un arbre / un graphique, quelle est la différence entre la largeur d'abord et la profondeur d'abord? Tout exemple de codage ou de pseudocode serait génial.

Ted Smith
la source
6
Avez-vous vérifié wikipedia ( profondeur d'abord , largeur d'abord )? Il y a des exemples de code sur ces pages, ainsi que beaucoup de jolies images.
rmeador
J'ai eu cette pensée aussi, mais les exemples donnés sont légèrement plus
beaux

Réponses:

292

Ces deux termes différencient deux manières différentes de marcher dans un arbre.

Il est probablement plus facile de simplement montrer la différence. Considérez l'arbre:

    A
   / \
  B   C
 /   / \
D   E   F

Un premier parcours en profondeur visiterait les nœuds dans cet ordre

A, B, D, C, E, F

Remarquez que vous descendez complètement une jambe avant de continuer.

Une première traversée en largeur visiterait le nœud dans cet ordre

A, B, C, D, E, F

Ici, nous travaillons à travers chaque niveau avant de descendre.

(Notez qu'il y a une certaine ambiguïté dans les ordres de traversée, et j'ai triché pour maintenir l'ordre de "lecture" à chaque niveau de l'arbre. Dans les deux cas, je pourrais arriver à B avant ou après C, et de même je pourrais arriver à E avant ou après F. Cela peut ou non avoir une importance, dépend de votre application ...)


Les deux types de parcours peuvent être réalisés avec le pseudocode:

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

La différence entre les deux ordres de parcours réside dans le choix de Container.

  • Pour la profondeur, utilisez d' abord une pile. (L'implémentation récursive utilise la pile d'appels ...)
  • Pour la largeur en premier, utilisez une file d'attente.

L'implémentation récursive ressemble à

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

La récursion se termine lorsque vous atteignez un nœud qui n'a pas d'enfants, donc il est garanti qu'elle se termine pour les graphes acycliques finis.


À ce stade, j'ai encore un peu triché. Avec un peu d'intelligence, vous pouvez également travailler sur les nœuds dans cet ordre:

D, B, E, F, C, A

qui est une variante de la profondeur d'abord, où je ne fais pas le travail à chaque nœud avant de remonter dans l'arbre. J'ai cependant visité les nœuds supérieurs en descendant pour trouver leurs enfants.

Cette traversée est assez naturelle dans l'implémentation récursive (utilisez la ligne "Alternate time" ci-dessus au lieu de la première ligne "Work"), et pas trop difficile si vous utilisez une pile explicite, mais je la laisserai comme un exercice.

dmckee --- chaton ex-modérateur
la source
@dmckee Merci! Je crois que vous vouliez dire "Travailler sur la charge utile chez Node", non?
batbrat
4
Il peut être intéressant de noter que vous pouvez modifier la version en profondeur d'abord pour obtenir le préfixe ( A, B, D, C, E, F- le premier présenté), l'infixe ( D, B, A, E, C, F- utilisé pour le tri: ajouter comme arbre AVL puis lire infix) ou postfix ( D, B, E, F, C, Al'alternative présentée) traversée. Les noms sont donnés par la position dans laquelle vous traitez la racine. Il convient de noter que l'infixe n'a vraiment de sens que pour les arbres binaires. @batbrat ce sont les noms ... étant donné le temps écoulé depuis que vous avez posé la question, vous le savez probablement déjà.
Theraot
@Theraot merci d'avoir ajouté cela! Oui, je connais ce type de parcours et pourquoi Infix n'a de sens que pour les arbres binaires.
batbrat
Comment décider quelle solution a une meilleure complexité spatio-temporelle?
IgorGanapolsky
1
@IgorGanapolsky Devrait être le même pour les deux en principe (après tout, ils utilisent essentiellement le même code). Une question plus intéressante serait de savoir comment ils affectent le cache et le jeu de travail, mais je pense que cela dépendra de la morphologie de l'arbre.
dmckee --- ex-moderator chaton
95

Comprendre les termes:

Cette image devrait vous donner une idée du contexte dans lequel les mots largeur et profondeur sont utilisés.

Comprendre l'étendue et la profondeur


Recherche en profondeur d'abord:

Recherche en profondeur d'abord

  • L'algorithme de recherche en profondeur d'abord agit comme s'il voulait s'éloigner le plus rapidement possible du point de départ.

  • Il utilise généralement un Stackpour se rappeler où il doit aller lorsqu'il atteint une impasse.

  • Règles à suivre: Poussez le premier sommet A sur le Stack

    1. Si possible, visitez un sommet non visité adjacent, marquez-le comme visité et poussez-le sur la pile.
    2. Si vous ne pouvez pas suivre la règle 1, alors, si possible, faites sortir un sommet de la pile.
    3. Si vous ne pouvez pas suivre la règle 1 ou la règle 2, vous avez terminé.
  • Code Java:

    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;
    }
    
  • Applications : Les recherches en profondeur sont souvent utilisées dans les simulations de jeux (et de situations de jeu dans le monde réel). Dans un jeu typique, vous pouvez choisir l'une des nombreuses actions possibles. Chaque choix conduit à d'autres choix, chacun d'entre eux conduisant à d'autres choix, et ainsi de suite dans un graphique de possibilités en forme d'arbre en constante expansion.


Recherche en largeur d'abord:

Recherche en largeur d'abord

  • L'algorithme de recherche en largeur d'abord aime rester aussi proche que possible du point de départ.
  • Ce type de recherche est généralement implémenté à l'aide d'un fichier Queue.
  • Règles à suivre: Faire du sommet A de départ le sommet courant
    1. Visitez le prochain sommet non visité (s'il y en a un) adjacent au sommet actuel, marquez-le et insérez-le dans la file d'attente.
    2. Si vous ne pouvez pas exécuter la règle 1 parce qu'il n'y a plus de sommets non visités, supprimez un sommet de la file d'attente (si possible) et faites-en le sommet courant.
    3. Si vous ne pouvez pas exécuter la règle 2 parce que la file d'attente est vide, vous avez terminé.
  • Code Java:

    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 : La recherche en largeur d'abord trouve d'abord tous les sommets situés à une arête du point de départ, puis tous les sommets à deux arêtes, et ainsi de suite. Ceci est utile si vous essayez de trouver le chemin le plus court entre le sommet de départ et un sommet donné.

J'espère que cela devrait suffire pour comprendre les recherches en largeur d'abord et en profondeur d'abord. Pour plus d'informations, je recommanderais le chapitre Graphiques d'un excellent livre sur les structures de données de Robert Lafore.

Yogesh Umesh Vaity
la source
6
Si j'en avais dix autres, je le ferais.
snr
@snr vous pourriez attribuer une prime;)
Snow
@Snow si vous dites ses directives, je peux. Je ne sais pas comment faire.
snr
Merci @snr, je suis très heureux de recevoir ma première prime. J'apprécie beaucoup.
Yogesh Umesh Vaity
1
Merci @Snow, je suis heureux que vous ayez trouvé ma réponse utile.
Yogesh Umesh Vaity
4

Compte tenu de cet arbre binaire:

entrez la description de l'image ici

Breadth First Traversal:
Traversez chaque niveau de gauche à droite.

"Je suis G, mes enfants sont D et moi, mes petits-enfants sont B, E, H et K, leurs petits-enfants sont 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

Depth First Traversal: La
traversée n'est pas effectuée sur des niveaux entiers à la fois. Au lieu de cela, la traversée plonge d'abord dans la PROFONDEUR (de la racine à la feuille) de l'arbre. Cependant, c'est un peu plus complexe que simplement monter et descendre.

Il existe trois méthodes:

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

Utilisation (aka, pourquoi nous en soucions-nous):
J'ai vraiment apprécié cette simple explication Quora des méthodes Depth First Traversal et de la manière dont elles sont couramment utilisées:
"In-Order Traversal imprimera les valeurs [dans l'ordre pour le BST (arbre de recherche binaire)] "
" Le parcours de précommande est utilisé pour créer une copie de [l'arbre de recherche binaire]. "
"Le parcours de post-ordre est utilisé pour supprimer [l'arborescence de recherche binaire]."
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

msyinmei
la source
2

Je pense qu'il serait intéressant de les écrire tous les deux de manière à ce que seulement en changeant certaines lignes de code, vous obteniez un algorithme ou un autre, de sorte que vous verrez que votre dillema n'est pas aussi fort qu'il semble l'être au début .

J'aime personnellement l'interprétation de BFS comme inondant un paysage: les zones de basse altitude seront inondées en premier, et alors seulement les zones de haute altitude suivront. Si vous imaginez les altitudes du paysage comme des isolignes comme nous le voyons dans les livres de géographie, il est facile de voir que BFS remplit toutes les zones sous la même isoligne en même temps, tout comme ce serait le cas avec la physique. Ainsi, interpréter les altitudes en tant que distance ou coût échelonné donne une idée assez intuitive de l'algorithme.

Dans cet esprit, vous pouvez facilement adapter l'idée derrière la première recherche en largeur pour trouver facilement l'arbre couvrant minimum, le chemin le plus court, ainsi que de nombreux autres algorithmes de minimisation.

Je n'ai pas encore vu d'interprétation intuitive de DFS (seulement celle standard sur le labyrinthe, mais elle n'est pas aussi puissante que celle de BFS et d'inondation), donc pour moi, il semble que BFS semble mieux corréler avec les phénomènes physiques comme décrit ci-dessus, alors que DFS corrèle mieux avec les choix dillema sur des systèmes rationnels (c'est-à-dire des personnes ou des ordinateurs décidant quel coup faire sur une partie d'échecs ou sortant d'un labyrinthe).

Donc, pour moi, la différence entre se trouve sur quel phénomène naturel correspond le mieux à leur modèle de propagation (transverse) dans la vie réelle.

user5193682
la source
1
Vous pouvez les implémenter avec un algorithme similaire, utilisez simplement stack pour DFS et queue pour BFS. Le problème avec BFS est que vous devez garder une trace de tous les nœuds vus jusqu'à présent. DFS en physique .. J'imagine des univers alternatifs et vous en voulez un avec la vie, tous les enfants de racine, sont des big-bangs différents et vous descendez jusqu'à la mort de l'univers, pas de vie? vous revenez à la dernière bifurcation et essayez un autre virage, jusqu'à ce que tout soit épuisé et que vous passiez au prochain big-bang, établissant de nouvelles lois physiques pour le nouvel univers. super intuitif. un bon problème est de trouver un chemin avec le cheval sur un échiquier.
juanmf