prep4place
Back to Visualizer

Breadth-First Search (BFS)

BFS explores a graph level by level, visiting all neighbors of the current node before moving to the next level. Uses a queue data structure.

O(V + E)Uses Queue
Speed:
Start
Current
In Queue
Visited

Visit Order

Start the visualization to see the visit order

How BFS Works

  1. 1Start from the source node, add it to a queue
  2. 2Mark the source node as visited
  3. 3While queue is not empty, dequeue a node
  4. 4Process the current node (visit it)
  5. 5For each unvisited neighbor, mark visited and enqueue
  6. 6Repeat until queue is empty
  7. 7BFS explores level by level (breadth-first)

Key Properties

  • • Finds shortest path in unweighted graphs
  • • Explores all nodes at current depth first
  • • Uses Queue (FIFO) data structure
  • • Complete: Will find solution if one exists

Complexity

TimeO(V + E)
SpaceO(V)

V = vertices, E = edges

Code

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  const result = [];
  
  visited.add(start);
  
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);
    
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  
  return result;
}