Largeur d'abord vs profondeur d'abord

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.

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.

Comprendre les termes:

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

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:

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

Compte tenu de cet arbre binaire:

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

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.