Graph BFS / DFS

O(V+E)

Walk a graph from a source node, tracking a visited set so cycles don't loop you forever: BFS spreads out ring by ring for fewest-edges distance, DFS dives down one path for reachability.

Signals

shortest path in an unweighted graphfewest steps/hops between nodescan node X reach node Yexplore ring by ring / layer by layergraph given as adjacency list, may contain cycles

Template

function bfsDistances(adj, source) {
    const dist = { [source]: 0 };
    const queue = [source];
    while (queue.length) {
        const node = queue.shift();
        for (const next of adj[node] || []) {
            if (!(next in dist)) {
                dist[next] = dist[node] + 1;
                queue.push(next);
            }
        }
    }
    return dist;
}

Looks similar, isn't

Tree traversal: A tree has no cycles and each node has one parent, so a plain visit never needs a visited set. A graph can loop back on itself, so BFS/DFS must track visited nodes or it revisits them forever.

V, E up to ~1e5, unweighted graph, need reachability or fewest-edge distance -> O(V+E): every node and edge is visited once.

Learn this pattern