Breadth-first search

Dado un grafo $G = (V, E)$ y un vértice source $s$, el algoritmo BFS explora sistemáticamente las aristas de $G$ para descubrir todos los vértices de $v \in V$ alcanzables desde $s$. En este proceso:

• Computa la distancia (mínimo número de vértices) desde $s$ a todo nodo alcanzable $v$.
• Produce un “árbol BFS” de raíz $s$ que contiene todos los nodos alcanzables. Para cada nodo $v \in V$ alcanzable desde $s$, el camino en el árbol BFS de $s$ a $v$ se corresponde con el camino mínimo (en vértices) de $s$ a $v$ en $G$.

El nombre de BFS proviene de que el algoritmo explora la frontera entre los vértices descubiertos y los no descubiertos de manera uniforme, visitando todos los vértices a distancia $k$ de $s$ antes de visitar cualquiera a distancia $k + 1$.

Para ir registrando el estado del procedimiento, BFS utiliza tres colores para los vértices de $G$:

• Blanco para los vértices todavía no explorados
• Gris para los vértices ya explorados que están en la frontera de exploración, es decir, existe al menos una arista que lo une con un vértice blanco (sin explorar)
• Negro para los vértices ya explorados que todas sus aristas los unen con vértices grises o negros. Es decir, ya fueron explorados y también fue explorada toda su vecindad

BFS comienza agregando $s$ al árbol. Al descubrir un nuevo vértice $v$ en la vecindad del nodo ya explorado $u$, agregamos el nodo $v$ y la arista $(u, v)$ al árbol. Es decir, $u$ resulta el predecesor (padre) de $v$. Como cada vértice es descubierto a lo sumo una vez, cada vértice tiene a lo sumo un padre.

Es importante notar que las relaciones entre ancestros y descendientes son relativas a la raíz $s$.

Pseudocódigo

BFS(G, s)
1 	for each vertex u in G.V - {s}:
2 		u.color = WHITE
3 		u.dist = INF
4 		u.parent = NULL
5 	s.color = GRAY
6 	s.dist = 0
7 	sl.parent = NULL
8	  Q = emptySet
9 	enqueue(Q, s)
10	while Q != emptySet:
11		u = dequeue(Q)
12		for each v in G.adj(u)
13			if v.color == WHITE:
14				v.color = GRAY
15				v.dist = u.dist + 1
16				v.parent = u
17				enqueue(Q, v)
18		u.color = BLACK