Depth-first search (DFS)

The same graph, a different traversal

Vertices A–H; undirected edges AB, AC, BD, BE, CE, CF, DG, EG and FG. H is isolated. Initially the start is A and the target is F. This is the BFS page's graph with the same neighbor order.

One branch before the next

DFS enters an undiscovered neighbor immediately. The current call is suspended until that neighbor and all its descendants finish. Only then does the call resume with its next neighbor. The layout of the graph is fixed: an edge's drawn length does not affect traversal.

The visualizer uses explicit call frames, not the JavaScript call stack. Each frame remembers a vertex and the number of its neighbors already inspected. The order matches recursive DFS with the same adjacency lists. Merely pushing all neighbors onto a stack can produce a different tree.

The stack is the current branch

The stack contains exactly the unfinished calls from the start to the current vertex. Its top is the current call; the other calls are suspended. A vertex is marked discovered before its frame is pushed, so it is entered at most once, even if the graph contains a cycle.

In each frame, the neighbor cursor advances before entering a child. Returning therefore resumes at the next neighbor rather than inspecting the same edge forever. Finished vertices remain discovered; revisiting them does not replace a parent. This page traverses only the component reachable from the start, not a forest of all components.

Enter, suspend, return

With the default input, discovery order is A, B, D, G, E, C, F. At F the stack is A, B, D, G, E, C, F. Every neighbor of F is already discovered; finish F and return to C, then E and the suspended calls above them. Return order is F, C, E, G, D, B, A.

The run discovers and finishes 7 vertices and inspects 18 adjacency entries: each of the 9 reachable undirected edges is read from both ends. The largest stack has 7 frames, including A at depth zero. Path reconstruction changes none of these counters. H stays undiscovered and is known to be unreachable only after the traversal ends.

Six edges in DFS, two in BFS

The parent chain to F gives A → B → D → G → E → C → F: 6 edges. Yet A → C → F uses only 2. DFS found a valid path first, not the shortest one. Depth 6 describes F's position in this DFS tree; it is not the graph's shortest-path distance.

Open the linked BFS example, keep the same graph and select target F. BFS reaches F at distance 2. Changing neighbor order can change the DFS tree, depth and path length; BFS still guarantees the minimum number of edges in an unweighted graph.

The demo always completes the reachable component and then follows parents from the target back to the start. During reconstruction the green partial path is reversed; the final result is start to target. Select H for an unreachable target, the start itself for a zero-edge path, or No target for traversal only.

Algorithm memory and playback history

With adjacency lists, traversal takes O(V + E) time including initialization of all vertex records. The explicit stack, vertex states, depths and parents take O(V) extra memory; graph storage is O(V + E). Restoring a path costs O(V) time and result memory in the worst case. Recursive DFS has the same asymptotic call-stack cost and can hit a language runtime's recursion limit.

This visualization additionally stores O(V + E) immutable snapshots, each with up to O(V) vertex and stack data. History therefore costs O(V(V + E)) memory plus the shared graph. Presets of at most eight vertices keep the scene readable; this is not an algorithmic DFS limit.

JavaScript implementation

The code accepts a valid simple undirected graph as a Map from IDs to ordered neighbor arrays, an existing start and an optional existing target. It preserves the input and matches the player's discovery order, return order, parents, depths and counters. The player additionally validates and copies the graph before emitting snapshots.

function depthFirstSearch(adjacency, start, target = null) {
    // A valid undirected graph: Map<vertexId, vertexId[]>.
    const depth = new Map([...adjacency.keys()].map(id => [id, null]));
    const parent = new Map([...adjacency.keys()].map(id => [id, null]));
    const order = [start], finishOrder = [];
    const stack = [{ vertex: start, nextNeighbor: 0 }];
    depth.set(start, 0);
    let edgeChecks = 0, maxStackSize = 1;

    while (stack.length) {
        const call = stack[stack.length - 1];
        const neighbors = adjacency.get(call.vertex);
        if (call.nextNeighbor === neighbors.length) {
            finishOrder.push(call.vertex);
            stack.pop();
            continue;
        }
        const neighbor = neighbors[call.nextNeighbor++];
        edgeChecks++;
        if (depth.get(neighbor) !== null) continue;
        parent.set(neighbor, call.vertex);
        depth.set(neighbor, depth.get(call.vertex) + 1);
        order.push(neighbor);
        stack.push({ vertex: neighbor, nextNeighbor: 0 });
        maxStackSize = Math.max(maxStackSize, stack.length);
    }

    const path = [];
    if (target !== null && depth.get(target) !== null) {
        for (let id = target; id !== null; id = parent.get(id)) path.push(id);
        path.reverse();
    }
    return { depth, parent, order, finishOrder, path, edgeChecks, maxStackSize };
}

When to choose DFS

DFS is useful for reachability, connected components and exploring branches. Cycle detection, topological sorting of a directed acyclic graph and strongly connected components require additional logic; this demo does not implement those tasks. A seen edge in this undirected graph may just lead back to the parent, so skip is not by itself a cycle detector.

For minimum edge count in an unweighted graph, use BFS. For minimum total weight, neither this DFS nor ordinary BFS handles arbitrary weights. The application defines the graph traversal; AlgiViz provides immutable step wrappers, timeline playback and custom scene objects.

Related resources