BFS Distancia

Recorrer un grafo consiste en “visitar”cada uno de los nodos a través de las aristas del mismo. Se trata de realizar recorridos de grafos de manera eficiente. Para ello, se pondrá una marca en un nodo en el momento en que es visitado, de tal manera que, inicialmente, no esta marcado ningún nodo del grafo.

BFS es un algoritmo de búsqueda que empezando en un nodo fuente, procede a procesar todos sus vecinos. Luego procesa todos los vecinos de sus vecinos y así sucesivamente hasta encontrar su destino. Es decir que primero procesa a todos los nodos que están a distancia k antes que procesar a los nodos a distancia k + 1.

La idea del procedimiento BFS(G, v) es la siguiente:
• Se marca el nodo v.
• Si todos los nodos adyacentes a v están marcados, entonces TERMINAR; si no,
marcar todos los nodos v1, v2, . . . , vk adyacentes a v que no estén marcados.
• Repetir el proceso con los nodos adyacentes a los nodos que se han marcado en el paso anterior.