Búsqueda en Amplitud (BFS)

La analogía: una onda expansiva

Imagina que dejas caer una piedra en un estanque. Las ondas se expanden en círculos concéntricos, tocando primero lo más cercano y después lo más lejano. BFS (Breadth-First Search) funciona exactamente así: explora todos los vecinos de un nodo antes de pasar al siguiente nivel.

Otra forma de verlo: estás buscando a alguien en un edificio. Primero revisas todas las habitaciones del piso actual, y solo después subes al siguiente piso.

¿Cuándo usar BFS?

• Encontrar el camino más corto en un grafo sin pesos (o donde todas las aristas pesan lo mismo).
• Explorar todos los nodos nivel por nivel.
• Encontrar la distancia mínima desde un punto de partida.
• Recorrer una cuadrícula paso a paso.

Implementación básica

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> adj[100005]; // Lista de adyacencia
bool visitado[100005];
int distancia[100005];

void bfs(int inicio) {
    queue<int> cola;
    cola.push(inicio);
    visitado[inicio] = true;
    distancia[inicio] = 0;

    while (!cola.empty()) {
        int actual = cola.front();
        cola.pop();

        for (int vecino : adj[actual]) {
            if (!visitado[vecino]) {
                visitado[vecino] = true;
                distancia[vecino] = distancia[actual] + 1;
                cola.push(vecino);
            }
        }
    }
}

Línea por línea:

1. queue<int> cola — Usamos una cola (FIFO) porque queremos procesar nodos en el orden en que los descubrimos.
2. cola.push(inicio) — Metemos el nodo inicial a la cola.
3. visitado[inicio] = true — Lo marcamos para no visitarlo otra vez.
4. while (!cola.empty()) — Mientras haya nodos por explorar…
5. int actual = cola.front(); cola.pop() — Sacamos el primero de la cola (el más antiguo).
6. for (int vecino : adj[actual]) — Revisamos todos sus vecinos.
7. if (!visitado[vecino]) — Si no hemos visitado al vecino…
8. distancia[vecino] = distancia[actual] + 1 — Su distancia es un paso más.
9. cola.push(vecino) — Lo metemos a la cola para explorarlo después.

Ejemplo visual

Grafo: 0 -- 1 -- 3 -- 4, 0 -- 2 -- 4

BFS desde 0:

Resultado: el camino más corto de 0 a 4 tiene longitud 2 (por 0→2→4).

BFS en cuadrícula

Uno de los usos más comunes en competencias: encontrar el camino más corto en un laberinto.

#include <iostream>
#include <queue>
using namespace std;

int n, m;
char grid[1005][1005];
int dist[1005][1005];
bool vis[1005][1005];

// 4 direcciones: arriba, abajo, izquierda, derecha
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool valida(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m
           && grid[x][y] != '#' && !vis[x][y];
}

int bfsGrid(int sx, int sy, int ex, int ey) {
    queue<pair<int,int>> cola;
    cola.push({sx, sy});
    vis[sx][sy] = true;
    dist[sx][sy] = 0;

    while (!cola.empty()) {
        auto [x, y] = cola.front();
        cola.pop();

        if (x == ex && y == ey) return dist[x][y];

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (valida(nx, ny)) {
                vis[nx][ny] = true;
                dist[nx][ny] = dist[x][y] + 1;
                cola.push({nx, ny});
            }
        }
    }

    return -1;  // No hay camino
}

int main() {
    cin >> n >> m;

    int sx, sy, ex, ey;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 'S') { sx = i; sy = j; }
            if (grid[i][j] == 'E') { ex = i; ey = j; }
        }
    }

    cout << bfsGrid(sx, sy, ex, ey) << endl;

    return 0;
}

Input de ejemplo:

5 5
S . . . .
. # # # .
. # . . .
. # . # .
. . . # E

BFS desde múltiples fuentes

A veces necesitas calcular la distancia desde varios puntos de partida simultáneamente. Solo agrega todos los orígenes a la cola al inicio.

void bfsMultiple(vector<int> &fuentes) {
    queue<int> cola;
    for (int f : fuentes) {
        cola.push(f);
        visitado[f] = true;
        distancia[f] = 0;
    }

    while (!cola.empty()) {
        int actual = cola.front();
        cola.pop();
        for (int vecino : adj[actual]) {
            if (!visitado[vecino]) {
                visitado[vecino] = true;
                distancia[vecino] = distancia[actual] + 1;
                cola.push(vecino);
            }
        }
    }
}

Ejemplo: tienes un tablero con varios incendios. ¿Cuánto tarda cada celda en quemarse?

Complejidad

• Tiempo: $O(V + E)$ donde $V$ = vértices y $E$ = aristas
• Espacio: $O(V)$ para la cola y los arreglos auxiliares
• En cuadrícula: $O(n \times m)$

Reconstruir el camino

BFS encuentra la distancia más corta, pero ¿cómo saber cuál es el camino? Guarda el padre de cada nodo:

int padre[100005];

void bfs(int inicio) {
    queue<int> cola;
    cola.push(inicio);
    visitado[inicio] = true;
    padre[inicio] = -1;

    while (!cola.empty()) {
        int actual = cola.front();
        cola.pop();
        for (int vecino : adj[actual]) {
            if (!visitado[vecino]) {
                visitado[vecino] = true;
                padre[vecino] = actual;
                cola.push(vecino);
            }
        }
    }
}

void imprimirCamino(int destino) {
    vector<int> camino;
    for (int v = destino; v != -1; v = padre[v]) {
        camino.push_back(v);
    }
    reverse(camino.begin(), camino.end());
    for (int v : camino) cout << v << " ";
    cout << endl;
}

Ejercicio de práctica

Dada una cuadrícula de N×M, encuentra la menor cantidad de pasos para ir de S a E. Los # son paredes y los . son caminos libres.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int n, m;
char grid[1005][1005];
int dist[1005][1005];

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int main() {
    cin >> n >> m;
    int sx, sy, ex, ey;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 'S') { sx = i; sy = j; }
            if (grid[i][j] == 'E') { ex = i; ey = j; }
        }

    memset(dist, -1, sizeof(dist));
    queue<pair<int,int>> q;
    q.push({sx, sy});
    dist[sx][sy] = 0;

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m
                && grid[nx][ny] != '#' && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }

    cout << dist[ex][ey] << endl;
    return 0;
}

Siguiente paso

Aprende Búsqueda en Profundidad (DFS), la contraparte de BFS que explora lo más lejos posible antes de retroceder.