codaBack to Academy
searching
Breadth-First Search
Breadth-First Search (BFS) is a graph traversal algorithm that explores all vertices at the present depth level before moving on to vertices at the next depth level. It uses a queue to process nodes in order of their distance from the source. BFS naturally finds the shortest path in unweighted graphs.
Use Cases
- •Finding the shortest path in unweighted graphs
- •Level-order traversal of trees
- •Social network analysis (finding degrees of separation)
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(V + E) | O(V + E) | O(V + E) |
| Space | O(V) | ||
Visualization
Implementation
Output
Click "Run Code" to see output...