Back to algorithmsSredni
Breadth-First Search (BFS)
A graph traversal algorithm that visits all neighbors at the current depth before moving to nodes at the next depth level.
O(V + E)O(V)OIJOI
Applications
- •Shortest path in unweighted graphs
- •Checking graph connectivity
- •Finding all vertices within a given distance
- •Solving mazes
Complexity
Time
O(V + E)
Memory
O(V)
V = number of vertices
E = number of edges
How does Breadth-First Search (BFS) work?
A graph traversal algorithm that visits all neighbors at the current depth before moving to nodes at the next depth level.
Analogy
Imagine throwing a stone into water. The waves spread in circles - first the closest points, then farther ones. BFS works the same way - it visits all neighbors first, then neighbors of neighbors.