Breadth First Search in Python (BFS Algorithm) with Examples

You have a graph and a starting node, and you want to visit everything you can reach from it, closest nodes first. That's the exact job of breadth first search. It checks all the nodes one step from the start, then the nodes two steps away, and keeps going level by level until there's nothing left to visit.

BFS is the algorithm you want when you care about distance from the start. It's how you find the fewest moves in a maze, the shortest chain between two people, or the closest matching item in a network. This lesson builds it from scratch in plain Python, shows why collections.deque is the right tool for the queue, and then goes further than a single traversal: shortest paths, level order, disconnected graphs, and the mistakes that trip people up.

What breadth first search actually is

A graph is just a set of things (called nodes or vertices) with connections between them (called edges). A social network is a graph. So is a map of cities joined by roads, or a web of pages joined by links.

Breadth first search is a way to visit every node you can reach from a starting point, in order of how far away they are. You visit all the neighbours of the start first. Then the neighbours of those neighbours. Then the next layer. You never jump ahead to a far node while a closer one is still unvisited. That "closest first" order is the whole point, and it's what makes BFS good at shortest-path problems on unweighted graphs.

The other main way to walk a graph is depth first search, which dives down one path as far as it can before backing up. BFS spreads out; DFS goes deep. We'll compare them properly later on.

How to represent a graph in Python

Before you can search a graph, you need to store it. The common way is an adjacency list: a dictionary where each key is a node and its value is the list of nodes it connects to.

Here's a small graph with six nodes named A through F:

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

print(graph["B"])
# Output: ['A', 'D', 'E']

This graph is undirected, so if A connects to B, then B connects back to A. You can see that both directions are listed. If you were building a one-way graph, like web links, you'd only list the direction that exists.

The queue and the visited set

BFS needs two things to work: a queue and a visited set.

The queue holds the nodes you've discovered but haven't explored yet. It works first in, first out, like a line at a shop. The node you added first is the node you deal with first. That ordering is exactly what keeps closer nodes ahead of farther ones. If you're new to the idea, our post on stacks and queues covers it in full.

The visited set remembers every node you've already seen, so you don't process the same node twice. Graphs have cycles. Without a visited set, BFS on the graph above would bounce between A and B forever.

The loop is short. Take the node at the front of the queue. Look at its neighbours. Any neighbour you haven't seen, mark as visited and add to the back of the queue. Repeat until the queue is empty.

Why deque and not a plain list

You'll see a lot of tutorials use a normal Python list as the queue, calling queue.pop(0) to take the front item. It works, but it's slow, and here's why.

A list stores its items in one block of memory. When you remove the first item with pop(0), Python has to shift every other item one place to the left to fill the gap. On a list of n items that's n moves. Do it for every node and your BFS quietly becomes O(n squared) on the queue operations alone.

collections.deque (say "deck", short for double ended queue) is built for this. Adding to the back and removing from the front are both O(1), constant time, no shifting. That's the difference:

from collections import deque

q = deque(["A", "B", "C"])
q.append("D")        # add to the back, O(1)
front = q.popleft()  # remove from the front, O(1)
print(front)
print(q)
# Output:
# A
# deque(['B', 'C', 'D'])

list.pop(0) gives you the same value, but at O(n) each time. For a small graph you won't notice. For a big one it's the difference between fast and painfully slow. Use deque for the BFS queue. That's the version we'll build.

Walking through the search step by step

Let's trace BFS by hand on the A to F graph, starting at A. This is the same graph from the diagram above, and following it slowly makes the code obvious.

We begin with A in the queue and marked visited. Then we repeat: pull the front node, add its unseen neighbours to the back.

Here's every step written out:

• Start. Queue is [A], visited is {A}.
• Dequeue A. Its neighbours are B and C, both new. Add them. Queue [B, C], visited {A, B, C}.
• Dequeue B. Neighbours A, D, E. A is already visited, so add D and E. Queue [C, D, E], visited {A, B, C, D, E}.
• Dequeue C. Neighbours A, F. A is seen, add F. Queue [D, E, F], visited {A, B, C, D, E, F}.
• Dequeue D. Only neighbour is B, already seen. Nothing to add. Queue [E, F].
• Dequeue E. Neighbours B and F, both seen. Queue [F].
• Dequeue F. Neighbours C and E, both seen. Queue is empty. Done.

