El algoritmo de la búsqueda en achura

La búsqueda en anchura le asigna dos valores a cada vértice v:
  • Una distancia, que da el número mínimo de aristas en cualquier camino del vértice de origen al vértice v.
  • El vértice predecesor de v a lo largo de algún camino más corta del vértice de origen. El predecesor del vértice de origen es algún valor especial, como null, que indica que no tiene predecesor.
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 debajo 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:
Resultado BFS
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, plus, 1.
Dado el ejemplo anterior, aquí están los pasos junto con una visualización para jugar en cada paso:
  • Empieza por visitar el vértice 3, el origen, haciendo su distancia igual a 0.
  • Después visita los vértices 2 y 6, haciendo sus distancias iguales a 1 y su vértice predecesor igual al vértice 3.
  • Empieza a visitar los vértices a una distancia 1 desde el origen, empezando con el vértice 2. Del vértice 2, visita los vértices 4 y 5, haciendo sus distancias iguales a 2 y su vértice predecesor igual al vértice 2. No visites el vértice 3, porque ya fue visitado.
  • Del vértice 6, no visites el vértice 5, porque acaba de ser visitado desde el vértice 2, y tampoco visites el vértice 3.
  • Ahora empieza a visitar los vértices a una distancia 2 desde el origen. Empieza a visitar desde el vértice 4. El vértice 2 ya fue visitado. Visita el vértice 1, haciendo su distancia igual a 3 y su predecesor igual al vértice 4.
  • Del vértice 5, no visites ninguno de sus vecinos, porque ya todos fueron visitados.
  • Ahora empieza a visitar los vértices a una distancia 3 desde el origen. El único vértice así es el vértice 1. Sus vecinos, los vértices 4 y 5, ya fueron visitados. Pero el vértice 0 no. Visita el vértice 0, haciendo su distancia igual a 4 y su predecesor igual al vértice 1.
  • Ahora empieza a visitar los vértices a una distancia 4 desde el origen. Esos solo son el vértice 0 y su vecino, el vértice 1, que ya fueron visitados. ¡Terminamos!
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 sea actualmente 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:
  • enqueue(obj) inserta un objeto en la fila.
  • dequeue() quita de la fila al objeto que ha estado más tiempo en ella, regresando este objeto.
  • isEmpty() regresa true si la fila actualmente no contiene objetos y false si la fila contiene por lo menos un objeto.
Siempre que visitamos un vértice por primera vez, lo ponemos en la fila. Al principio, ponemos en la fila al 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:
  • Inicialmente, la fila contiene solo al vértice 3 con distancia 0.
  • Quita al vértice 3 de la fila e inserta en la fila a los vértices 2 y 6, ambos con distancia 1. La fila ahora contiene al vértice 2 con distancia 1 y al vértice 6 con distancia 1.
  • Quita al vértice 2 de la fila e inserta en la fila a los vértices 4 y 5, ambos con distancia 2. La fila ahora contiene al vértice 6 con distancia 1, al vértice 4 con distancia 2 y al vértice 5 con distancia 2.
  • Quita al vértice 6 de la fila y no insertes ningún otro vértice en la fila. La fila ahora contiene al vértice 4 con distancia 2 y al vértice 5 con distancia 2.
  • Quita al vértice 4 de la fila e inserta a¿en la fila al vértice 1 con distancia 3. La fila ahora contiene al vértice 5 con distancia 2 y al vértice 1 con distancia 3.
  • Quita al vértice 5 de la fila y no insertes ningún otro vértice en la fila. La fila ahora contiene solo al vértice 1 con distancia 3.
  • Quita al vértice 1 de la fila e inserta en la fila al vértice 0 con distancia 4. La fila ahora contiene solo al vértice 0 con distancia 4.
  • Quita al vértice 0 de la fila y no insertes ningún otro vértice en la fila. La fila ahora está vacía. Como la fila está vacia, la búsqueda en anchura termina.
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, plus, 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, plus, 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.