Breadth-First Search
A graph traversal algorithm that explores vertices in layers.
Time Complexity
O(V + E)
?Space Complexity
O(V)
?In-Place
No
NoStability
Yes
YesDifficulty
Medium
★★★☆☆Description
Breadth-First Search (BFS) is a graph traversal algorithm that explores all neighbors of a vertex before moving to the next level.
It uses a queue to keep track of the next vertex to visit, making it ideal for finding the shortest path in unweighted graphs.
Steps:
- Start from a source vertex
- Visit all its neighbors
- Then visit the neighbors’ neighbors, and so on
BFS guarantees the shortest path in terms of the number of edges in unweighted graphs.