5.32 A lo ancho.

Búsqueda en anchura es un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles). Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación, para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol. Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución.

El algoritmo no usa ninguna estrategia heurística. 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.

http://itpn.mx/recursosisc/1semestre/matematicasdiscretas/Unidad%20VI.pdf