Búsqueda en anchura (BFS)
Tira una piedra a un estanque y las ondas se extienden en anillos regulares. La búsqueda en anchura explora un grafo de la misma manera: primero todo lo que está a un paso del origen, luego todo lo que está a dos pasos, y así sucesivamente. Ese orden tan simple es lo que le permite encontrar caminos más cortos.
La idea
Un grafo es un conjunto de nodos unidos por aristas: lugares y carreteras, personas y amistades, casillas de un laberinto y los pasos entre ellas. La búsqueda en anchura responde a la pregunta: empezando aquí, ¿a qué puedo llegar y en cuántos pasos como mínimo? Mantiene una cola de nodos por visitar. Como toma los nodos del frente y añade los nuevos al final, los nodos se procesan en el orden en que se descubrieron.
Paso a paso
Pon el origen en la cola a distancia 0. Toma el nodo del frente. Para cada vecino que aún no se ha visto, anota como distancia la del nodo actual más uno, recuerda el nodo actual como aquel desde el que se llegó a él y añádelo al final de la cola. Salta los vecinos ya vistos. Repite hasta que la cola esté vacía o hasta alcanzar el destino.
Un ejemplo
Toma un grafo con las aristas A–B, A–C, B–D, C–D, C–E y D–F, y empieza en A. Al sacar A de la cola se encuentran B y C a distancia 1. Al sacar B se encuentra D a distancia 2. Al sacar C se ve que D ya se había visto, y se encuentra E a distancia 2. Al sacar D se encuentra F a distancia 3. E y F no encuentran nada nuevo, y la cola queda vacía. Seguir los nodos recordados desde F da F ← D ← B ← A, así que un camino más corto de A a F es A → B → D → F, de tres aristas.
Por qué las distancias son correctas
Cada nodo a distancia 1 entra en la cola antes que cualquier nodo a distancia 2, cada nodo a distancia 2 antes que cualquiera a distancia 3, y así sucesivamente, porque los vecinos de un nodo solo entran en la cola cuando el propio nodo sale de ella. Así que el primer camino que alcanza un nodo es uno con el menor número de aristas, y BFS nunca tiene que corregir una distancia. Cada nodo se toma una vez y cada arista se mira desde sus dos extremos, así que el trabajo crece con el número de nodos más el número de aristas.
Historia y usos
Konrad Zuse describió la búsqueda en anchura en 1945, en un trabajo sobre su lenguaje Plankalkül que no se publicó hasta 1972. Edward F. Moore la reinventó en 1959 para encontrar el camino más corto para salir de un laberinto, y C. Y. Lee la usó en 1961 para trazar pistas en placas de circuito. Hoy encuentra el menor número de movimientos en rompecabezas, los grados de separación en redes sociales, las páginas a las que un rastreador web llega primero y la casilla libre más cercana en los videojuegos. Cuando las aristas tienen longitudes, el algoritmo de Dijkstra la generaliza.
Explórala
Abre la aplicación y pulsa Paso. El nodo que se está visitando aparece resaltado, los nodos que esperan en la cola son azules y los visitados son verdes, cada uno con su distancia. La cola se muestra bajo el grafo, con el frente primero. Cambia el clic a Destino y elige un nodo para parar allí y ver el camino más corto, o crea un grafo nuevo con más nodos y aristas.
Preguntas frecuentes
¿Cuál es la complejidad temporal de BFS?
O(V + E) para V nodos (vértices) y E aristas: cada nodo entra y sale de la cola una vez, y cada arista se examina desde sus dos extremos. Necesita O(V) de memoria extra para la cola y las distancias.
¿Por qué BFS usa una cola?
Porque «el primero en entrar es el primero en salir» mantiene los nodos en el orden en que se descubrieron, que es el orden de su distancia. Con una pila, la búsqueda bajaría primero en profundidad: eso es la búsqueda en profundidad.
¿Puede BFS encontrar caminos más cortos en grafos ponderados?
En general, no: cuenta aristas, no sus longitudes. Para grafos ponderados sin aristas negativas, usa el algoritmo de Dijkstra. Si cada peso es 0 o 1, funciona una variante llamada BFS 0-1.
¿Dónde se usa BFS?
Para resolver rompecabezas y laberintos con el menor número de movimientos, encontrar amigos de amigos en redes sociales, rastrear la web nivel a nivel, difundir mensajes en redes y como pieza de otros algoritmos, por ejemplo para hallar flujos máximos.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Prueba la búsqueda en anchura