Breadth First Search (BFS)
Interactive Visualization
Try out BFS on this interactive graph:
Breadth First Search (BFS)
info
BFS is a graph traversal algorithm that explores all vertices at the present depth before moving on to vertices at the next depth level.
How BFS Works
Breadth First Search works like exploring a maze level by level:
- Start at a chosen vertex
- Visit all its neighbors
- Then visit all neighbors of those neighbors
- Continue this pattern until all reachable vertices are visited
Key Characteristics
- Uses a queue data structure
- Time Complexity: O(V + E) where V is vertices and E is edges
- Space Complexity: O(V)
- Guarantees shortest path in unweighted graphs
- Explores nodes level by level
Common Applications
- Finding shortest path in unweighted graphs
- Social networking (finding people within N connections)
- Web crawlers
- GPS Navigation systems
- Broadcasting in network