The order we visited nodes is A, B, C, D, E, F. Notice how it went level by level: A first, then A's neighbours (B, C), then their new neighbours (D, E, F). That's breadth first order.

The main BFS implementation with deque

Now the code. It's a direct translation of the walkthrough. Take a node off the front, look at each neighbour, queue the new ones:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

    return order

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

print(bfs(graph, "A"))
# Output: ['A', 'B', 'C', 'D', 'E', 'F']

One detail that matters: mark a node visited when you add it to the queue, not when you take it out. If you wait until you dequeue it, the same node can get added several times before it's processed, once by each neighbour that points at it. Marking on the way in stops that.

Reading the queue and visited state as a table

Here's the same run laid out as a table, so you can watch both structures change on every turn of the loop. "Dequeued" is the node pulled off the front, "Added" is the new neighbours pushed to the back.

Step	Dequeued	Added	Queue after	Visited after
1	A	B, C	[B, C]	A, B, C
2	B	D, E	[C, D, E]	A, B, C, D, E
3	C	F	[D, E, F]	A, B, C, D, E, F
4	D	none	[E, F]	A, B, C, D, E, F
5	E	none	[F]	A, B, C, D, E, F
6	F	none	[]	A, B, C, D, E, F

The queue grows while there's new ground to cover, then drains once every node has been seen. When it hits empty, the search is over.

BFS on a tree for level order

A tree is a graph with no cycles, so BFS on a tree has a nice name: level order traversal. It visits the root, then everything on level 1, then level 2, and so on.

Often you want more than the flat order. You want the nodes grouped by their level. The trick is to check how many nodes are in the queue at the start of each round. That count is exactly one full level, so you process that many, collect them, and whatever's left in the queue is the next level.

from collections import deque

tree = {
    1: [2, 3],
    2: [4, 5],
    3: [6, 7],
    4: [], 5: [], 6: [], 7: [],
}

def level_order(tree, root):
    levels = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        current = []
        for _ in range(level_size):
            node = queue.popleft()
            current.append(node)
            for child in tree[node]:
                queue.append(child)
        levels.append(current)
    return levels

print(level_order(tree, 1))
# Output: [[1], [2, 3], [4, 5, 6, 7]]

No visited set here, because a tree has no cycles, so you can never come back to a node you've already passed. On a general graph you'd still need one.

Finding the shortest path in an unweighted graph

This is where BFS earns its keep. On an unweighted graph, the first time BFS reaches a node, it has reached it by the shortest possible route. There's no shorter path waiting to be found later, because BFS checks everything one step away before anything two steps away.

To turn that into an actual path, you keep a parent dictionary: for each node, remember which node you came from to reach it. Once you hit the target, you walk those parent pointers backward to the start, then reverse the list.

from collections import deque

def shortest_path(graph, start, target):
    if start == target:
        return [start]
    visited = {start}
    parent = {start: None}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                parent[neighbour] = node
                if neighbour == target:
                    # walk the parents back to the start
                    path = [target]
                    while parent[path[-1]] is not None:
                        path.append(parent[path[-1]])
                    return path[::-1]
                queue.append(neighbour)
    return None   # target not reachable

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"))
# Output: ['A', 'C', 'F']

The path from A to F is A, C, F, two edges long. There's another route through B and E that's also two edges, and BFS returns whichever it reaches first based on neighbour order. Both are shortest. If you only need the number of steps, count the edges: len(path) - 1.

