Algoritmo Bsqueda en Profundidad*Se comienza en el vrtice inicial (vrtice con ndice 1) que se marca como vrtice activo. Hasta que todos los vrtices hayan sido visitados, en cada paso se avanza al vecino con el menor ndice siempre que se pueda, pasando este a ser el vrtice activo. Cuando todos los vecinos al vrtice activo hayan sido visitados, se retrocede al vrticeXdesde el que se alcanz el vrtice activo y se prosigue siendo ahora Xel vrtice activo.

ALGORITMO DFS:Sea G = (V, A) un grafo conexo,V = Vun conjunto de vrtices,A un vector de arcos inicialmente vaco y P un vector auxiliar inicialmente vaco:

Se introduce el vrtice inicial en P y se elimina del conjuntoV.MientrasVno sea vaco repetir los puntos 3 y 4. En otro caso parar.Se toma el ltimo elemento de P como vrtice activo.Si el vrtice activo tiene algn vrtice adyacente que se encuentre enV:Se toma el de menor ndice.Se inserta en P como ltimo elemento.Se elimina de V.Se inserta en A el arco que le une con el vrtice activo.Si el vrtice activo no tiene adyacentes se elimina de P.

Implementacin mediante un Applet*http://www.dma.fi.upm.es/java/matematicadiscreta/busqueda/pag_applet.htm#applet

Implementacin mediante un Applet*1) Primera iteracin, busco en V' el de menor ndice

Implementacin mediante un Applet*2) Segunda iteracin, Se elimina (5) de V' y se toma como si fuera nodo inicial, se repite el paso 1)

Implementacin mediante un Applet* N iteraciones repetidas, a pesar de que la solucin esta a un paso, el algoritmo debe visitar el siguiente nodo de menor ndice.

Implementacin mediante un Applet*La bsqueda se extendera hasta que V' solo contenga el nodo destino.

Implementacin mediante un Applet*Cuando llegamos a 11, no hay que mas visitar y empezamos a retroceder hasta el nodo que tenga un nodo por visitar, se llega finalmente a la solucion

Implementacin mediante un Applet*Finalmente la solucin visita todos los nodos

Algoritmo de Bsqueda en Anchura*Se comienza en el vrtice inicial (vrtice con ndice 1) y se marca como vrtice activo, a diferencia con la BEP ahora se visitan en orden creciente de ndice todos los vecinos del vrtice activo antes de pasar al siguiente. Hasta que todos los vrtices hayan sido visitados, en cada paso se van visitando en orden creciente de ndice todos los vecinos del vrtice activo. Cuando se han visitado todos los vecinos del vrtice activo, se toma como nuevo vrtice activo el primer vrticeXvisitado despus del actual vrtice activo en el desarrollo del algoritmo.ALGORITMO BEA:Sea G = (V, A)un grafo conexo,V = Vun conjunto de vrtices,Aun vector de arcos inicialmente vaco yP un vector auxiliar inicialmente vaco:Se introduce el vrtice inicial en P y se elimina del conjunto.Mientras V no sea vaco repetir los puntos 3 y 4. En otro caso parar.Se toma el primer elemento de P como vrtice activo.Si el vrtice activo tiene algn vrtice adyacente que se encuentre en V:Se toma el de menor ndice.Se inserta en P como ltimo elemento.Se elimina de V.Se inserta en A el arco que le une con el vrtice activo.Si el vrtice activo no tiene adyacentes se elimina de P.

Implementacin mediante un Applet*Ntese la primera iteracin.

Implementacin mediante un Applet*Segunda iteracin se busca el de menor ndice.

Implementacin mediante un Applet*

Implementacin mediante un Applet*

Implementacin mediante un Applet*

Implementacin mediante un Applet*La solucin igual que en DFS termina por visitar todos los NODOS

*

*

*

*

*

*

*Los mtodos anteriores entonces quedan obsoletos y sern reemplazados por bsquedas informadas.