Comment garder la trace de la profondeur en première recherche?
J'ai un arbre d'entrée de la largeur de recherche et je veux savoir que l'algorithme progresse à quel niveau il est?
# Breadth First Search Implementation
graph = {
'A':['B','C','D'],
'B':['A'],
'C':['A','E','F'],
'D':['A','G','H'],
'E':['C'],
'F':['C'],
'G':['D'],
'H':['D']
}
def breadth_first_search(graph,source):
"""
This function is the Implementation of the breadth_first_search program
"""
# Mark each node as not visited
mark = {}
for item in graph.keys():
mark[item] = 0
queue, output = [],[]
# Initialize an empty queue with the source node and mark it as explored
queue.append(source)
mark[source] = 1
output.append(source)
# while queue is not empty
while queue:
# remove the first element of the queue and call it vertex
vertex = queue[0]
queue.pop(0)
# for each edge from the vertex do the following
for vrtx in graph[vertex]:
# If the vertex is unexplored
if mark[vrtx] == 0:
queue.append(vrtx) # mark it as explored
mark[vrtx] = 1 # and append it to the queue
output.append(vrtx) # fill the output vector
return output
print breadth_first_search(graph, 'A')
Il faut de arbre comme un graphique d'entrée, ce que je veux dire, c'est qu'à chaque itération, il doit imprimer le niveau actuel qui est en cours de traitement.
source d'informationauteur functioncall | 2015-07-06
Vous devez vous connecter pour publier un commentaire.
Vous n'avez pas besoin d'utiliser extra file d'attente ou n'importe quel calcul compliqué d'obtenir ce que vous voulez faire. Cette idée est très simple.
Ce n'utilise pas tout l'espace supplémentaire autre que la file d'attente utilisée pour BFS.
L'idée que je vais utiliser est d'ajouter
null
à la fin de chaque niveau. Ainsi, le nombre de valeurs null, vous rencontrées +1 est la profondeur. (bien sûr après la fin c'est justelevel
).Maintenir une file d'attente de stockage de la profondeur du nœud correspondant dans la SECTION de la file d'attente. Exemple de code pour votre information:
Cette méthode est simple et naive, par O(1) de l'espace supplémentaire, vous aurez besoin de la réponse post par @stolen_leaves.
Essayer d'avoir un coup d'oeil à ce post. Il garde la trace de la profondeur à l'aide de la variable
currentDepth
https://stackoverflow.com/a/16923440/3114945
Pour votre mise en œuvre, de garder trace de la plus à gauche du nœud et une variable pour la profondeur. Chaque fois que le nœud le plus à gauche est sorti de la file d'attente, vous savez que vous atteignez un nouveau niveau et vous incrémenter la valeur de la profondeur.
Donc, votre racine est la
leftMostNode
au niveau 0. Ensuite, le plus à gauche de l'enfant est laleftMostNode
. Dès que vous le frappez, il devient de niveau 1. La gauche de la plupart des enfants de ce nœud est la prochaineleftMostNode
et ainsi de suite.Si votre arbre est parfaitement ballanced (c'est à dire que chaque nœud a le même nombre d'enfants) il y a en fait une solution simple et élégante ici avec O(1) fois la complexité et O(1) l'espace de la complexité. Les principaux cas d'utilisation où je peux trouver cela utile est en parcourant un arbre binaire, mais il est trivialement adaptable à d'autres arbres de tailles.
La clé de chose à comprendre ici est que chaque niveau d'un arbre binaire contient exactement le double de la quantité de nœuds par rapport au niveau précédent. Cela nous permet de calculer le nombre total de nœuds dans un arbre donné de l'arbre de profondeur. Par exemple, considérons l'arbre suivant:
Cet arbre a une profondeur de 3 et 7 nœuds. Nous n'avons pas besoin de compter le nombre de nœuds à comprendre cela. Nous pouvons calculer cette en O(1) fois avec le formaula: 2^d - 1 = N, où
d
est la profondeur et laN
est le nombre total de nœuds. (Dans un arbre ternaire, c'est 3^d - 1 = N, et dans un arbre où chaque nœud a K les enfants, c'est K^d - 1 = N). Donc dans ce cas, 2^3 - 1 = 7.De garder une trace de la profondeur tandis que la réalisation d'une largeur de recherche, nous avons simplement besoin d'inverser ce calcul. Alors que la formule ci-dessus nous permet de résoudre pour
N
donnéd
en fait, nous voulons résoudre pourd
donnéN
. Par exemple, dire que nous sommes sur l'évaluation de la 5e nœud. Pour comprendre ce que la profondeur de la 5e noeud est sur, nous prenons l'équation suivante: 2^d - 1 = 5, puis simplement résoudre pourd
qui est la base de l'algèbre:Si
d
s'avère être rien d'autre qu'à un nombre entier, juste arrondir (le dernier nœud dans une ligne est toujours un nombre entier). Avec que tous, dans l'esprit, je propose l'algorithme suivant pour identifier la profondeur d'un nœud dans un arbre binaire au cours de la largeur de la première traversée de l':visited
égale à 0.visited
par 1.visited
est incrémenté de calculer le nœud de profondeurdepth = round_up(log2(visited + 1))
Vous pouvez également utiliser une table de hachage à la carte chaque nœud à son niveau de profondeur, si ce n'est augmenter l'espace de la complexité à O(n). Voici un PHP de mise en œuvre de cet algorithme:
Qui imprime: