Primero algoritmo de búsqueda en profundidad no recursivo [cerrado]
Estoy buscando un algoritmo de primera búsqueda en profundidad no recursivo para un árbol no binario. Cualquier ayuda es muy apreciada.
Aceptado
DFS:
list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
currentnode = nodes_to_visit.take_first();
nodes_to_visit.prepend( currentnode.children );
//do something
}
BFS:
list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
currentnode = nodes_to_visit.take_first();
nodes_to_visit.append( currentnode.children );
//do something
}
La simetría de los dos es bastante interesante.
Actualización: como se señaló, take_first()elimina y devuelve el primer elemento de la lista.
Usarías una pila que contenga los nodos que aún no fueron visitados:
stack.push(root)
while !stack.isEmpty() do
node = stack.pop()
for each node.childNodes do
stack.push(stack)
endfor
// …
endwhile
Si tiene punteros a nodos principales, puede hacerlo sin memoria adicional.
def dfs(root):
node = root
while True:
visit(node)
if node.first_child:
node = node.first_child # walk down
else:
while not node.next_sibling:
if node is root:
return
node = node.parent # walk up ...
node = node.next_sibling # ... and right
Tenga en cuenta que si los nodos secundarios se almacenan como una matriz en lugar de a través de punteros hermanos, el siguiente hermano se puede encontrar como:
def next_sibling(node):
try:
i = node.parent.child_nodes.index(node)
return node.parent.child_nodes[i+1]
except (IndexError, AttributeError):
return None
