Page 153 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 153
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Figura 7.1. Estrategias de ramificación FIFO
En la figura 7.1 se puede observar que se comienza introduciendo en la LNV el nodo A. Luego se
extrae el nodo de la cola y se expande generando los nodos B y C, que son introducidos en la LNV.
Seguidamente, se saca el primer nodo, que es el B, y se vuelve a expandir generando los nodos D y
E, que se introducen en la LNV. Este proceso se repite mientras que quede algún elemento en la cola.
estrategia lIfo
En la estrategia LIFO (last in first out), la LNV será una pila, lo que produce un recorrido en profundi-
dad del árbol.
Figura 7.2. Estrategias de ramificación LIFO
En la figura 7.2 se muestra el orden de generación de los nodos con una estrategia LIFO. El proceso
que se sigue en la LNV es similar al de la estrategia FIFO, pero en lugar de utilizar una cola se emplea
una pila.
147
