Breadth-First Search
Explores a graph level by level using a queue — all distance-1 nodes before any distance-2 node. Finds shortest paths in unweighted graphs; powers web crawlers and social-degree queries.
- Category
- Graphs
- Time complexity
- O(V + E)
- Space complexity
- O(V)
Pseudocode
queue ← [start] visit front, enqueue new neighbours repeat until queue empty order = discovery order
Reference implementation
queue = [start]
while queue:
n = queue.pop(0)
for m in adj[n]:
if m not in seen:
queue.append(m)