En el desarrollo de algoritmos de búsqueda en grafos o matrices, la implementación de la Búsqueda en Anchura (BFS) parece directa. Sin embargo, existe un detalle sutil en la gestión de los estados de visita que puede degradar el rendimiento de una solución eficiente a una que exceda el tiempo límite de ejecución (TLE).

Este problema se manifiesta claramente en desafíos clásicos como "Contar el número de islas". A continuación, analizaremos por qué el momento exacto en el que marcamos un nodo como "visitado" determina la eficiencia del algoritmo.

El error común: Marcado al extraer de la cola

Muchos desarrolladores cometen el error de marcar un nodo como procesado únicamente cuando este es extraído de la cola (operación pop). Aunque lógicamente parece correcto, esto genera redundancia masiva en la cola de procesamiento.

// Ejemplo de implementación ineficiente (causa TLE)
class IslandCounter {
public:
    int countIslands(vector<vector>>& mapa) {
        int filas = mapa.size();
        int columnas = mapa[0].size();
        int totalIslas = 0;

        for (int i = 0; i < filas; ++i) {
            for (int j = 0; j < columnas; ++j) {
                if (mapa[i][j] == '1') {
                    totalIslas++;
                    queue<pair int="">> q;
                    q.push({i, j});

                    while (!q.empty()) {
                        pair<int int=""> actual = q.front();
                        q.pop();
                        
                        // ERROR: Marcar como visitado al extraer
                        mapa[actual.first][actual.second] = '0';

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

                        for (int k = 0; k < 4; ++k) {
                            int nx = actual.first + dx[k];
                            int ny = actual.second + dy[k];

                            if (nx >= 0 && nx < filas && ny >= 0 && ny < columnas && mapa[nx][ny] == '1') {
                                q.push({nx, ny});
                            }
                        }
                    }
                }
            }
        }
        return totalIslas;
    }
};
</int></pair></vector>

El enfoque óptimo: Marcado al insertar en la cola

La forma correcta de evitar que un mismo nodo sea añadido múltiples veces a la cola es marcarlo como visitado en el mismo instante en que se decide añadirlo (operación push). Esto garantiza que ningún otro nodo adyacente vuelva a considerar a ese vecino como "no visitado" mientras este espera en la cola.

// Ejemplo de implementación optimizada
class IslandCounterRefactored {
public:
    int countIslands(vector<vector>>& terreno) {
        if (terreno.empty()) return 0;
        int m = terreno.size(), n = terreno[0].size();
        int islas = 0;

        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                if (terreno[r][c] == '1') {
                    islas++;
                    // Marcamos inmediatamente el inicio de la isla
                    terreno[r][c] = '0'; 
                    queue<pair int="">> cola;
                    cola.push({r, c});

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

                        int offsets[] = {0, 1, 0, -1, 0}; 
                        for (int i = 0; i < 4; ++i) {
                            int nx = currX + offsets[i];
                            int ny = currY + offsets[i+1];

                            if (nx >= 0 && nx < m && ny >= 0 && ny < n && terreno[nx][ny] == '1') {
                                // CORRECCIÓN: Marcamos como visitado ANTES de insertar
                                terreno[nx][ny] = '0';
                                cola.push({nx, ny});
                            }
                        }
                    }
                }
            }
        }
        return islas;
    }
};
</pair></vector>

Análisis de la diferencia de rendimiento

¿Por qué el primer método falla en grafos densos o matrices grandes? La explicación reside en la redundancia exponencial:

• Supongamos que el nodo A tiene como vecinos a B y C, y tanto B como C tienen como vecino a D.
• Si usamos el primer método:
  1. Procesamos A, insertamos B y C en la cola.
  2. Extraemos B, lo marcamos como visitado e insertamso a su vecino D.
  3. Extraemos C. Como D aún está en la cola pero no ha sido extraído ni marcado, C vuelve a insertar a D en la cola.
• En una cuadrícula grande, un solo nodo puede ser insertado en la cola miles de veces innecesariamente antes de ser procesado por primera vez.

Al marcar el nodo como visitado en el momento del push, bloqueamos cualquier intento posterior de insertar el mismo nodo, menteniendo el tamaño de la cola bajo control y asegurando una complejidad de tiempo lineal O(V + E) o O(M * N) en el caso de matrices.