Practice Now
breadth-first search
BFS applications
graph algorithms
search strategies
computer science

What is breadth-first search useful for?

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
AlgorithmsData Structures

Introduction

Breadth first search, often called BFS, explores a graph level by level from a starting node. It is one of the most practical graph traversal techniques because it guarantees the shortest path in unweighted graphs. If you deal with routing, dependency levels, or nearest match queries, BFS is often the first algorithm to try.

Why BFS Is Useful

BFS processes all neighbors at distance one before distance two, then distance three, and so on. This ordering is valuable when distance in number of edges is your cost model. In plain terms, BFS answers questions like "what is the fewest steps needed" without extra weighting logic.

Common real uses include:

  • Shortest path in unweighted maps or networks.
  • Finding connected components.
  • Level order traversal of trees.
  • Discovering all nodes reachable within k hops.

Because BFS uses a queue, it is easy to reason about and debug.

python
1from collections import deque
2
3
4def bfs_order(graph: dict[str, list[str]], start: str) -> list[str]:
5    visited = set([start])
6    queue = deque([start])
7    order = []
8
9    while queue:
10        node = queue.popleft()
11        order.append(node)
12        for neighbor in graph.get(node, []):
13            if neighbor not in visited:
14                visited.add(neighbor)
15                queue.append(neighbor)
16
17    return order
18
19
20graph_data = {
21    "A": ["B", "C"],
22    "B": ["D", "E"],
23    "C": ["F"],
24    "D": [],
25    "E": ["F"],
26    "F": [],
27}
28
29print(bfs_order(graph_data, "A"))

BFS for Shortest Path in Unweighted Graphs

A major reason BFS is popular is shortest path recovery. By recording each node parent when first discovered, you can reconstruct the minimum edge path from source to target.

python
1from collections import deque
2
3
4def shortest_path_unweighted(graph: dict[str, list[str]], start: str, target: str) -> list[str]:
5    if start == target:
6        return [start]
7
8    queue = deque([start])
9    visited = {start}
10    parent: dict[str, str | None] = {start: None}
11
12    while queue:
13        node = queue.popleft()
14        for neighbor in graph.get(node, []):
15            if neighbor in visited:
16                continue
17
18            visited.add(neighbor)
19            parent[neighbor] = node
20
21            if neighbor == target:
22                path = [target]
23                cur = target
24                while parent[cur] is not None:
25                    cur = parent[cur]  # type: ignore[index]
26                    path.append(cur)
27                path.reverse()
28                return path
29
30            queue.append(neighbor)
31
32    return []
33
34
35graph_data = {
36    "home": ["a", "b"],
37    "a": ["c"],
38    "b": ["c", "d"],
39    "c": ["office"],
40    "d": ["office"],
41    "office": [],
42}
43
44print(shortest_path_unweighted(graph_data, "home", "office"))

This approach runs in linear time relative to nodes plus edges, which is efficient for many practical datasets.

BFS on Trees and Layered Processing

For trees, BFS is often called level order traversal. It helps when operations depend on depth, such as rendering organizational charts, computing level averages, or scheduling tasks by dependency depth.

python
1from collections import deque
2
3
4def level_order_levels(tree: dict[str, list[str]], root: str) -> list[list[str]]:
5    levels: list[list[str]] = []
6    queue = deque([(root, 0)])
7
8    while queue:
9        node, depth = queue.popleft()
10        if depth == len(levels):
11            levels.append([])
12        levels[depth].append(node)
13
14        for child in tree.get(node, []):
15            queue.append((child, depth + 1))
16
17    return levels
18
19
20tree_data = {
21    "CEO": ["CTO", "CFO"],
22    "CTO": ["Dev1", "Dev2"],
23    "CFO": ["Fin1"],
24    "Dev1": [],
25    "Dev2": [],
26    "Fin1": [],
27}
28
29print(level_order_levels(tree_data, "CEO"))

Common Pitfalls

A common mistake is marking nodes as visited only when popped from the queue. Marking on enqueue is usually safer because it avoids duplicate queue entries and unnecessary memory growth.

Another issue is using BFS on weighted graphs and expecting shortest weighted path. BFS gives shortest by number of edges only. For weighted graphs, use algorithms such as Dijkstra.

A third issue is forgetting disconnected nodes. If you need full graph coverage, run BFS from every unvisited node, not just one starting point.

Summary

  • BFS explores graphs level by level using a queue.
  • It is ideal for shortest paths in unweighted graphs.
  • Parent tracking allows full path reconstruction.
  • Level order traversal is a direct BFS pattern on trees.
  • Mark visited nodes on enqueue to avoid duplicate work.
Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
Codemia
© 2026 Codemia
Resources
Legal
Social
All Rights Reserved.