Visitados
En la cola
Aristas revisadas

  • Actual
  • En la cola
  • Visitado
  • Camino
Un clic en un nodo fija

Más sobre la búsqueda en anchura

Búsqueda en anchura (BFS)

La búsqueda en anchura explora un grafo por anillos: primero cada nodo junto al origen, luego cada nodo a dos aristas, y así sucesivamente. Lo hace con una cola: el primero en entrar es el primero en salir. Haz clic en un nodo para empezar desde él, elige un destino si quieres, y avanza paso a paso para ver cómo la cola crece y se vacía, cada nodo recibe su distancia y aparece un camino más corto. Pulsa Reproducir para ver la búsqueda, o Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto. Haz clic en un nodo para que sea el origen; cambia el clic a Destino y haz clic en otro nodo para buscar un camino más corto hasta él. El número de cada nodo es su distancia al origen, y la fila bajo el grafo es la cola. Nuevo grafo crea otro grafo; elige cuántos nodos y aristas tiene. Con el tablero seleccionado, las flechas avanzan o retroceden un paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.

Cómo funciona

  1. Haz clic en un nodo para que sea el origen. Para buscar un camino, cambia el clic a Destino y haz clic en otro nodo.
  2. Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto de la búsqueda.
  3. Observa la cola bajo el grafo y la distancia de cada nodo. Nuevo grafo crea otro grafo para probar.

Cómo funciona la búsqueda en anchura

Pon el nodo de origen en una cola con distancia 0. Después repite: toma el nodo del frente de la cola y mira cada uno de sus vecinos. Un vecino que aún no se ha visto recibe una distancia una unidad mayor que la del nodo tomado, recuerda ese nodo como aquel desde el que se llegó a él y pasa al final de la cola. Los vecinos ya vistos se saltan. Cuando la cola está vacía, cada nodo alcanzable tiene su distancia.

Por qué encuentra caminos más cortos

La cola entrega los nodos en el orden en que se encontraron, y los nodos se encuentran anillo a anillo: todos los nodos a distancia 1 entran en la cola antes que cualquiera a distancia 2, y así sucesivamente. Así, la primera vez que se alcanza un nodo, se llega por un camino con el menor número posible de aristas. Seguir los nodos recordados desde el destino hasta el origen da ese camino. Esto solo cuenta aristas; cuando las aristas tienen longitudes distintas, hace falta el algoritmo de Dijkstra.

Preguntas frecuentes

¿Qué es la búsqueda en anchura?

Una forma de explorar un grafo desde un nodo de origen visitando primero todos sus vecinos, luego los vecinos de estos, y así sucesivamente, anillo a anillo. Usa una cola para guardar los nodos en el orden en que se encontraron.

¿La búsqueda en anchura encuentra el camino más corto?

Sí, cuando todas las aristas cuentan igual: la primera vez que BFS alcanza un nodo, ha usado el menor número posible de aristas. Para aristas con longitudes distintas, usa el algoritmo de Dijkstra.

¿Qué diferencia hay entre BFS y DFS?

La búsqueda en anchura usa una cola y se extiende de forma uniforme, anillo a anillo. La búsqueda en profundidad usa una pila (o recursión) y sigue un camino hasta el fondo antes de retroceder. BFS encuentra caminos más cortos en aristas; DFS no, pero es útil para encontrar ciclos y para el ordenamiento topológico.

¿Es rápida la búsqueda en anchura?

Saca cada nodo de la cola una vez y mira cada arista desde sus dos extremos, así que el trabajo crece con el número de nodos más el número de aristas.

¿Se envía mi grafo a algún sitio?

No. El grafo se crea y se recorre en tu navegador, y tus últimos ajustes se guardan en el almacenamiento local de este navegador.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Ir al editor