Búsqueda en anchura (BFS)
Explora un grafo capa por capa. Una cola decide qué vértice va después, así que los vértices más cercanos siempre se visitan primero.
- tiempo O(V + E)
- espacio O(V)
- usa una cola
¿Qué significan estos términos?
- Vértice: un punto del grafo, dibujado aquí como un círculo con una letra.
- Arista: una línea que une dos vértices. Aquí se puede recorrer en los dos sentidos.
- Vecinos: los vértices unidos a un vértice por una arista. Se revisan en orden alfabético.
- Cola: el primero en entrar es el primero en salir. BFS siempre toma el vértice que lleva más tiempo esperando.
- Pila: el último en entrar es el primero en salir. DFS siempre sigue desde el último vértice al que llegó.
- V y E: el número de vértices y de aristas. O(V + E) significa que cada vértice y cada arista se procesan un número fijo de veces.
- en la cola
- actual
- listo
- arista del árbol de búsqueda
- arista omitida
Empieza en A. Pulsa reproducir o avanza paso a paso.
Espacio: reproducir o pausar. Flechas izquierda y derecha: paso a paso. Inicio y Fin: saltar.
Prueba esto: Elige el grafo de dos partes. Los vértices que no están conectados con el inicio nunca se alcanzan.
Cómo funciona
BFS pone el vértice de inicio en una cola. Luego, una y otra vez, toma el vértice del frente de la cola y añade sus vecinos nuevos al final. Una cola atiende por orden de llegada, así que todos los vértices a una arista quedan listos antes que cualquiera a dos aristas. El número junto a un vértice es su distancia al inicio: las menos aristas necesarias para llegar a él.
Cuándo es una buena opción
Usa BFS cuando necesites el camino más corto en pasos: los menos movimientos en un rompecabezas, los menos saltos en una red, las personas a dos contactos de ti. En un grafo grande la cola puede crecer mucho, porque guarda una capa entera a la vez.