Loading...
Breadth-First Search visits a start node, then all its neighbours, then their neighbours, expanding outward in rings using a FIFO queue. It finds the shortest path in terms of edge count on unweighted graphs, and underpins things like shortest-hop routing, web crawlers, and social-network "degrees of separation". Runs in O(V + E).
Explores a graph level by level using a queue.
Start at A: mark it discovered and enqueue it.
| Average case | O(V + E) |
| Worst case | O(V + E) |
| Space | O(V) |
Complexities are for the reference implementation shown; constant factors and cache behavior vary by language.
Idiomatic, copy-paste implementations. Pick your language:
Python
from collections import deque
def bfs(adj, start):
visited = [False] * len(adj)
order, q = [], deque([start])
visited[start] = True
while q:
u = q.popleft()
order.append(u)
for v in adj[u]: # neighbours of u
if not visited[v]:
visited[v] = True
q.append(v)
return orderRunning Breadth-First Search (BFS) on the sample graph, step by step:
The control flow of the algorithm as a diagram: