Búsqueda en anchura en Javascript

La búsqueda en anchura es un algoritmo de búsqueda de grafos que explora todos los vértices de un grafos en el mismo nivel antes de pasar al siguiente nivel. Este algoritmo es muy útil para encontrar la ruta más corta en un grafo no ponderado donde el costo de cada arista es el mismo. En este artículo exploraremos cómo implementar la búsqueda en anchura en Javascript.

¿Qué es la búsqueda en anchura?

La búsqueda en anchura (BFS por sus siglas en inglés) es un método de recorrer y buscar datos en árboles o gráficos. En contraposición a la búsqueda en profundidad, en la que se avanza tan lejos como sea posible en la rama actual antes de retroceder, en la BFS se visita primero por niveles, es decir, de manera horizontal.

Este algoritmo se implementa utilizando una estructura de datos llamada cola. Los nodos se agregan a la cola en el orden en que se visitan, y se eliminan de la cola en el mismo orden. La BFS comienza visitando el nodo raíz y lo marca como visitado. Luego agrega todos los nodos adyacentes al nodo raíz a la cola. Saca el primer elemento de la cola, marca el nodo como visitado, agrega todos los vecinos al final de la cola y lleva a cabo el mismo proceso hasta que la cola esté vacía.

Implementando la búsqueda en anchura en Javascript

Para implementar la BFS en Javascript, podemos utilizar una matriz para representar el grafo y una cola para realizar el recorrido.

function BFS(graph, start) {
    const visited = [], queue = [];
    visited[start] = true;
    queue.push(start);

    while(queue.length > 0) {
        const u = queue.shift();
        for(let v of graph[u]) {
            if(!visited[v]) {
                visited[v] = true;
                queue.push(v);
            }
        }
    }

    return visited;
}

La función toma dos argumentos: el grafo representado como una matriz y el nodo de inicio. Creamos una matriz de visitados y una cola. El nodo de inicio se marca como visitado y se agrega a la cola.

En el cuerpo del bucle, sacamos el primer elemento de la cola, marcamos los vecinos no visitados y los agregamos a la cola. Continuamos sacando elementos de la cola hasta que esté vacía.

Ejemplo de uso

Veamos un ejemplo de cómo se utilizaría esta función:

// Definimos el grafo
const graph = [
    [1, 2], // vecinos del nodo 0
    [0, 3, 4], // vecinos del nodo 1
    [0, 5, 6], // vecinos del nodo 2
    [1], // vecinos del nodo 3
    [1], // vecinos del nodo 4
    [2], // vecinos del nodo 5
    [2, 7], // vecinos del nodo 6
    [6] // vecinos del nodo 7
];

// Ejecutamos la búsqueda en anchura desde el nodo 0
console.log(BFS(graph, 0));

En este ejemplo, el grafo se representa como una matriz donde cada fila representa los vecinos de un nodo. El resultado de la función es un arreglo que contiene valores booleanos que indican si el nodo correspondiente se visitó o no. En este ejemplo, la salida será:

[
    true, // nodo 0
    true, // nodo 1
    true, // nodo 2
    false, // nodo 3
    false, // nodo 4
    false, // nodo 5
    false, // nodo 6
    false // nodo 7
]

Conclusión

En este artículo hemos visto cómo implementar la búsqueda en anchura en Javascript utilizando una matriz para representar el grafo y una cola para realizar el recorrido. La BFS es un algoritmo útil para encontrar la ruta más corta en un grafo no ponderado. Con la implementación dada se puede comenzar a utilizar este algoritmo en proyectos que requieran esta funcionalidad.

Preguntas frecuentes

¿Cómo se implementa la BFS en un grafo ponderado?

En un grafo ponderado, la BFS necesita llevar un registro de los costos de alcanzar cada nodo. Para lograr esto se puede utilizar una estructura de datos como un mapa para registrar el costo de cada nodo.

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

BFS visita los nodos de un grafo por niveles, mientras que DFS avanza lo más posible en la rama actual antes de retroceder. DFS es más eficiente en grafos profundos, mientras que BFS lo es en grafos anchos.

¿La BFS siempre encuentra el camino más corto?

La BFS siempre encuentra el camino más corto en un grafo no ponderado en el que todas las aristas tienen el mismo costo.

¿Qué es una matriz de adyacencia?

Una matriz de adyacencia es una forma de representar un grafo mediante una matriz bidimensional. En la matriz, los valores de las celdas indican si hay una arista que conecta a los nodos representados por las filas y columnas correspondientes.

Cómo establecer el valor de un campo de entrada oculto a través de JavaScript?

Diferencia entre los métodos every() y some() en JavaScript

Cómo verificar si una variable no es nula en JavaScript

Cómo exportar una función en JavaScript

Cómo eliminar comas de una cadena en JavaScript

Cómo abrir una URL en una nueva pestaña usando JavaScript

Cómo mostrar “Sí” o “No” con la función confirm() en JavaScript

Cómo comparar cadenas en JavaScript

Operador de comparación de no igualdad en JavaScript | Explicado