Graph AlgosGraph Algorithms

Breadth-First Search

Explore a graph layer by layer from a source using a FIFO queue, visiting every node at distance d before any node at distance d + 1.

Learn Breadth-First Search (BFS) →
A0BCDEFGHIJKL
Queue (front → back)
A
1/42Start BFS from A. Put it in the queue and mark it visited with distance 0.
Current nodeIn queueVisitedBFS tree edge
PseudocodeLearn Breadth-First Search (BFS) →
1queue = [source]; visited = {source}
2while queue not empty:
3  u = queue.popleft()
4  for v in neighbors(u):
5    if v not in visited:
6      visited.add(v); parent[v] = u
7      queue.append(v)
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed