Breadth-First Search

⏱ Time: O(V + E)💾 Space: O(V)

Explore a graph or tree level by level using a queue. Guarantees finding the shortest path on unweighted graphs.

🎯 When to Use

  • ✓Shortest path in unweighted graphs
  • ✓Level-order traversal
  • ✓Finding nearest neighbors

📝 Pseudocode

Breadth-First Search TemplateO(V + E)
1function bfs(startNode):
2  queue = [startNode]
3  visited = new Set([startNode])
4  
5  while queue.length > 0:
6    node = queue.shift()
7    for neighbor in node.neighbors:
8      if neighbor not in visited:
9        visited.add(neighbor)
10        queue.push(neighbor)

🏢 Real-World Use Cases

LinkedIn
Connection Degrees

Finding 1st, 2nd, and 3rd degree professional connections using level-order graph search.

💡 Practice Problems (1)

1.Clone GraphMedium
→
← Back to Patterns