"""
Cada elemento de este diccionario contiene una posicion y como valor tiene
el nombre de su elemento padre en el arbol
a
/ | \
b c d
/ \ | / \
e f h i j
| | | |
k m g l
/ \
n o
"""
valores={ "b":"a",
"c":"a",
"d":"a",
"e":"b",
"f":"b",
"h":"c",
"i":"d",
"j":"d",
"k":"e",
"m":"f",
"g":"h",
"l":"j",
"n":"m",
"o":"m"
}
# variable que contiene el camino que recorre el algoritmo
camino=[]
# variable que contiene la cola de elementos a revisar
# First In, First Out
fifo=[]
def buscar(inicio,valorBuscar,iteraciones):
"""
Funcion recursiva para buscar en anchura
Tiene que recibir:
- el valor inicial donde empezar a buscar
- el valor a buscar en su estructura
- el contador de interaciones
Devuelve True o False y el valor de interaciones realizadas para encontrar
el elemento
"""
camino.append(inicio)
# Si encontramos el elemento, lo devolvemos
if inicio==valorBuscar:
return (True,iteraciones)
# Añadimos los elementos al fifo
fifoAdd(inicio)
# Si no hay elementos en el fifo, es que hemos llegado al final y no ha
# encontrado el elemento
if len(fifo)==0:
return (False,iteraciones)
# Llamamos nuevamente a la función pasando el primer elemento añadido a la
# fifo y aumentando la variable de la interacion
return buscar(fifo.pop(0),valorBuscar,iteraciones+1)
def fifoAdd(inicio):
"""
Función para buscar los elementos hijos a un elemento dado y añadirlos
a la variable fifo
"""
for k,v in valores.items():
if v==inicio:
fifo.append(k)
resultado,iteraciones=buscar("a","f",1)if resultado:
print("Ha encontrado el valor en {} iteraciones".format(iteraciones))else:
print("No se ha encontrado")print("El camino que ha realizado ha sido: {}".format(camino))
Crear cuenta
Comentarios sobre la versión: Versión 1 (0)
No hay comentarios