BFS — Breadth First Search
- BFS uses a queue (deque) — FIFO ensures level-by-level traversal.
- Mark nodes as visited when enqueuing, not when dequeuing — prevents duplicate processing.
- BFS finds the shortest path in unweighted graphs because it processes nodes in order of distance.
BFS explores a graph level by level — all neighbours of the current node before moving deeper. Use a queue (deque) to track nodes to visit. BFS finds the shortest path in unweighted graphs because it processes nodes in order of their distance from the source. Time complexity: O(V + E).
How BFS Works — Plain English and Step-by-Step
BFS answers the question: 'What are all the nodes I can reach, in order of how many hops they are from my starting point?' Think of dropping a stone in a pond — ripples spread outward one ring at a time, and BFS visits nodes the same way: every node at distance 1 first, then every node at distance 2, and so on.
The algorithm requires three ingredients: a queue (FIFO) to decide the order of visiting, a visited set to avoid revisiting nodes, and the graph itself.
Step-by-step: 1. Add the start node to the queue and mark it visited. 2. While the queue is non-empty, dequeue the front node. 3. Process the dequeued node (record it, check a goal, etc.). 4. For each neighbour of the current node: if unvisited, mark it visited and enqueue it. 5. Repeat from step 2.
Worked example on the graph A-B, A-C, B-D, B-E, C-F starting from A: Round 1: dequeue A. Enqueue B, C. Visited={A,B,C}. Order=[A] Round 2: dequeue B. Enqueue D, E (A already visited). Visited={A,B,C,D,E}. Order=[A,B] Round 3: dequeue C. Enqueue F (A visited). Visited={A,B,C,D,E,F}. Order=[A,B,C] Round 4: dequeue D. No new neighbours. Order=[A,B,C,D] Round 5: dequeue E. F already visited. Order=[A,B,C,D,E] Round 6: dequeue F. Done. Order=[A,B,C,D,E,F]
Notice B and C (distance 1 from A) both appear before D, E, F (distance 2). That level-by-level guarantee is why BFS finds shortest paths in unweighted graphs: the first time you reach a node, you have used the fewest possible hops.
BFS on a Graph
The implementation uses Python's collections.deque, which provides O(1) append and popleft. Never use a plain list as a BFS queue — list.pop(0) is O(n) and will make your BFS O(V*E) instead of O(V+E). The visited set uses hashing for O(1) membership checks, which is essential when the graph is large.
# Package: io.thecodeforge.python.algorithms from collections import deque def bfs(graph, start): """Visit all reachable nodes in BFS order.""" visited = set() queue = deque([start]) visited.add(start) order = [] while queue: node = queue.popleft() # FIFO — dequeue from left order.append(node) for neighbour in graph[node]: if neighbour not in visited: visited.add(neighbour) queue.append(neighbour) # enqueue to right return order # Adjacency list representation graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } print(bfs(graph, 'A')) # ['A', 'B', 'C', 'D', 'E', 'F']
Shortest Path with BFS
BFS naturally finds the shortest path in an unweighted graph. Track the parent of each node to reconstruct the path.
from collections import deque def shortest_path(graph, start, end): if start == end: return [start] visited = {start} queue = deque([[start]]) # each item is a path while queue: path = queue.popleft() node = path[-1] for neighbour in graph[node]: if neighbour not in visited: new_path = path + [neighbour] if neighbour == end: return new_path visited.add(neighbour) queue.append(new_path) return None # no path exists graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } print(shortest_path(graph, 'A', 'F')) # ['A', 'C', 'F'] print(shortest_path(graph, 'A', 'D')) # ['A', 'B', 'D']
['A', 'B', 'D']
Level-Order Tree Traversal
Level-order traversal is BFS applied to a binary tree. To separate the output by level, snapshot the queue length before processing each level. That snapshot tells you exactly how many nodes belong to the current level — process exactly that many, collecting children for the next level as you go. This avoids the need for sentinel values or separate level-tracking variables.
from collections import deque class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right def level_order(root): if not root: return [] result = [] queue = deque([root]) while queue: level_size = len(queue) # nodes at this level level = [] for _ in range(level_size): node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result # Build tree: 1 # / \ # 2 3 # / \ \ # 4 5 6 root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6))) print(level_order(root)) # [[1], [2, 3], [4, 5, 6]]
🎯 Key Takeaways
- BFS uses a queue (deque) — FIFO ensures level-by-level traversal.
- Mark nodes as visited when enqueuing, not when dequeuing — prevents duplicate processing.
- BFS finds the shortest path in unweighted graphs because it processes nodes in order of distance.
- Time: O(V + E); Space: O(V) for the visited set and queue.
- For level-order traversal, snapshot queue size before the inner loop to group nodes by level.
Interview Questions on This Topic
- QWhat data structure does BFS use and why?
- QWhat is the time and space complexity of BFS?
- QWhy is BFS preferred over DFS for finding shortest paths in unweighted graphs?
Frequently Asked Questions
When should I use BFS vs DFS?
Use BFS for shortest path in unweighted graphs, level-order traversal, and finding closest matches. Use DFS for detecting cycles, topological sort, path existence (not shortest), and exploring all possibilities (combinatorics). BFS uses more memory (all nodes at current level) while DFS uses less (just the current path).
Why must I mark nodes as visited when enqueuing, not when dequeuing?
If you mark when dequeuing, the same node can be added to the queue multiple times before it is processed. This causes O(V²) queue size in dense graphs and incorrect shortest path computations. Mark when enqueuing to ensure each node enters the queue exactly once.
Does BFS work on disconnected graphs?
A single BFS call only visits nodes reachable from the start node. For a disconnected graph, loop over all nodes and call BFS on any that have not been visited — the same pattern used to count connected components.
What is the space complexity of BFS in the worst case?
O(V). In the worst case (a star graph), the queue holds all V-1 neighbours simultaneously after the first dequeue. The visited set also grows to O(V).
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.