BFS Visualizer Online

Pseudocode

The whole algorithm is a queue and a visited set. Everything else BFS is famous for follows from the order in which the queue hands nodes back.

BFS(graph, source):
    visited = {source}
    dist[source] = 0
    queue = [source]

    while queue is not empty:
        u = queue.removeFirst()
        for each neighbor v of u:
            if v not in visited:
                visited.add(v)
                dist[v] = dist[u] + 1
                parent[v] = u
                queue.addLast(v)

The invariant is that the queue always holds nodes from at most two consecutive distance levels, in nondecreasing order of distance. That single property is what makes dist correct: a node is assigned its distance the first time it is seen, and it can never be reached more cheaply later.

Worked example, step by step

Run BFS from A on the graph the visualizer loads by default, so you can follow along step for step in the panel above.

Example graph: Undirected edges A-B (2), A-C (3), B-C (1) and C-D (4). BFS ignores the weights entirely and counts hops, so every edge is worth one.

1. Start. Mark A visited with dist 0 and put it in the queue. Queue: [A].
2. Dequeue A. A has neighbors B and C, neither visited. Both get dist 1 and parent A. Queue: [B, C].
3. Dequeue B. B has neighbors A and C. Both are already visited: A as the source, C claimed a moment ago by A. Nothing is added. This is the step that shows why BFS never revisits, since reaching C through B would cost 2 hops against the 1 already recorded. Queue: [C].
4. Dequeue C. C has neighbors A, B and D. Only D is new, so it gets dist 2 and parent C. Queue: [D].
5. Dequeue D. D only neighbor is C, already visited. The queue empties and the search ends.

Final distances are A 0, B 1, C 1, D 2, and the parent pointers give the shortest-path tree A to B, A to C, and C to D. Note that BFS routes to D through C even though the weighted cost that way is 7 against the 3 of A to B to C: hop count is all it optimises, which is exactly why weighted graphs need Dijkstra instead.

Complexity, and where it comes from

Time: O(V + E) · Space: O(V)

Each vertex enters the queue at most once, because it is marked visited at the moment it is enqueued rather than when it is dequeued. That bounds the outer loop at V iterations. Inside the loop, the work is proportional to the degree of the current vertex, and the sum of all degrees is 2E in an undirected graph, so the neighbor scanning totals O(E). Space is dominated by the visited set, the distance array and the queue, each O(V). On an adjacency matrix the neighbor scan becomes O(V) per vertex and the whole run degrades to O(V squared).

When to use Breadth-First Search, and when not to

BFS is the right default whenever edges are unweighted. The moment weights appear, or the goal changes from distance to structure, something else wins.

Common pitfalls

• Marking visited on dequeue instead of enqueue. If a node is only marked when it comes off the queue, it can be enqueued many times before its first dequeue. On dense graphs this turns a linear traversal into a quadratic one and can exhaust memory. Mark it visited at the moment you push it.
• Using BFS on a weighted graph. BFS counts hops, not weight. On a graph where A to C costs 100 in one edge and A to B to C costs 2 in two edges, BFS reports the 100-cost path as shorter. Reach for Dijkstra instead.
• Reconstructing the path from distances alone. Distances tell you how far, not which way. Store a parent pointer when you assign a distance, then walk parents back from the target and reverse.
• Recursing instead of queuing. A recursive traversal is depth-first no matter what you name it. BFS needs an explicit FIFO queue; there is no natural recursive formulation.

Frequently asked questions

What is breadth-first search used for?

BFS finds the shortest path in unweighted graphs, tests connectivity and bipartiteness, and traverses trees level by level. It is also the augmenting-path search inside Edmonds-Karp for maximum flow, and it backs the shortest-hop queries in social and routing networks.

What is the time complexity of BFS?

O(V + E) time and O(V) space with an adjacency list, where V is the number of vertices and E the number of edges. With an adjacency matrix it becomes O(V squared) because each neighbor scan costs O(V) regardless of the actual degree.

Does BFS always find the shortest path?

Yes on unweighted graphs, and no on weighted ones. BFS expands nodes in nondecreasing order of hop count, so the first time it reaches a node it has used the fewest possible edges. As soon as edges carry different weights that guarantee breaks, because the fewest edges and the lowest total weight stop being the same thing.

What is the difference between BFS and DFS?

BFS explores level by level using a queue and finds shortest paths in unweighted graphs. DFS follows one branch to its end using a stack or recursion and reveals structure such as cycles, topological order and strongly connected components. BFS uses more memory on wide graphs, DFS uses more on deep ones.

Can BFS detect a cycle?

Yes. In an undirected graph, if BFS reaches an already visited node that is not the parent of the current node, that edge closes a cycle. In a directed graph BFS is a poor fit and Kahn topological sort or a DFS with edge classification is the standard approach.