Breadth-First Search
A graph traversal algorithm that explores vertices in order of distance from a source using a queue, finding shortest paths in unweighted graphs.
Breadth-first search (BFS) traverses a graph by visiting all vertices at distance 1 from the source, then all at distance 2, and so on, using a first-in-first-out queue. Because it processes vertices in strictly increasing distance order, the first time BFS discovers a vertex the path used to reach it is a shortest path — provided the graph is unweighted, meaning every edge has equal cost. This makes BFS the unweighted special case of Dijkstra's algorithm, which generalizes the same frontier idea to weighted edges.
The algorithm starts by enqueueing the source. Each step dequeues a vertex, marks it visited, and enqueues every unvisited neighbor. A visited set — typically a hash table or a boolean array — prevents vertices from being processed twice, so each vertex and each edge is touched at most once, giving O(V+E) running time on an adjacency-list representation.
function bfs(graph, source):
visited = set(source)
queue = [source]
while queue is not empty:
u = queue.pop_front()
for each neighbor v of u:
if v not in visited:
visited.add(v)
queue.push_back(v)
BFS appears wherever the distance from a start point matters: shortest paths in road and maze problems, web crawlers that fetch pages level by level, social-network analysis (degrees of separation), and broadcast or gossip protocols in networks. In Big O terms it is linear in the size of the graph, which is optimal for unweighted reachability and shortest-path problems. Its close relative, depth-first search, uses a stack instead of a queue and is preferred for connectivity, cycle detection, and topological ordering.
Tags
algorithms graph theory queues searching
Related articles
- Bellman–Ford Algorithm
- Dijkstra's Shortest Path Algorithm
- Binary Search
- Merge Sort
- Dynamic Programming
- Hash Tables
Click here for easy-to-read helpful e-books for anyone, anywhere, and about anything