•          Búsqueda en anchura empezando en un nodo v:

–         Primero se visita v.

–         Luego se visitan todos sus adyacentes.

–         Luego los adyacentes de estos y así sucesivamente.

•          El algoritmo utiliza una cola de vértices.

•          Operaciones básicas:

–         Sacar un elemento de la cola.

–         Añadir a la cola sus adyacentes no visitados.

Método donde se hace el llamado a bpa() (búsqueda primero en anchura)

operación BúsquedaPrimeroEnAnchura

                BorraMarcas

                para v:= 1, ..., n hacer

                                si marca[v] = noVisitado entonces

                                       bpa(v)

                finpara

 Algoritmo de búsqueda primero en anchura

operación bpa (v: Nodo)

var  C: Cola[Nodo]

        x, y: Nodo

                marca[v]:= visitado

                InsertaCola (v, C)

                mientras NOT EsVacíaCola (C) hacer

                      x:= FrenteCola (C)

                      SuprimirCola (C)

                      para cada nodo y adyacente a x hacer

                           si marca[y] == noVisitado entonces

                                       marca[y]:= visitado

                                       InsertaCola (y, C)

                                   finsi

                      finpara

                finmientras

Ejemplo 1 Grafo no dirigido.

Árbol de expansión en anchura.

Ejemplo 2 Grafo dirigido.                                 Árbol de expansión en anchura.

•          ¿Cuánto es el tiempo de ejecución de la BPA?

•          ¿Cómo comprobar si un arco es de avance, cruce, etc.?

•          Solución: Construir el bosque explícitamente.