El algoritmo de la búsqueda en achura

La búsqueda en anchura le asigna dos valores a cada vértice $v$‍:

Si no hay un camino del vértice de origen al vértice $v$‍, entonces la distancia de $v$‍ es infinita y su predecesor tiene el mismo valor especial que el predecesor del vértice de origen.

Por ejemplo, aquí hay un grafo no dirigido con ocho vértices, numerados del 0 al 7, con los números de los vértices mostrados arriba o abajo de los vértices. Dentro de cada vértice hay dos números: su distancia del origen, que es el vértice 3, seguido de su predecesor en el camino más corto desde el vértice 3. Un guion indica null:

En BFS, inicialmente hacemos que la distancia y el predecesor de cada vértice sea el valor especial (null). Empezamos la búsqueda en el origen y le asignamos una distancia de 0. Después visitamos a todos los vecinos del origen y a cada vecino le damos una distancia de 1 y hacemos su predecesor igual al origen. Después visitamos a todos los vecinos de los vértices cuya distancia es 1 y que no han sido visitados anteriormente, y le damos a cada uno de estos vértices una distancia de 2 y hacemos que su predecesor sea el vértice a partir del cual lo visitamos. Seguimos avanzando hasta que todos los vértices alcanzables desde el vértice de origen han sido visitados, siempre visitando los vértices a una distancia $k$‍ del origen antes de visitar cualquier vértice a una distancia $k+1$‍.

Dado el ejemplo anterior, aquí están los pasos junto con una visualización para jugar en cada paso:

Observa que como no hay un camino del vértice 3 al vértice 7, la búsqueda nunca visita el vértice 7. Su distancia y predecesor permanecen sin cambiar sus valores iniciales de null.

Aparecen un par de preguntas. Una es cómo determinar si un vértice ya fue visitado. Eso es fácil: la distancia de un vértice es null hasta que haya sido visitado, en cuyo momento obtiene un valor numérico para su distancia. Por lo tanto, cuando examinamos los vecinos de un vértice, solamente visitamos a los vecinos cuya distancia actualmente sea null.

La otra pregunta es cómo llevar un registro de cuáles vértices ya fueron visitados, pero que no hemos visitado a partir de ellos. Usamos un queue (o una fila), que es una estrucutra de datos que nos permite insertar y quitar elementos, donde el elemento que se quita siempre es el que ha estado en la fila por más tiempo. A este comportamiento lo llamamos primero en entrar, primero en salir. Una fila tiene tres operaciones:

Siempre que visitamos un vértice por primera vez, lo ponemos en la fila. Al principio, ponemos en la fila el vértice de origen porque ese siempre es el primer vértice que visitamos. Para decidir qué vértice visitamos después, escogemos el vértice que ha estado en la fila por más tiempo y lo quitamos de la fila. En otras palabras, usamos el vértice que regresa dequeue(). Dado nuestro grafo de ejemplo, aquí está cómo se ve la fila para cada paso, mostrada junto con la visualización anterior con el estado de la fila:

Ten en cuenta que en cada momento, la fila contiene vértices todos con la misma distancia o contiene vértices con distancia $k$‍ seguidos de vértices con distancia $k+1$‍. Así es como nos aseguramos de visitar todos los vértices a una distancia $k$‍ antes de visitar cualquier vértice a una distancia $k+1$‍.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.