Breadth-First Search (BFS) Visualizer & Step-by-Step Tool

How this BFS visualizer works

This tool lets you define any small graph using an adjacency list, then runs breadth-first search (BFS) from a chosen start node. You can step through the algorithm, watch the queue evolve, and see how BFS builds a shortest-path tree.

Adjacency list format

Each line describes one node and its neighbors:

• Left of : is the node label (e.g. A).
• Right side is a space-separated list of neighbors.
• For undirected graphs, you usually list edges in both directions (A: B and B: A).

BFS algorithm (pseudocode)

function BFS(start):
    create empty queue Q
    create empty set visited
    create map dist, parent

    enqueue(Q, start)
    visited.add(start)
    dist[start] = 0
    parent[start] = null

    while Q is not empty:
        u = dequeue(Q)          // current node
        for each neighbor v of u:
            if v not in visited:
                visited.add(v)
                dist[v] = dist[u] + 1
                parent[v] = u
                enqueue(Q, v)

If you want the shortest path from start to some target, you can stop the loop once you dequeue target, then reconstruct the path using the parent map.

Key properties of BFS

• Traversal order: explores the graph level by level (all nodes at distance 1, then 2, etc.).
• Shortest paths: in an unweighted graph, BFS finds the shortest path (fewest edges) from the start node to every reachable node.
• Data structure: uses a queue (FIFO) to manage the frontier.
• Complexity: time O(V + E), space O(V + E) with adjacency lists.

When to use BFS

• Finding the shortest path in an unweighted graph (e.g. grid mazes, social networks).
• Computing connected components (by running BFS from each unvisited node).
• Level-order traversal of trees (BFS on a tree).
• Checking bipartiteness (2-coloring) of a graph.

Time and space complexity

Let V be the number of vertices and E the number of edges.

• Time: each vertex is enqueued and dequeued at most once, and each edge is inspected at most twice (undirected) or once (directed). So the total time is O(V + E).
• Space: you store the adjacency list, visited set, queue, distance and parent arrays, which together require O(V + E) space.

Reconstructing the shortest path

After BFS finishes (or after you reach the target), you can reconstruct the shortest path by following the parent links backwards:

function get_path(start, target, parent):
    if target not reachable:
        return []

    path = []
    cur = target
    while cur is not null:
        path.append(cur)
        cur = parent[cur]
    reverse(path)
    return path

In this visualizer, when you provide both a start and a target node, the tool automatically reconstructs and highlights this path.

Common BFS pitfalls

• Forgetting to mark visited when enqueuing: you should mark a node visited as soon as you enqueue it, not when you dequeue it, to avoid duplicates in the queue.
• Using BFS on weighted graphs: BFS only gives shortest paths when all edges have equal weight. For weighted graphs, use Dijkstra or Bellman–Ford.
• Not handling disconnected graphs: BFS from one start node only covers its connected component. To visit all nodes in a disconnected graph, run BFS from each unvisited node.