"""
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 recorrido hasta llegar a la letra a buscar
camino=[]
def buscar(inicio,valorBuscar):
"""
Funcion recursiva para buscar en profundidad
Tiene que recibir:
- el valor inicial donde empezar a buscar
- el valor a buscar en su estructura
Devuelve el valor a buscar o 0 si no lo encuentra
"""
camino.append(inicio)
# si encontramos el elemento, lo devolvemos
if inicio==valorBuscar:
return valorBuscar
# recorremos todos los elementos en busca del valor de inicio
for k,v in valores.items():
# si el valor del elemento tiene como padre al valor de inicio
if v==inicio:
# llamamos a la función recursivamente enviando el nuevo padre
result=buscar(k,valorBuscar)
# si hemos recibido algun resultado es que hemos encontrado el
# elemento que buscamos
if result:
return result
camino.pop()
# si llegamos aqui, es que hemos llegado al final de una profundidad
return 0
result=buscar("a","o")if result:
print(camino)
else:
print("no encontrado")
Comentarios sobre la versión: Versión 1 (6)
Será que lo pueden hacer ejecutable?
Imagino que la idea de este ejercicio es encontrar la ruta desde inicio hasta valorBuscar.
Si es el caso, hay un detalle con esta versión: En algunos casos incluye en los resultados nodos que no forman parte de la ruta. La razón es que busca siempre en todos los elementos del diccionario valores.
Por ejemplo, esta versión del código da los siguientes resultados;
buscar('a','o') = ['a', 'b', 'f', 'm', 'o']
buscar('a','g') = ['a', 'b', 'f', 'm', 'o', 'a', 'c', 'h', 'g']
buscar('a','l') = ['a', 'b', 'f', 'm', 'o', 'a', 'c', 'h', 'g', 'a', 'd', 'j', 'l']
buscar('c','g') = ['a', 'b', 'f', 'm', 'o', 'a', 'c', 'h', 'g', 'a', 'd', 'j', 'l', 'c', 'h', 'g']
buscar('o','g') = no encontrado
buscar('b','g') = no encontrado
buscar('x','y') = no encontrado
Redefiniendo la funcion buscar de la siguiente manera:
def buscar( inicio , valorBuscar ):
# Encontrar todos los nodos cuyo padre es inicio
children = [k for k,v in valores.items() if v == inicio]
# Si inicio tiene hijos
if children :
# Si el valorBuscar es hijo de inicio
if valorBuscar in children :
# Devolver una lista con ambos valores como elementos
return [inicio,valorBuscar]
# de lo contrario buscar en cada nodo hijo
else :
for child in children :
# de manera recursiva
nextNode = buscar( child , valorBuscar )
if nextNode :
# hasta encontrar valorBuscar
return [inicio]+nextNode
# y retornar None si valorBucar no es concontrado en el árbol de ninguno de sus hijos
return None
# Si inicio no tiene hijos no hay camino a valorBuscar
else :
return None
Estos son los resultados:
buscar('a','o') = ['a', 'b', 'f', 'm', 'o']
buscar('a','g') = ['a', 'c', 'h', 'g']
buscar('a','l') = ['a', 'd', 'j', 'l']
buscar('c','g') = ['c', 'h', 'g']
buscar('o','g') = no encontrado
buscar('b','g') = no encontrado
buscar('x','y') = no encontrado
Aquí la idea es buscar solo en los nodos hijos de inicio, ignorando el resto de los nodos.
Luego hay otra cuestión práctica para el caso de los diccionarios: Cada key es única, por lo que podría determinarse directamente si inicio y valorBuscar existen como key. Y también si solo existen como value en el diccionario valores, en cuyo caso sabemos que se trata del Nodo al tope del árbol.
Suponiendo que valorBuscar pertenece al arbol de inicio, se puede hacer la búqueda en sentido contrario, es decir desde valorBuscar hasta inicio:
Esta búsqueda devuelve una ruta invertida, la cual puede luego ser reordenada.
def RutaEntreNodos( valorBuscar , inicio ) :
camino = []
actual = valorBuscar
while actual in valores.keys() :
padre = valores[actual]
camino.append(actual)
if actual == inicio :
return camino
actual=padre
# El elemento al tope del arbol no es un key en el diccionario valores porque no tiene un nodo padre. Solo aparece en el diccionario como value
if actual in valores.values() :
camino.append(actual)
# Para asegurarnos que valorBuscar sea el último elemento del camino = inicio
if actual == inicio :
return camino
else :
return None
Y por supuesto, se podría ampliar para establecer una ruta entre dos nodos aunque no estén en la misma rama del árbol.
PD: La imagen 5b4debf423386-arbol-busqueda-en-profundidad.png tiene un error. El elemento M aparece repetido. El error está en A-C-H-M que deb ser cambiado a A-C-H-G.
buscar('a','g') = ['a', 'c', 'h', 'g']
buscar('a','l') = ['a', 'd', 'i']
buscar('c','g') = ['c', 'h', 'g']
he actualizado la imagen, gracias por comentarlo!!!
Tienes razón.
Ya me di cuenta de mi error.
Ejecuté las pruebas, una detrás de la otra, en el mismo script, y por supuesto el contenido de camino seguía manteniendo los valores de la búsqueda anterior.
Saludos y disculpa mi torpeza.