BFS Visualizer — Breadth-First Search

How it works

1. Mark the start node s as seen, set dist[s] = 0 and put s in a queue.
2. Dequeue the node u at the front of the queue.
3. For each neighbour v of u that has not been seen: mark it seen, set dist[v] = dist[u] + 1 and parent[v] = u, and enqueue it.
4. Skip neighbours that were already seen — they are waiting in the queue or already done.
5. Repeat until the queue is empty. Nodes that were never seen are unreachable from s.

Why a queue gives shortest paths

Think of ripples on a pond. The queue only ever holds nodes from two consecutive levels: those at distance d at the front, and the nodes at distance d + 1 they are discovering at the back. Because the queue is first-in, first-out, every node at distance d leaves before any node at distance d + 1.

So when BFS discovers v from u, no shorter route to v can exist — it would have to pass through a node that was dequeued earlier, and that node would have discovered v first. This is why dist[v] is final the moment it is set, and why following parent pointers back from any node spells out a fewest-edge path.

The argument relies on every edge costing the same. With weights, a route with more edges can be cheaper, and the FIFO queue no longer hands out nodes in order of cost. Dijkstra's algorithm fixes exactly that by replacing the queue with a priority queue.

Worked example

The visualizer opens on a 7-node undirected graph with edges A–B, A–C, B–C, B–D, B–E, C–D, C–F, D–E, D–F, E–G and F–G (weights hidden — BFS ignores them). Neighbours are examined in alphabetical order. Starting from A:

• Dequeue A: discover B and C at distance 1. Queue: B, C.
• Dequeue B: A and C are already seen; discover D and E at distance 2. Queue: C, D, E.
• Dequeue C: A, B and D are seen; discover F at distance 2. Queue: D, E, F.
• Dequeue D: every neighbour is already seen. Dequeue E: discover G at distance 3.
• Dequeue F and G: nothing new. The queue is empty, so BFS stops.

The visit order is A, B, C, D, E, F, G, and the levels are {A}, {B, C}, {D, E, F}, {G}. The tree edges A–B, A–C, B–D, B–E, C–F and E–G form the BFS tree, which gives a fewest-edge route to every node — for example A → B → E → G for G.

BFS vs DFS

Both visit every node and edge once, so both are O(V + E). They differ in the frontier they keep and in what they are good for:

• Order: BFS visits by distance from the start; DFS follows one path as deep as it can, then backtracks.
• Memory: BFS holds a whole level at once — on a star-shaped graph that is V − 1 nodes. DFS holds only the current path, O(depth).
• Answers: BFS gives shortest paths in unweighted graphs and levels; DFS gives discovery and finish times, which power cycle detection, topological sort and strongly connected components.

On the demo graph, DFS from A dives down the single chain A → B → C → D → E → G → F, six edges deep, while the BFS tree is only three levels deep.

Common mistakes

• Marking nodes as visited when they are dequeued instead of enqueued. A node can then enter the queue once per incoming edge, wasting up to O(E) queue space and risking an overwritten dist. Mark it the moment you enqueue it.
• Using a list as the queue. In Python list.pop(0) shifts every element, costing O(n) per dequeue; use collections.deque.
• Using BFS for weighted shortest paths. It returns the route with the fewest edges, not the lowest total weight.
• Forgetting disconnected graphs. One BFS only reaches the start's component. Loop over all nodes and start a new BFS from each unseen one — the number of starts is the number of connected components.
• Scanning an adjacency matrix. Finding neighbours by scanning a row makes BFS O(V²) instead of O(V + E).

Where BFS is used

• Grids and mazes: each cell is a node and each move an edge, so BFS finds the minimum number of moves (knight moves, robot paths, word ladder).
• Multi-source BFS: enqueue several starts at distance 0 to get the distance to the nearest source, as in "rotting oranges" or nearest-hospital maps.
• Bipartite check: colour nodes by level parity; an edge between two nodes of the same colour reveals an odd cycle.
• 0-1 BFS: with weights of only 0 and 1, a double-ended queue (push 0-edges to the front) replaces Dijkstra.
• Level-order traversal of a tree is BFS on a tree.

Outside interviews, BFS powers web crawlers, "people within two hops" features on social networks, broadcast in computer networks, and Cheney's copying garbage collector, which copies live objects in breadth-first order.

Time and space complexity

Breadth-First Search in Python

from collections import deque


def bfs(graph, s):
    """graph: {node: [neighbours]}. Returns dist[v] = fewest edges from s to v."""
    dist = {s: 0}
    seen = {s}
    queue = deque([s])
    while queue:                        # while queue not empty
        u = queue.popleft()             # u <- queue.dequeue()
        for v in graph[u]:              # each neighbour v of u
            if v not in seen:
                dist[v] = dist[u] + 1
                seen.add(v)
                queue.append(v)
            # else: v was already seen - skip it
    return dist

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• DFS Visualizer — Depth-First SearchDepth-first search explores a graph by going as deep as possible, then backtracking. See DFS step by step with discovery and finish times, back edges and code.
• Dijkstra's Algorithm VisualizerDijkstra's algorithm finds the shortest paths from one node in a graph with non-negative weights. Watch every relaxation step by step, with heap-based code.
• Topological Sort VisualizerA topological sort orders the nodes of a DAG so every edge points forward. Watch Kahn's algorithm step by step, see why cycles block it, and get the code.
• Queue VisualizerInteractive queue visualizer: watch enqueue and dequeue move the front and rear of an array queue, and see the wasted-space problem that circular queues fix.
• Tree Traversal Visualizer — Inorder, Preorder, Postorder, Level OrderVisualize inorder, preorder, postorder and level-order tree traversal on one tree: the visit order, the call stack or queue, the code, and when to use each.
• Graph Algorithm VisualizerInteractive graph algorithm visualizer: draw or generate a graph and step through BFS, DFS, Dijkstra, Bellman-Ford, Kruskal, Prim, topological sort and SCCs.