FACULTAD    DE  INFORMÁTICA

Dpto. Matemática aplicada

 

 

 

 

 


ALGORITMOS  DE  BÚSQUEDA  EN  PROFUNDIDAD  Y  EN  ANCHURA 


 

AUTOR: Samuel Gutiérrez Revenga

TUTORA: Gloria Sánchez Torrubia

 

 


 

  Introducción a la teoría de grafos

Búsqueda en Profundidad   (BEP)

Búsqueda en Anchura  (BEA)

Instrucciones para el uso del applet 

Applet para la ejecución de los algoritmos

 


 

TEORÍA DE GRAFOS

        Para la comprensión y resolución de los algoritmos de Búsqueda en Profundidad y Búsqueda en Anchura es necesario el conocimiento de una serie de conceptos básicos de la teoría de grafos que se explican a continuación:

 


 

        Así pues, un camino especifica una ruta en G que va de un vértice a otro adyacente, y así sucesivamente. Un camino puede visitar un vértice varias veces, y en particular puede cambiar de dirección yendo de x a y e inmediatamente de vuelta a x. En un camino simple, cada vértice se visita una vez como máximo.

        Se escribe x ~ y, y se dice que x es accesible desde y, si los vértices de x e y de G pueden unirse por un camino en G: hablando con  precisión, esto significa  que existe un camino  v1, a1, v2, , a2,  ... , aj-1, vj en G tal que x = v1 e y = vj. Es sencillo comprobar que ~ es una relación de equivalencia en el conjunto de vértices V de G, con lo que V queda dividido en clases de equivalencia. Dos vértices están en la misma clase si pueden unirse por un camino y en clases distintas en caso contrario.

 

 


 

       [ inicio ]

 

 

BÚSQUEDA EN PROFUNDIDAD  (BEP)

       Se comienza en el vértice inicial (vértice con índice 1) que se marca como vértice activo. Hasta que todos los vértices hayan sido visitados, en cada paso se avanza al vecino con el menor índice siempre que se pueda, pasando este a ser el vértice activo. Cuando todos los vecinos al vértice activo hayan sido visitados, se retrocede al vértice X desde el que se alcanzó el vértice activo y se prosigue siendo ahora X el vértice activo.  

        Sea G = (V, A) un grafo conexo, V’ = V  un conjunto de vértice, A’un vector de arcos inicialmente vacío y P un vector auxiliar inicialmente vacío:

  1. Se introduce el vértice inicial en P y se elimina del conjunto V’.
  2. Mientras V’ no sea vacío repetir los puntos 3 y 4. En otro caso parar.
  3. Se toma el último elemento de P como vértice activo.
  4. Si el vértice activo tiene algún vértice 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 vértice activo.

Si el vértice activo no tiene adyacentes se elimina de P.

 
     [ inicio ]

 

 

BÚSQUEDA ANCHURA  (BEA)

        Se comienza en el vértice inicial (vértice con índice 1) y se marca como vértice activo, a  diferencia con la BEP ahora se visitan en orden creciente de índice todos los vecinos del vértice activo antes de pasar al siguiente. Hasta que todos los vértices hayan sido visitados, en cada paso se van visitando en orden creciente de índice todos los vecinos del vértice activo. Cuando se han visitado todos los vecinos del vértice activo, se toma como nuevo vértice activo el primer vértice X visitado después del actual vértice activo en el desarrollo del algoritmo.

    Sea G = (V, A) un grafo conexo, V’ = V un conjunto de vértices, A’ un vector de arcos inicialmente vacío y P un vector auxiliar inicialmente vacío:

  1. Se introduce el vértice inicial en P y se elimina del conjunto.

  2. Mientras V’ no sea vacío repetir los puntos 3 y 4. En otro caso parar.
  3. Se toma el primer elemento de P como vértice activo.
  4. Si el vértice activo tiene algún vértice 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 vértice activo.

Si el vértice activo no tiene adyacentes se elimina de P.

 
    [ inicio ]

 

 

INSTRUCCIONES DE USO DEL APPLET

        El proceso consta de dos fases, en la primera de ellas hay que construir el grafo al que queremos aplicar el algoritmo, una  vez que se ha construido el grafo se pasa a  la segunda fase que es la de resolución del algoritmo.

        Comenzando por el vértice inicial (vértice con índice 1), presionar sobre los vértice en el orden en el que aparecen en la solución del algoritmo seleccionado. Si el vértice seleccionado no es el siguiente en la solución del algoritmo aparecerá un mensaje de error en otro caso seleccionar el vértice siguiente.

        Durante la fase de resolución del algoritmo se irán marcando en color verde los vértice pertenecientes a la solución  y en color azul los arcos pertenecientes a la solución, además el vértice activo de la solución se marcará en color azul claro.

- Volver a la fase de construcción: En cualquier momento del desarrollo de la fase de resolución del algoritmo se puede volver a la fase de construcción del grafo presionando el botón "Modo dibujo". De esta manera se puede construir otro grafo partiendo del grafo actual.

- Reiniciar la resolución: En cualquier momento del desarrollo de la fase de resolución del algoritmo se puede reiniciar la resolución desde el principio presionando el botón "Resolver algoritmo". También se puede aplicar otro tipo de algoritmo al mismo grafo seleccionando previamente "BProfundidad" o "BAnchura".

- Crear un nuevo grafo: Una vez que se ha terminado con éxito la resolución del algoritmo se puede regresar a la fase de construcción del grafo pulsando el botón "Nuevo grafo". De esta forma se comienza la construcción de un nuevo grafo para posteriormente ser resuelto por alguno de los algoritmos mencionados.

 

   [ inicio ]