Breadth-First Search (BFS)

BFS is a graph traversal algorithm that explores all neighbors at the current depth before moving to nodes at the next depth level.

Key Concepts

• Uses a queue data structure (FIFO)
• Explores nodes level by level
• Finds the shortest path in unweighted graphs

Interactive Visualization

1function bfs(graph, start) {
2  const visited = new Set();
3  const queue = [start];
4  visited.add(start);
5 
6  while (queue.length > 0) {
7    const current = queue.shift();
8    console.log(current); // Process node
9 
10    for (const neighbor of graph[current]) {
11      if (!visited.has(neighbor)) {
12        visited.add(neighbor);
13        queue.push(neighbor);
14      }
15    }
16  }
17}

Algorithm Steps

1. Start at the source node, add it to the queue
2. Mark the source as visited
3. While queue is not empty:
   • Dequeue a node
   • Process it (print, store, etc.)
   • Add all unvisited neighbors to the queue
   • Mark neighbors as visited

Complexity

Where V = vertices, E = edges

Use Cases

• Shortest path in unweighted graphs
• Level-order traversal of trees
• Finding connected components
• Social network friend suggestions (people within N connections)
• Web crawlers (exploring links level by level)