Quick answer: Breadth-first search explores a graph in layers. Put the start node in a deque, mark nodes visited when enqueued, and process neighbors with popleft so the first visit gives the shortest unweighted distance.
Breadth-first search, or BFS, visits a graph level by level. It starts at one node, visits all immediate neighbors, then visits neighbors of those neighbors. In Python, the standard way to implement BFS is with collections.deque for the queue.
BFS is useful for shortest paths in an unweighted graph, graph traversal, level-order tree traversal, connected component discovery, and grid problems. Python’s official documentation covers deque, which provides efficient queue operations. Breadth-first search becomes level-order traversal when the graph is a tree; Level Order Traversal in Python shows the queue, per-level boundaries, and returned levels.
The core idea is simple: add the start node to a queue, mark it as visited, then repeatedly remove one node from the left side of the queue. For each unvisited neighbor, mark it and add it to the right side of the queue.
BFS differs from depth-first search because it explores nearby nodes before going deeper. That is why it is the right choice when every edge has the same cost and you want the fewest edges from a start node to a target node.
The running time is O(V + E) for a graph with V nodes and E edges, assuming adjacency lists. Each node is visited once, and each edge is inspected at most a small constant number of times.
Basic BFS Traversal
This example prints nodes in breadth-first order.
from collections import deque
graph = {
"A": ["B", "C"],
"B": ["D", "E"],
"C": ["F"],
"D": [],
"E": [],
"F": [],
}
visited = {"A"}
queue = deque(["A"])
while queue:
node = queue.popleft()
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
The queue ensures that nodes discovered earlier are processed earlier.
Marking a node as visited when it enters the queue prevents duplicates and avoids infinite loops in graphs with cycles.
Do not wait until a node is removed from the queue to mark it. In a graph with multiple incoming edges, the same neighbor could be added several times before it is processed.
Return BFS Order From A Function
A reusable BFS function should return the traversal order instead of printing inside the loop.
from collections import deque
def bfs_order(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
graph = {"A": ["B", "C"], "B": ["D"], "C": [], "D": []}
print(bfs_order(graph, "A"))
graph.get(node, []) lets the function handle nodes that have no outgoing edges listed.
Returning a list is useful for tests, logging, and any code that needs to use the traversal result later.
A function also keeps the queue and visited set local to one search. That avoids accidental reuse between separate graph runs.
Find A Shortest Path
In an unweighted graph, BFS finds the shortest path by number of edges.
from collections import deque
def shortest_path(graph, start, goal):
queue = deque([start])
parent = {start: None}
while queue:
node = queue.popleft()
if node == goal:
break
for neighbor in graph.get(node, []):
if neighbor not in parent:
parent[neighbor] = node
queue.append(neighbor)
if goal not in parent:
return None
path = []
node = goal
while node is not None:
path.append(node)
node = parent[node]
return path[::-1]
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(shortest_path(graph, "A", "D"))
The parent map records how each node was first reached.
After the goal is found, the path is rebuilt by walking backward through the parent links.
This works because the first time BFS reaches a node, it has found the shortest unweighted route to that node. Later routes may exist, but they cannot be shorter.
Track Level Distances
BFS naturally computes distance from the start node in an unweighted graph.
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
distance = {"A": 0}
queue = deque(["A"])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in distance:
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
print(distance)
Each neighbor is one level farther than the node that discovered it.
This is the basis for many problems that ask for the minimum number of moves, steps, or edges.
Distances are also useful when grouping nodes by level. For example, all nodes with distance 2 are two edges away from the start node.
Handle Disconnected Graphs
If a graph has disconnected components, run BFS from each unvisited node.
from collections import deque
graph = {
"A": ["B"],
"B": ["A"],
"C": ["D"],
"D": ["C"],
}
visited = set()
components = []
for start in graph:
if start in visited:
continue
queue = deque([start])
visited.add(start)
component = []
while queue:
node = queue.popleft()
component.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
components.append(component)
print(components)
Each BFS run returns one connected component.
This pattern is useful for clustering, network analysis, and graph cleanup tasks.
Disconnected graphs are common when data comes from real systems. Users, files, tasks, or services may form separate groups that never connect to each other.
BFS On A Grid
Grid BFS treats each cell as a node and moves through valid neighboring cells.
from collections import deque
grid = [
[0, 0, 0],
[1, 1, 0],
[0, 0, 0],
]
start = (0, 0)
goal = (2, 2)
queue = deque([(start, 0)])
visited = {start}
while queue:
(row, col), steps = queue.popleft()
if (row, col) == goal:
print(steps)
break
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nr, nc = row + dr, col + dc
inside = 0 <= nr < len(grid) and 0 <= nc < len(grid[0])
if inside and grid[nr][nc] == 0 and (nr, nc) not in visited:
visited.add((nr, nc))
queue.append(((nr, nc), steps + 1))
The queue stores both the cell and the number of steps taken so far.
Use BFS for unweighted shortest paths. If edges have different costs, use Dijkstra’s algorithm with a priority queue instead.
For grid problems, always check boundaries before reading a cell. Then check whether the cell is blocked and whether it has already been visited. Keeping those checks in the same place makes the loop easier to debug.
In short, BFS needs a queue, a visited set, and a rule for finding neighbors. Use deque.popleft() for efficient queue removal, mark nodes before enqueueing them, and keep parent or distance maps when the result needs paths or levels.
Represent The Graph
An adjacency dictionary maps each node to its neighbors. For an undirected graph, add both directions; for a directed graph, store only outgoing edges. The traversal policy should define whether missing keys mean an empty neighbor list or invalid input.
graph = {
"A": ["B", "C"],
"B": ["D"],
"C": ["D"],
"D": [],
}
Traverse With A FIFO Queue
Marking a node when it enters the queue prevents duplicate enqueues and keeps the complexity near O(V + E) for adjacency lists. A deque’s popleft is efficient, whereas removing from the front of a list shifts every remaining element.
from collections import deque
queue = deque(["A"])
visited = {"A"}
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print(order)Record Levels And Parents
Store a distance or parent map when BFS is used for shortest unweighted paths. The first time a node is discovered is the shortest route from the start because the queue processes all nodes at one distance before the next distance.
distance = {"A": 0}
parent = {"A": None}
queue = deque(["A"])
while queue:
node = queue.popleft()
for neighbor in graph.get(node, []):
if neighbor not in distance:
distance[neighbor] = distance[node] + 1
parent[neighbor] = node
queue.append(neighbor)
print(distance)The standard library’s deque is the queue primitive used here; NetworkX also documents BFS traversal patterns for larger graph workflows.
For related traversal and queue patterns, compare level-order traversal, priority queues, and queue inspection when the graph problem needs a different frontier policy.
Frequently Asked Questions
What is breadth-first search in Python?
BFS visits a graph level by level, using a FIFO queue so every unweighted shortest path is discovered in increasing edge distance.
Why use collections.deque for BFS?
deque supports efficient append at the back and popleft at the front, matching the queue operations BFS needs.
Does BFS find the shortest path?
Yes, for an unweighted graph when neighbors are explored by edge distance and the start node is marked visited correctly.
What is the time complexity of BFS?
With adjacency lists, BFS is O(V + E), where V is the number of reachable vertices and E is the number of examined edges.