One thing to be clear about: this works because every edge counts the same. If edges had different weights (a road that's longer than another), you'd need Dijkstra's algorithm instead. BFS assumes every step costs one.

Handling a disconnected graph

BFS from a single start only reaches nodes connected to that start. If your graph has separate pieces (islands with no bridge between them), a plain BFS will miss the nodes it can't reach.

Take this graph. A, B, and C form one group. X and Y form a second, with no edge joining the two:

from collections import deque

graph = {
    "A": ["B"],
    "B": ["A", "C"],
    "C": ["B"],
    "X": ["Y"],
    "Y": ["X"],
}

def bfs_from(graph, start, visited):
    order = []
    queue = deque([start])
    visited.add(start)
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)
    return order

def bfs_all(graph):
    visited = set()
    components = []
    for node in graph:               # loop over every vertex
        if node not in visited:
            components.append(bfs_from(graph, node, visited))
    return components

print(bfs_all(graph))
# Output: [['A', 'B', 'C'], ['X', 'Y']]

The fix is the outer loop over every vertex. If a node hasn't been visited by any earlier search, you start a fresh BFS from it. Each fresh start finds one connected piece, so you end up with a list of the separate groups. That's a common way to count the connected components in a graph.

BFS versus DFS

BFS and DFS visit the same nodes, just in a different order and with a different data structure behind them. BFS uses a queue and spreads out level by level. DFS uses a stack (often the call stack through recursion) and plunges down one branch first.

	BFS	DFS
Data structure	Queue (deque)	Stack or recursion
Order	Level by level, closest first	One deep branch at a time
Shortest path (unweighted)	Yes, finds it directly	No, not guaranteed
Memory	Can hold a whole level at once	Holds one path at a time
Good for	Nearest node, shortest hops, level order	Cycle detection, topological sort, path existence

Reach for BFS when the question is about distance or the fewest steps. Reach for DFS when you're exploring structure, checking whether a path exists, or working with recursion feels natural.

Time and space complexity

BFS visits each node once and looks at each edge once. So the time is O(V + E), where V is the number of vertices and E the number of edges. You touch every vertex when you dequeue it, and every edge when you scan a node's neighbour list. There's no wasted work, which is why deque matters: a slow queue would add an extra factor on top.

The space is O(V). In the worst case the queue and the visited set each hold every vertex. For a wide graph, the queue can hold a whole level at once, which is why BFS can use more memory than DFS on very bushy graphs. DFS only keeps the current path.

Where BFS gets used

BFS shows up any time "closest" or "fewest steps" is the question:

• Shortest path in a maze or grid, where every move costs the same.
• Social networks, finding the degrees of separation between two people.
• Web crawlers, visiting pages layer by layer out from a seed page.
• GPS and routing on unweighted maps, and as the base idea behind weighted versions like Dijkstra.
• Broadcasting and networks, working out how far a message spreads in each hop.

Graph traversal comes up a lot in coding interviews too, so it's worth being fluent in it. If you're preparing, a timed run through problems with an AI mock interview is a good way to practice explaining your BFS out loud.

Common mistakes with BFS

• Using list.pop(0) as the queue. It's O(n) every time because the list shifts. Use collections.deque and popleft() for O(1).
• Marking visited on dequeue instead of enqueue. If you wait, a node can be added many times before it's processed. Mark it the moment you push it onto the queue.
• Forgetting the visited set on a graph with cycles. Without it, BFS loops forever between connected nodes. A tree is the only case where you can skip it.
• Assuming BFS gives shortest paths on weighted graphs. It doesn't. BFS treats every edge as one step. Use Dijkstra when edges have weights.
• Only searching from one start on a disconnected graph. You'll miss whole components. Loop over every vertex and start a new BFS from any that's still unvisited.
• Using a plain set and expecting a stable order. A set has no order. Keep the queue as a deque and only use the set for the "have I seen this" check.

Practice exercises

Try each one before opening the solution. Everything you need is above.

Count the nodes BFS reaches

Write a function that returns how many nodes are reachable from a start node.

# Solution
from collections import deque

def reachable_count(graph, start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)
    return len(visited)

graph = {"A": ["B", "C"], "B": ["A"], "C": ["A"], "Z": []}
print(reachable_count(graph, "A"))
# Output: 3

Find the distance to every node

