Fundamentos del Algoritmo de Búsqueda en Amplitud

El algoritmo de Búsqueda en Amplitud (BFS, por sus siglas en inglés) es una técnica fundamental para recorrer o buscar en estructuras de datos como grafos y árboles. A diferencia de la Búsqueda en Profundidad (DFS), que utiliza una pila para explorar en profundidad, BFS emplea una cola (FIFO) para explorar los nodos nivel por nivel. Este enfoque garantiza que todos los nodos a una distancia k del nodo de origen se visiten entes que los nodos a una distancia k+1. Al ser un método de búsqueda no informada, explora exhaustivamente el espacio de estados hasta encontrar el objetivo, sin utilizar heurísticas para dirigir la búsqueda.

Basándonos en este comportamiento de exploración por capas, podemos definir la siguiente plantilla estructural:

void executeBFS(int startNode, int totalNodes) {
    std::queue<int> explorationQueue;
    explorationQueue.push(startNode);
    
    while (!explorationQueue.empty()) {
        int currentNode = explorationQueue.front();
        explorationQueue.pop();
        
        for (int adjacentNode = 0; adjacentNode < totalNodes; ++adjacentNode) {
            if (isValidTransition(currentNode, adjacentNode)) {
                explorationQueue.push(adjacentNode);
            }
        }
    }
}

Recorrido por Niveles en Estructuras Arbóreas

El recorrido por niveles es la aplicación directa de BFS en estructuras arbóreas. Consiste en visitar los nodos jerárquicamente, comenzando por la raíz y avanzando hacia los niveles inferiores, procesando los nodos de cada nivel de izquierda a derecha. A continuación, se muestra una implementación utilizando la biblioteca estándar de C++:

std::vector<int> levelOrderTraversal(TreeNode* rootNode) {
    std::vector<int> traversalResult;
    if (!rootNode) return traversalResult;
    
    std::queue<TreeNode*> nodeQueue;
    nodeQueue.push(rootNode);
    
    while (!nodeQueue.empty()) {
        TreeNode* activeNode = nodeQueue.front();
        nodeQueue.pop();
        traversalResult.push_back(activeNode->value);
        
        if (activeNode->leftChild) nodeQueue.push(activeNode->leftChild);
        if (activeNode->rightChild) nodeQueue.push(activeNode->rightChild);
    }
    return traversalResult;
}

Aplicación en Problemas de Caminos Más Cortos

En grafos no ponderados, BFS es la herramienta óptima para encontrar el camino más corto. Dado que la exploración se realiza capa por cappa, la primera vez que el algoritmo alcanza un nodo destino, se garantiza matemáticamente que la distancia recorrida es la mínima posible.

Profundidad Mínima de un Árbol Binario

Calcular la profundidad mínima de un árbol binario equivale a encontarr la distancia más corta desde la raíz hasta cualquier nodo hoja. Aplicando BFS, el primer nodo hoja que encontremos determinará la profundidad mínima del árbol, ya que los niveles se procesan en orden ascendente.

int calculateMinDepth(TreeNode* rootNode) {
    if (!rootNode) return 0;
    
    std::queue<TreeNode*> depthQueue;
    depthQueue.push(rootNode);
    int currentDepth = 0;
    
    while (!depthQueue.empty()) {
        int levelSize = depthQueue.size();
        currentDepth++;
        
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* activeNode = depthQueue.front();
            depthQueue.pop();
            
            if (!activeNode->leftChild && !activeNode->rightChild) {
                return currentDepth;
            }
            
            if (activeNode->leftChild) depthQueue.push(activeNode->leftChild);
            if (activeNode->rightChild) depthQueue.push(activeNode->rightChild);
        }
    }
    return currentDepth;
}

Navegación Óptima en un Laberinto

Para resolver un laberinto representado como una matriz donde ciertos valores indican obstáculos, podemos modelar el problema como un grafo no ponderado. BFS explorará todas las rutas posibles simultáneamente, asegurando que la primera vez que lleguemos a la salida, el número de pasos sea el menor. En esta implementación, se utiliza un índice basado en cero y se valida los límites de la matriz dinámicamente.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Coordinate {
    int row;
    int col;
};

int findShortestPath(vector<vector<int>>& maze, int rows, int cols) {
    vector<vector<int>> distances(rows, vector<int>(cols, -1));
    queue<Coordinate> pathQueue;
    
    pathQueue.push({0, 0});
    distances[0][0] = 0;
    
    int rowDirections[] = {-1, 1, 0, 0};
    int colDirections[] = {0, 0, -1, 1};
    
    while (!pathQueue.empty()) {
        Coordinate current = pathQueue.front();
        pathQueue.pop();
        
        if (current.row == rows - 1 && current.col == cols - 1) {
            return distances[current.row][current.col];
        }
        
        for (int dir = 0; dir < 4; ++dir) {
            int nextRow = current.row + rowDirections[dir];
            int nextCol = current.col + colDirections[dir];
            
            if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && 
                maze[nextRow][nextCol] == 0 && distances[nextRow][nextCol] == -1) {
                distances[nextRow][nextCol] = distances[current.row][current.col] + 1;
                pathQueue.push({nextRow, nextCol});
            }
        }
    }
    return -1;
}

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }
    
    cout << findShortestPath(grid, n, m) << endl;
    return 0;
}