¿Qué es Breadth First Search (BFS)?

Breadth First Search (BFS) es un algoritmo utilizado para recorrer o buscar elementos en un grafo o árbol. Explora todos los nodos vecinos en el mismo nivel antes de pasar al siguiente nivel, utilizando una estructura de cola para mantener el orden de los nodos por explorar.

El Código

                
class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  addEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1].push(vertex2);
    this.adjacencyList[vertex2].push(vertex1);
  }

  breadthFirstSearch(start) {
    const queue = [start];
    const result = [];
    const visited = {};
    let currentVertex;

    visited[start] = true;

    while (queue.length) {
      currentVertex = queue.shift();
      result.push(currentVertex);

      this.adjacencyList[currentVertex].forEach((neighbor) => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      });
    }

    return result;
  }
}

// Ejemplo de uso
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "E");
graph.addEdge("D", "E");
graph.addEdge("D", "F");
graph.addEdge("E", "F");

console.log("BFS desde el vértice A:", graph.breadthFirstSearch("A"));
                
            

Puntos Clave del Algoritmo

• Entrada: Un grafo representado como una lista de adyacencia y un nodo inicial.
• Salida: Un arreglo con los nodos visitados en el orden BFS.
• Método:
  • Utiliza una cola para llevar el seguimiento de los nodos por visitar.
  • Visita el nodo actual y agrega todos sus vecinos no visitados a la cola.
  • Repite el proceso hasta que la cola esté vacía.
• Complejidad:
  • Tiempo: O(V + E), donde V es el número de vértices y E es el número de aristas.
  • Espacio: O(V) debido al almacenamiento en la cola y el seguimiento de nodos visitados.
• Ventajas: Es ideal para encontrar el camino más corto en grafos no ponderados y para explorar todos los nodos conectados a un componente.
• Desventajas: Puede ser menos eficiente en memoria para grafos grandes y densos en comparación con Depth First Search (DFS).

Ejemplo de Ejecución

Grafo inicial:

• Vértices: A, B, C, D, E, F
• Aristas: A-B, A-C, B-D, C-E, D-E, D-F, E-F

Proceso de BFS desde el vértice A:

1. Inicia en A, agrega sus vecinos B y C a la cola.
2. Visita B, agrega su vecino no visitado D.
3. Visita C, agrega su vecino no visitado E.
4. Visita D, agrega su vecino no visitado F.
5. Visita E, sin vecinos no visitados.
6. Visita F, sin vecinos no visitados.

Resultado final: [A, B, C, D, E, F]

Información Adicional

BFS es ampliamente utilizado en problemas de grafos como el cálculo de caminos más cortos en grafos no ponderados, detección de ciclos y búsqueda de componentes conectados. Es especialmente útil cuando el objetivo es explorar nodos cercanos al nodo inicial antes de proceder a niveles más profundos.