Lorsqu’il traverse un arbre/graphique, quelle est la différence entre le premier largeur et profondeur d’abord ? Des exemples de codage ou pseudo-code serait formidable.
Réponses
Trop de publicités?
Ces deux termes la distinction entre deux façons différentes de pied d'un arbre.
Il est probablement plus facile simplement de faire preuve de la différence. Envisager de l'arbre:
A
/ \
B C
/ / \
D E F
Une profondeur d'abord la traversée de visiter les nœuds dans cet ordre
A, B, D, C, E, F
Notez que vous aller tout le chemin vers le bas d'une jambe avant de passer.
Une largeur de la première traversée de visiter le nœud dans cet ordre
A, B, C, D, E, F
Ici, nous travaillons tout le chemin à travers chaque niveau avant de descendre.
(À noter qu'il existe une certaine ambiguïté dans la traversée de l'ordre, et j'ai triché pour maintenir la "lecture" de l'ordre à chaque niveau de l'arbre. Dans les deux cas que j'ai pu obtenir de B avant ou après le C, et de la même manière que j'ai pu obtenir pour E avant ou après F. Cela peut ou ne peut pas d'importance, dépend de l'application...)
Les deux types de parcours peuvent être obtenus avec le pseudo-code:
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 la traversée des commandes réside dans le choix de l' Container.
- Pour la profondeur de la première utilisation d'une pile. (Le récursive de la mise en œuvre utilise la pile des appels...)
- Pour la largeur de la première utilisation d'une file d'attente.
Le récursive de la mise en œuvre 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é se termine lorsque vous atteignez un nœud qui n'a pas d'enfants, alors il est garanti à la fin de finis, les graphes acycliques.
À ce point, j'ai encore triché un peu. Avec un peu d'ingéniosité, vous pouvez également travailler sur les nœuds dans cet ordre:
D, B, E, F, C, A
qui est une variation de la profondeur d'abord, où je ne fais pas le travail à chaque nœud, jusqu'à ce que je suis en marche arrière en haut de l'arborescence. J'ai cependant visité le plus élevé de nœuds sur le chemin vers le bas pour retrouver leurs enfants.
Cette traversée est assez naturel dans le récursive de mise en œuvre (utilisation de l' "Autre temps" de la ligne ci-dessus à la place du premier "Travail" de la ligne), et pas trop dur si vous utilisez une pile explicite, mais je vais laisser cela comme un exercice.
Brian Liang
Points
4375
Ce lien m’a aidé quand j’ai appris à ce sujet.
Animation permet de visualiser. Largeur/profondeur de recherche première première recherche Animations
