Breadth-first search (BFS)

The starting graph

Vertices A–H; undirected edges AB, AC, BD, BE, CE, CF, DG, EG and FG. H has no edges. Initially the start is A and the target is G.

Layers, not geometric distance

BFS first discovers the start at distance 0, then vertices one edge away, then two edges away, and so on. The drawing is just a layout: edge lengths on screen do not affect the answer. The graph stays still throughout playback.

This example is a simple undirected graph without weights. The player completes the entire component reachable from the start before restoring a path to the target. It does not stop at the first sight of the target. Other components remain unexplored.

Mark a vertex when adding it to the queue

Remove the front vertex, inspect its neighbors in the given order, and append each undiscovered neighbor to the back. At that moment set its distance and parent. A vertex can be discovered and still waiting: discovered does not mean fully processed.

Each vertex enters the queue once. This prevents a cycle from creating an endless traversal and prevents two different parents from enqueuing the same neighbor. Queue distances are nondecreasing. The current vertex has already left the queue; processed means all its neighbors have been inspected.

A cycle and an already queued vertex

The neighbors in the default example are in alphabetical order. After A the queue is [B, C]. While processing B, add D and E: the queue becomes [C, D, E]. C also has E as a neighbor, but E has already been discovered, so skip it and keep parent B.

The full processing order is A, B, C, D, E, F, G. Distances are A: 0, B/C: 1, D/E/F: 2 and G: 3. The isolated H is unreachable. The traversal discovers and processes 7 vertices, inspects 18 neighbor entries and reaches a maximum queue size of 3.

Neighbors inspected counts adjacency entries, including skips. An undirected edge is inspected from both ends, so the reachable component's 9 edges produce 18 inspections. The discovered counter includes the start. Path reconstruction does not change traversal counters.

One shortest path, not necessarily the only one

Follow parents from G: G, D, B, A. Reverse that sequence to obtain A → B → D → G, with 3 edges. A first-discovery parent always has distance one less. Following parents therefore reaches the start without a cycle.

Routes through E or F can also have 3 edges. A different neighbor order may choose a different parent and path, but not a different shortest distance. Change the target to H to see no path, or select the start itself as target for a zero-edge path. With no target, the player simply shows the completed traversal.

Before traversal finishes, a dash means not discovered yet. Afterwards ∞ means unreachable from this start. During reconstruction the partial path is shown from target to start; the final result is shown from start to target.

Time, memory and the saved history

With adjacency lists the upper bound is O(V + E) time. Initializing distances and parents covers every vertex, while traversal only inspects the reachable component. Queue and per-vertex data use O(V) extra memory; storing the graph itself takes O(V + E). Restoring one path takes O(V) time and output space.

The visualization has a separate cost: up to O(V + E) immutable snapshots, each with O(V) per-vertex data, for O(V(V + E)) stored history plus the shared graph. The eight-vertex scene limit is for readability, not a limit of BFS. The implementation uses a queue head index instead of repeatedly shifting an array.

JavaScript implementation

The code expects a valid simple undirected graph as a Map from vertex IDs to ordered neighbor arrays, a valid start and an optional valid target. It performs the same full traversal and parent selection as the player. The input Map and its arrays are not changed. The player also validates and copies its graph before generating snapshots.

function breadthFirstSearch(adjacency, start, target = null) {
    // Map<vertexId, vertexId[]>; a valid undirected graph.
    const distance = new Map([...adjacency.keys()].map(id => [id, null]));
    const parent = new Map([...adjacency.keys()].map(id => [id, null]));
    const queue = [start];
    distance.set(start, 0);
    let edgeChecks = 0;
    let maxQueueSize = 1;

    for (let head = 0; head < queue.length; head++) {
        const vertex = queue[head];
        for (const neighbor of adjacency.get(vertex)) {
            edgeChecks++;
            if (distance.get(neighbor) !== null) continue;
            // Mark on enqueue, not when the vertex is removed.
            distance.set(neighbor, distance.get(vertex) + 1);
            parent.set(neighbor, vertex);
            queue.push(neighbor);
            maxQueueSize = Math.max(maxQueueSize, queue.length - head - 1);
        }
    }

    const path = [];
    if (target !== null && distance.get(target) !== null) {
        for (let vertex = target; vertex !== null; vertex = parent.get(vertex)) {
            path.push(vertex);
        }
        path.reverse();
    }
    return { distance, parent, path, order: queue, edgeChecks, maxQueueSize };
}

Where BFS applies

A shortest path here means fewest edges. For unequal edge costs, ordinary BFS does not guarantee the minimum total cost. DFS explores depth first and is useful for other tasks, but its first path is not generally shortest by edge count.

The algorithm and graph layouts belong to the website. AlgiViz 0.8.0 supplies step wrappers, timeline sampling and custom scene objects. The graph, queue and accessible text all describe the same saved state; seeking does not rerun the traversal.

Related resources