Largeur Premier Vs Profondeur D’abord

Lors de la traversée d’un arbre / graphique, quelle est la différence entre la largeur d’abord et la profondeur d’abord? Tout codage ou exemple de pseudocode serait génial.

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

Il est probablement plus simple de montrer la différence. Considérez l’arbre:

A / \ BC / / \ DEF 

Une première traversée en profondeur visiterait les nœuds dans cet ordre

 A, B, D, C, E, F 

Notez que vous descendez d’ une jambe avant de continuer.

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

 A, B, C, D, E, F 

Ici, nous travaillons tout au long de chaque niveau avant de descendre.

(Notez qu’il y a une certaine ambiguïté dans les ordres de traversée, et j’ai sortingché pour maintenir l’ordre “lecture” à chaque niveau de l’arbre. Dans les deux cas, je pouvais accéder à B avant ou après C, et E avant ou après F. Cela peut ou peut ne pas avoir d’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 traversée réside dans le choix du Container .

  • Pour la profondeur, utilisez d’ abord une stack. (L’implémentation récursive utilise la stack d’appel …)
  • Pour la première fois, utilisez une queue.

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écursivité prend fin lorsque vous atteignez un nœud qui n’a pas d’enfant, de sorte qu’il est garanti de terminer pour les graphiques finis, acycliques.


À ce stade, j’ai encore un peu sortingché. Avec un peu d’intelligence, vous pouvez également travailler sur les noeuds dans cet ordre:

 D, B, E, F, C, A 

ce qui est une variation de profondeur d’abord, où je ne fais pas le travail à chaque nœud jusqu’à ce que je marche sur l’arbre. J’ai cependant visité les noeuds supérieurs 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 stack explicite, mais je la laisserai comme exercice.

Comprendre les termes:

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

Comprendre la largeur et la profondeur


Recherche en profondeur:

Profondeur Première Recherche

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

  • Il utilise généralement une Stack pour se rappeler où il doit aller quand il atteint une impasse.

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

    1. Si possible, visitez un sumt non visité adjacent, marquez-le comme visité et poussez-le sur la stack.
    2. Si vous ne pouvez pas suivre la règle 1, alors, si possible, retirez un sumt de la stack.
    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 les situations de jeu dans le monde réel). Dans un jeu typique, vous pouvez choisir parmi plusieurs actions possibles. Chaque choix conduit à d'autres choix, chacun d'entre eux conduisant à de nouveaux choix, et ainsi de suite, dans un graphique de possibilités en forme d'arbre qui ne cesse de s'étendre.


Recherche de la largeur d'abord:

Recherche en largeur

  • L'algorithme de recherche en largeur permet de restr aussi proche que possible du sharepoint départ.
  • Ce type de recherche est généralement implémenté à l'aide d'une Queue .
  • Règles à suivre: Lancez le sumt A comme sumt actuel
    1. Visitez le prochain sumt non visité (s'il y en a un) adjacent au sumt actuel, marquez-le et insérez-le dans la queue.
    2. Si vous ne pouvez pas exécuter la règle 1 car il n'y a plus de sumts non visités, supprimez un sumt de la queue (si possible) et faites-en le sumt actuel.
    3. Si vous ne pouvez pas exécuter la règle 2 car la queue 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 par largeur d'abord détecte d'abord tous les sumts situés à un bord du sharepoint départ, puis tous les sumts situés à deux bords, etc. Ceci est utile si vous essayez de trouver le plus court chemin du sumt de départ à un sumt donné.

Espérons que cela suffira pour comprendre les recherches de la largeur d'abord et de la profondeur d'abord. Pour plus de lecture, je recommanderais le chapitre Graphes d'un excellent livre de structures de données de Robert Lafore.

Je pense qu’il serait intéressant de les écrire tous les deux de manière à ce que ce n’est qu’en changeant certaines lignes de code que vous obtiendrez un algorithme ou un autre, de sorte que vous verrez que votre dillema n’est pas aussi fort qu’au premier abord. .

Personnellement, j’aime 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 le BFS remplit toutes les zones sous le même isoleau en même temps, comme ce serait le cas avec la physique. Ainsi, interpréter les altitudes comme distance ou coût échelonné donne une idée assez intuitive de l’algorithme.

Dans cette optique, vous pouvez facilement adapter l’idée qui sous-tend la recherche la plus large possible pour trouver le spanning tree minimum, le chemin le plus court et de nombreux autres algorithmes de minimisation.

Je n’ai pas encore vu d’interprétation intuitive de DFS (seulement la version standard sur le labyrinthe, mais elle n’est pas aussi puissante que celle de BFS et d’inondation), donc il me semble que BFS semble mieux corrélé aux phénomènes physiques DFS se corrèle mieux avec les choix possibles sur les systèmes rationnels (c.-à-d. Les personnes ou les ordinateurs qui décident de faire un jeu d’échecs ou de sortir d’un labyrinthe).

Donc, pour moi, la différence entre les mensonges sur lesquels les phénomènes naturels correspondent le mieux à leur modèle de propagation (transverse) dans la vie réelle.

Étant donné cet arbre binary:

entrer la description de l'image ici

Largeur première traversée:
Traverser 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 tous les niveaux à 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 est-ce que nous nous en soucions):
J’ai vraiment apprécié cette simple explication Quora des méthodes Depth First Traversal et comment elles sont couramment utilisées:
“Traversal en ordre imprimera les valeurs [dans l’ordre pour le BST (arbre de recherche binary)]”
“La traversée de pré-commande est utilisée pour créer une copie de [l’arbre de recherche binary].”
“La traversée de l’ordre postal est utilisée pour supprimer l’arbre de recherche binary.”
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing