Algoritmo por anchura

ALGORITMO POR 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 elementoraí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
PSEUDOCODIGO
BFS(grafo G, nodo_fuentes)
{
// 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;
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);
}
}
}
}
*Falta recorrer vertices no adyacentes directa o indirectamente al vertice origen "s",
pues cola queda vacia sin los adyacentes restantes

Estealgoritmo realiza una búsqueda en anchura en un grafo G comenzando en un nodo de partida A.
1.- Inicializar todos los nodos al estado de preparados (ESTADO = 1)
2.- Poner al nodo de partida A en COLA ycambiar su estado a espera (ESTADO = 2).
3.-Repetir pasos 4 y 5 hasta que COLA este vacía;
4.-Quitar el nodo del principio de la cola, N. Procesar N y cambiar su estado a procesado (ESTADO =...