BÚSQUEDA EN ANCHURA

La idea general de la búsqueda en anchura comenzando en un nodo de partida A es la siguiente. Primero examinamos el nodo de partida A. luego examinamos todos los vecinos de A. luego examinamos todos los vecinos de los vecinos de A. y así sucesivamente. naturalmente, necesitamos seguir la pista a los vecinos de un nodo y tenemos que garantizar que ningún nodo se procesa mas de una vez. Esto se hace usando una cola para mantener los nodos que estén esperando para ser procesados y usando un campo ESTADO que nos diga el estado actual de los nodos.

BUSQUEDA EN PROFUNDIDAD

La idea general de la búsqueda en profundidad comenzando en un nodo A es la siguiente. Primero examinamos el nodo inicial A. luego examinamos cada nodo N de un camino P que comience en A; o sea, procesamos un vecino de A, luego un vecino de un vecino de un vecino A así sucesivamente tras llegar un “punto muerto “o sea, el final del camino P, volveremos atrás por P hasta que podamos conseguir por otro camino P´. y  a si sucesivamente. (Este algoritmo es similar al recorrido inorden de un árbol binario, y también a la forma en que se debe pasar a través de  un laberinto). El algoritmo es muy similar al de búsqueda en anchura excepto que usamos una pila en lugar de una cola. De nuevo se usa un campo ESTADO para indicar el estado actual de un nodo .

El algoritmo es el siguiente:

Algoritmo B: este algoritmo realiza una búsqueda en profundidad en el grafo G comenzando en un nodo A.

1.    Inicializar con todos los nodos al estado de preparado (ESTADO =1).

2.    Meter el nodo inicial A en la pila y cambiar su estado a estado de espera (ESTADO=2).

3.    Repetir paso 4 y 5 hasta que la pila esta  vacia.

4.    Sacar el nodo N en la cima de la pila. Procesar el nodo N  y cambiar un estado al de procesado (ESTADO =3).

5.    Meter en la pila todos los vecinos de N que estén en estado de preparados (ESTADO=1) y cambiar su estado al de espera (ESTADO =2). [fin del bucle del paso 3]

6.    salir   

de nuevo este algoritmo procesa solo los nodos que sean alcanzables desde el nodo de partida A.si queremos examinar todos los nodos G entonces el algoritmo debe ser modificado para que comience de nuevo con otro nodo que llamaremos B que este en estado de preparado, este nodo se puede obtener recorriendo la lista de nodos.