Depth-limited DFS: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Search from node 0 to the highest numbered node. Ignore weights; revisit a node if a shallower path is discovered.

Refuse DFS expansions beyond a chosen edge depth; allow a shallower revisit when it restores useful remaining depth.

Open the 3D visualization

Depth-limited DFS 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-limited DFS

Searching under an explicit depth budget.

Choosing an alternative

Iterative deepening increases the limit across repeated searches.

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 | 4

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: Start DFS with depth limit 4.

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

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

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

    State at this checkpoint
    {
      "values": [
        0,
        1,
        1,
        2,
        3
      ],
      "active": [
        4
      ],
      "kind": "graph",
      "visited": [
        0,
        1,
        3
      ],
      "chosen": []
    }
  5. Step 9: Path length = 3; path 0 → 1 → 3 → 4.

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

Expected final state

Path length = 3; path 0 → 1 → 3 → 4.

Complexity and input bounds

Family: Graphs. Time complexity: O(VE) with depth pruning.

Space complexity: O(V) bounded graph-search state.

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. Append | depth limit (0–7).

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

Failure at one limit does not prove unreachability; depth counts edges, not visited nodes.

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
15
16
17
18
19
20
21
22
23
24
// Directed graph with 1–8 vertices and up to 16 edges; weights ignored. Source 0, goal vertices-1. limit is 0–7. Revisit nodes on shallower paths. Writes path indices and returns moves or -1. 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, limit) {
    let best = Array(256).fill(0); let parent = Array(256).fill(0); let stack = Array(256).fill(0); let depth = Array(256).fill(0);
    for (let bound = limit; bound <= limit; bound++) {
        for (let v = 0; v < vertices; v++) { best[v] = 1000000; parent[v] = -1; }
        best[0] = 0; let top = 1; stack[0] = 0; depth[0] = 0;
        while (top > 0) {
            top--; let u = stack[top]; let d = depth[top];
            if (d != best[u]) { continue; }
            if (u == vertices - 1) {
                let path = Array(256).fill(0); let count = 0;
                for (let v = u; v >= 0; v = parent[v]) { path[count++] = v; }
                for (let i = 0; i < count; i++) { output[i] = path[count - 1 - i]; }
                return count - 1;
            }
            if (d == bound) { continue; }
            for (let i = edges - 1; i >= 0; i--) {
                let v = to[i];
                if (from[i] == u && d + 1 < best[v]) { best[v] = d + 1; parent[v] = u; stack[top] = v; depth[top++] = d + 1; }
            }
        }
    }
    return -1;
}

Source

Korf studies iterative deepening and its depth-limited searches. The playground adds bounded graph depth-pruning rules.