Depth-first search: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Explore each branch recursively before backtracking.

Follow a branch until it cannot expand, then backtrack; visited state prevents cycles from causing infinite exploration.

Open the 3D visualization

Depth-first search example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Depth-first search

Structural graph exploration and dependency analysis.

Choosing an alternative

BFS explores layers and finds shortest unweighted routes.

Worked example: input and state changes

Example input

0,1,4; 0,2,2; 2,1,1; 1,3,5; 2,3,8; 3,4,2

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Initial graph.

    State at this checkpoint
    {
      "values": [
        "∞",
        "∞",
        "∞",
        "∞",
        "∞"
      ],
      "active": [],
      "kind": "graph",
      "visited": [],
      "chosen": []
    }
  2. Step 2: Visit node 1.

    State at this checkpoint
    {
      "values": [
        1,
        2,
        "∞",
        "∞",
        "∞"
      ],
      "active": [
        1
      ],
      "kind": "graph",
      "visited": [
        0,
        1
      ],
      "chosen": []
    }
  3. Step 3: Visit node 3.

    State at this checkpoint
    {
      "values": [
        1,
        2,
        "∞",
        3,
        "∞"
      ],
      "active": [
        3
      ],
      "kind": "graph",
      "visited": [
        0,
        1,
        3
      ],
      "chosen": []
    }
  4. Step 5: Visit node 2.

    State at this checkpoint
    {
      "values": [
        1,
        2,
        5,
        3,
        4
      ],
      "active": [
        2
      ],
      "kind": "graph",
      "visited": [
        0,
        1,
        3,
        4,
        2
      ],
      "chosen": []
    }
  5. Step 6: Traversal order: 0 → 1 → 3 → 4 → 2. Unreachable nodes stay unvisited.

    State at this checkpoint
    {
      "values": [
        1,
        2,
        5,
        3,
        4
      ],
      "active": [],
      "kind": "graph",
      "visited": [
        0,
        1,
        3,
        4,
        2
      ],
      "chosen": []
    }

Expected final state

Traversal order: 0 → 1 → 3 → 4 → 2. Unreachable nodes stay unvisited.

Complexity and input bounds

Family: Graphs. Time complexity: O(V + E).

Implementation detail: With adjacency lists DFS is O(V + E). The edge-array reference scans E edges per visited vertex and can retain pending duplicate vertices, so allow O(V + VE) time and O(V + E) stack/state.

Space complexity: O(V + E) visited and pending-stack storage in the iterative reference.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

Directed edges as source,target,weight; separated by semicolons. Nodes 0–7, positive weights 1–99. Start node is 0.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

Visit order depends on neighbor order and is not a shortest-path certificate.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// Directed edge arrays from, to, weight; nodes 0..vertices-1; source 0. Up to 8 vertices, 16 edges. Allocate output with at least 256 integers. Writes depth-first traversal order and returns its length. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(from, to, weight, edges, vertices, output) {
    let seen = Array(256).fill(0); let stack = Array(256).fill(0);
    let top = 0; let count = 0; stack[top++] = 0;
    while (top > 0) {
        let u = stack[--top];
        if (seen[u] == 1) { continue; }
        seen[u] = 1; output[count++] = u;
        for (let i = edges - 1; i >= 0; i--) {
            if (from[i] == u && seen[to[i]] == 0) { stack[top++] = to[i]; }
        }
    }
    return count;
}

Source

Tarjan presents foundational DFS-based graph algorithms; this is not a claim that depth-first traversal was first invented in that paper.