Visualizador BFS Online

Pseudocódigo

Todo el algoritmo se reduce a una cola y un conjunto de visitados. Cualquier otra propiedad por la que se conoce a BFS se deriva del orden en que la cola devuelve los nodos.

BFS(grafo, origen):
    visitados = {origen}
    dist[origen] = 0
    cola = [origen]

    mientras la cola no esté vacía:
        u = cola.quitarPrimero()
        para cada vecino v de u:
            si v no está en visitados:
                visitados.añadir(v)
                dist[v] = dist[u] + 1
                padre[v] = u
                cola.añadirAlFinal(v)

El invariante es que la cola siempre contiene nodos de como mucho dos niveles de distancia consecutivos, en orden no decreciente. Esa única propiedad es la que garantiza que dist sea correcta: a un nodo se le asigna su distancia la primera vez que se ve, y ya no puede alcanzarse de forma más barata después.

Ejemplo resuelto, paso a paso

Ejecuta BFS desde A sobre el grafo que carga el visualizador por defecto, para poder seguir cada paso en el panel superior.

Grafo de ejemplo: Aristas no dirigidas A-B (2), A-C (3), B-C (1) y C-D (4). BFS ignora por completo los pesos y cuenta saltos, así que cada arista vale uno.

1. Inicio. Marca A como visitado con dist 0 y ponlo en la cola. Cola: [A].
2. Extraer A. A tiene como vecinos B y C, ninguno visitado. Ambos reciben dist 1 y padre A. Cola: [B, C].
3. Extraer B. B tiene como vecinos A y C. Los dos están ya visitados: A como origen y C reclamado hace un momento por A. No se añade nada. Este paso muestra por qué BFS nunca revisita: llegar a C pasando por B costaría 2 saltos frente al 1 ya registrado. Cola: [C].
4. Extraer C. C tiene como vecinos A, B y D. Solo D es nuevo, así que recibe dist 2 y padre C. Cola: [D].
5. Extraer D. El único vecino de D es C, ya visitado. La cola se vacía y la búsqueda termina.

Las distancias finales son A 0, B 1, C 1, D 2, y los punteros al padre dan el árbol de caminos mínimos A a B, A a C y C a D. Fíjate en que BFS llega a D pasando por C aunque el coste con pesos por esa ruta sea 7 frente al 3 de A a B a C: lo único que optimiza es el número de saltos, que es exactamente la razón por la que los grafos con pesos necesitan Dijkstra.

Complejidad y de dónde sale

Tiempo: O(V + E) · Espacio: O(V)

Cada vértice entra en la cola como mucho una vez, porque se marca como visitado en el momento de encolarlo y no al desencolarlo. Eso acota el bucle exterior en V iteraciones. Dentro del bucle, el trabajo es proporcional al grado del vértice actual, y la suma de todos los grados es 2E en un grafo no dirigido, así que recorrer los vecinos suma O(E). El espacio lo dominan el conjunto de visitados, el vector de distancias y la cola, cada uno O(V). Con una matriz de adyacencia el recorrido de vecinos pasa a costar O(V) por vértice y la ejecución completa degrada a O(V al cuadrado).

Cuándo usar Búsqueda en Anchura y cuándo no

BFS es la opción por defecto siempre que las aristas no tengan peso. En cuanto aparecen pesos, o el objetivo pasa de distancia a estructura, conviene otra cosa.

Errores frecuentes

• Marcar como visitado al desencolar en lugar de al encolar. Si un nodo solo se marca cuando sale de la cola, puede encolarse muchas veces antes de su primera extracción. En grafos densos esto convierte un recorrido lineal en uno cuadrático y puede agotar la memoria. Márcalo como visitado en el momento de insertarlo.
• Usar BFS en un grafo con pesos. BFS cuenta saltos, no peso. En un grafo donde A a C cuesta 100 en una sola arista y A a B a C cuesta 2 en dos aristas, BFS informa de que la ruta de coste 100 es más corta. Usa Dijkstra en su lugar.
• Reconstruir el camino solo con las distancias. Las distancias dicen cuán lejos, no por dónde. Guarda un puntero al padre cuando asignes una distancia, luego recorre los padres hacia atrás desde el destino e invierte el resultado.
• Usar recursión en lugar de una cola. Un recorrido recursivo es en profundidad, se llame como se llame. BFS necesita una cola FIFO explícita; no existe una formulación recursiva natural.

Preguntas frecuentes

¿Para qué sirve la búsqueda en anchura?

BFS encuentra el camino más corto en grafos sin pesos, comprueba conectividad y bipartición, y recorre árboles por niveles. También es la búsqueda de caminos aumentantes dentro de Edmonds-Karp para flujo máximo, y sostiene las consultas de distancia mínima en redes sociales y de enrutamiento.

¿Cuál es la complejidad temporal de BFS?

O(V + E) en tiempo y O(V) en espacio con lista de adyacencia, donde V es el número de vértices y E el de aristas. Con matriz de adyacencia pasa a O(V al cuadrado), porque cada recorrido de vecinos cuesta O(V) independientemente del grado real.

¿BFS encuentra siempre el camino más corto?

Sí en grafos sin pesos, y no en grafos con pesos. BFS expande los nodos en orden no decreciente de número de saltos, así que la primera vez que alcanza un nodo ha usado el mínimo de aristas posible. En cuanto las aristas tienen pesos distintos esa garantía se rompe, porque el menor número de aristas y el menor peso total dejan de coincidir.

¿Cuál es la diferencia entre BFS y DFS?

BFS explora por niveles usando una cola y encuentra caminos mínimos en grafos sin pesos. DFS sigue una rama hasta el final usando una pila o recursión y revela estructura como ciclos, orden topológico y componentes fuertemente conexas. BFS consume más memoria en grafos anchos y DFS más en grafos profundos.

¿Puede BFS detectar un ciclo?

Sí. En un grafo no dirigido, si BFS alcanza un nodo ya visitado que no es el padre del nodo actual, esa arista cierra un ciclo. En un grafo dirigido BFS encaja mal y lo habitual es el orden topológico de Kahn o un DFS con clasificación de aristas.