Modules / Algorithms / Breadth-First Search

Breadth-First Search (BFS)

Algorithms & Data StructuresBy Ashish JangraUpdated 26 October 2026

Traverse a tree level by level the way breadth-first search does, and compare it against the depth-first orders on the same nodes.

1. Node Operations

2. Quick Actions

Status Log

Ready

CANVAS VIEW

Tree Metrics

Height 0

Nodes 0

Leaves 0

Balanced Yes

Traversals

Output Sequence

Overview

Start by marking the source visited and adding it to a queue. Repeatedly remove the front node and add its unvisited neighbours to the back. Since older discoveries leave first, every node at distance (d) is processed before nodes at distance (d+1).

The queue determines the order

The visualizer is a tree, where BFS is the Level (BFS) traversal. From root 8, it visits 8, then the next level 3 and 10, then 1, 6, and 14. Inorder, Preorder, and Postorder are depth-first traversals; they answer different ordering questions.

Press Random to build a new tree, then compare Level (BFS) with a depth-first order. Watch the highlight finish each level before moving lower. The tree view shows the traversal order; in a general graph, each node also needs a visited mark because cycles can lead back to previously seen nodes.

A graph implementation

from collections import deque

def bfs(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)  # mark when enqueued
                queue.append(neighbour)
    return order

Marking a node when it enters the queue prevents multiple neighbours from adding it repeatedly. To recover shortest paths, store each node’s predecessor when first discovered. Because BFS discovers nodes in distance order, that predecessor chain uses the fewest edges from the source.

When BFS applies

BFS finds shortest paths by edge count in an unweighted graph, and in a graph whose edges all have equal cost. It does not find minimum-cost paths when edge weights differ; use Dijkstra’s algorithm for nonnegative weights. For adjacency lists, BFS takes O(V + E) time and O(V) extra space.

Common mistakes with Breadth First Search

Using a stack: that produces depth-first search instead of BFS.
Marking visited only after removal: the same node can be queued many times.
Using BFS for unequal edge costs: fewest edges need not mean lowest cost.
**Using list.pop(0) in Python:** removing the first list item shifts the rest; use collections.deque.

Sources and next steps

Princeton Algorithms: Breadth-first search covers graph traversal and shortest paths.
Continue with depth-first search and Dijkstra’s algorithm.

Run it in Python

BFS printed level by level, then used for what it is actually for: the shortest path in an unweighted graph. The queue contents are shown at every step so the frontier is visible.

bfs.pyPython 3

# Breadth-first search: explore everything one step away, then two, then...
from collections import deque

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

def bfs(graph, start):
    visited = {start}                # marked when ENQUEUED, not when dequeued
    queue = deque([start])
    order, parent, dist = [], {start: None}, {start: 0}

    while queue:
        print(f"  queue: {list(queue)}")
        node = queue.popleft()       # popleft = FIFO = breadth-first
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                parent[neighbour] = node
                dist[neighbour] = dist[node] + 1
                queue.append(neighbour)
    return order, parent, dist


print("BFS from A:")
order, parent, dist = bfs(graph, "A")
print()
print("visit order:", " -> ".join(order))

print()
levels = {}
for node, d in dist.items():
    levels.setdefault(d, []).append(node)
for d in sorted(levels):
    print(f"  {d} step(s) from A: {levels[d]}")

# Rebuild the path by walking parents backwards from the target.
target = "G"
path, node = [], target
while node is not None:
    path.append(node)
    node = parent[node]
print()
print(f"shortest path A -> {target}:", " -> ".join(reversed(path)),
      f"({dist[target]} edges)")

Output

How the code works

queue = deque([start])A deque, not a list: list.pop(0) is O(n) because it shifts every remaining item. On a large graph that alone turns a linear traversal quadratic.
visited.add(neighbour) # on enqueueMarking on enqueue rather than on dequeue is the difference between BFS and a slow disaster. Mark late and a node with three neighbours already in the queue gets added three times.
node = queue.popleft()First in, first out. Change this one call to pop() and the same twelve lines become depth-first search — the container is the algorithm.
dist[neighbour] = dist[node] + 1Because nodes are dequeued in order of distance, the first time BFS reaches a node is necessarily by a shortest path. This is why BFS solves shortest paths on unweighted graphs and Dijkstra is not needed.
while node is not None: path.append(node)The parent map is a tree rooted at the start, so the path is recovered by walking up it. Storing the whole path per node instead would cost O(V) memory per node for no benefit.

Change one thing

Change popleft() to pop(). The visit order becomes depth-first and the distances stop being shortest paths.
Move visited.add to just after popleft(), then print the queue length. Nodes appear more than once — the classic BFS bug.
Add the edge "A": ["B", "C", "G"]. The path to G drops to one edge, and the level listing rearranges itself.

Where this runs

Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.

Predict, then reveal

About to run: press Node Operations. Before it does — what happens to the readout?

Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.

Check yourself

0 of 3

Answer without scrolling back up.

Turning BFS into DFS requires changing:
Why does the code mark a node visited when it is enqueued rather than when it is dequeued?
BFS gives shortest paths on an unweighted graph because:

Cheat sheet