Return a dictionary mapping each reachable node to its number of steps from the start.

# Solution
from collections import deque

def distances(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbour in graph[node]:
            if neighbour not in dist:
                dist[neighbour] = dist[node] + 1
                queue.append(neighbour)
    return dist

graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A"], "D": ["B"]}
print(distances(graph, "A"))
# Output: {'A': 0, 'B': 1, 'C': 1, 'D': 2}

Check if a path exists

Return True if you can get from start to target, False otherwise.

# Solution
from collections import deque

def can_reach(graph, start, target):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == target:
            return True
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)
    return False

graph = {"A": ["B"], "B": ["A", "C"], "C": ["B"], "X": ["Y"], "Y": ["X"]}
print(can_reach(graph, "A", "C"))
print(can_reach(graph, "A", "X"))
# Output:
# True
# False

Print each level on its own line

Given a tree as an adjacency dict, print each level as a separate list.

# Solution
from collections import deque

def print_levels(tree, root):
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node)
            for child in tree[node]:
                queue.append(child)
        print(level)

tree = {1: [2, 3], 2: [4], 3: [], 4: []}
print_levels(tree, 1)
# Output:
# [1]
# [2, 3]
# [4]

Shortest path length between two nodes

Return the number of edges on the shortest path, or -1 if there's no path.

# Solution
from collections import deque

def path_length(graph, start, target):
    if start == target:
        return 0
    visited = {start}
    queue = deque([(start, 0)])
    while queue:
        node, steps = queue.popleft()
        for neighbour in graph[node]:
            if neighbour == target:
                return steps + 1
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append((neighbour, steps + 1))
    return -1

graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"]}
print(path_length(graph, "A", "D"))
# Output: 2

Frequently asked questions

What is breadth first search in Python?

It's a way to visit every node reachable from a starting node, in order of distance from that start. You use a queue to hold nodes waiting to be explored and a set to remember which ones you've already seen. In Python the queue is a collections.deque and the graph is usually a dictionary of lists.

Why use collections.deque instead of a list for BFS?

Removing the front item of a list with pop(0) is O(n), because every other item shifts down. A deque removes from the front with popleft() in O(1). On a large graph that changes BFS from slow to fast, so deque is the right choice for the queue.

Does BFS always find the shortest path?

On an unweighted graph, yes. The first time BFS reaches a node is by a shortest route, because it checks all nodes one step away before any node two steps away. On a weighted graph it doesn't, and you'd use Dijkstra's algorithm instead.

What's the difference between BFS and DFS?

BFS uses a queue and spreads out level by level, so it's good for shortest paths. DFS uses a stack or recursion and goes deep down one branch first, so it's good for things like cycle detection and topological sorting. They visit the same nodes in a different order.

What is the time complexity of BFS?

O(V + E), where V is the number of vertices and E the number of edges. BFS visits each vertex once and looks at each edge once. The space is O(V), because the queue and visited set can each hold every vertex in the worst case.

How do I run BFS on a disconnected graph?

Loop over every vertex in the graph. For each one that hasn't been visited yet, start a fresh BFS from it. Each fresh start covers one connected piece, so you end up visiting all of them, and you can collect each run as a separate connected component.

Do I need a visited set for a tree?

No. A tree has no cycles, so you can never return to a node you've already passed. You only need a visited set on a general graph, where cycles can send you round in circles.

Key takeaways

• BFS explores a graph level by level from a start node, closest nodes first, using a queue and a visited set.
• Store the graph as a dictionary adjacency list, and use collections.deque for the queue so removing the front is O(1), not O(n) like list.pop(0).
• Mark a node visited when you add it to the queue, never when you take it out.
• On an unweighted graph, BFS finds the shortest path. Track a parent dictionary and walk it back from the target to rebuild the route.
• Loop over every vertex to handle a disconnected graph, and remember the cost: O(V + E) time, O(V) space.

Now that BFS makes sense, the natural next step is its opposite. Where BFS works through a graph level by level, depth first search dives straight down a path before backtracking, and the two together cover almost every graph problem you'll meet.