ALGORITMO DE BÚSQUEDA: BREADTH FIRST SEARCH (BFS)

Descripción

Este algoritmo de grafos es muy útil en diversos problemas de programación. Por ejemplo halla la ruta más corta cuando el peso entre todos los nodos es 1, cuando se requiere llegar con un movimiento de caballo de un punto a otro con el menor numero de pasos, cuando se desea tranformar algo un numero o cadena en otro realizando ciertas operaciones como suma producto, pero teniendo en cuenta que no sea muy grande el proceso de conversion, o para salir de un laberinto con el menor numero de pasos , etc. Podrán aprender a identificarlos con la práctica.


Algoritmo en pseudocódigo

1 método BFS(Grafo,origen):
2 creamos una cola Q
3 agregamos origen a la cola Q
4 marcamos origen como visitado
5 mientras Q no este vacío:
6 sacamos un elemento de la cola Q llamado v
7 para cada vertice w adyacente a v en el Grafo:
8 si w no ah sido visitado:
9 marcamos como visitado w
10 insertamos w dentro de la cola Q

  BFS(grafo G, nodo_fuente s) 
  { 
     // recorremos todos los vértices del grafo inicializándolos a NO_VISITADO,
     // distancia INFINITA y padre de cada nodo NULL
     for u ∈ V[G] do
     {
        estado[u] = NO_VISITADO;
        distancia[u] = INFINITO; /* distancia infinita si el nodo no es alcanzable */
        padre[u] = NULL;
     }
     estado[s] = VISITADO;
     distancia[s] = 0;
     padre[s] = NULL;
     CrearCola(Q); /* nos aseguramos que la cola está vacía */
     Encolar(Q, s);
     while !vacia(Q) do
     {
        // extraemos el nodo u de la cola Q y exploramos todos sus nodos adyacentes
        u = extraer(Q);
        for  v ∈ adyacencia[u]  do
        {
           if estado[v] == NO_VISITADO then
           {
                estado[v] = VISITADO;
                distancia[v] = distancia[u] + 1;
                padre[v] = u;
                Encolar(Q, v);
           }
        }
     }
  }