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.
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.
Step 0: Start DFS with depth limit 4.
State at this checkpoint
{ "values": [ 0, "∞", "∞", "∞", "∞" ], "active": [], "kind": "graph", "visited": [], "chosen": [] }Step 2: Push node 2 at depth 1.
State at this checkpoint
{ "values": [ 0, "∞", 1, "∞", "∞" ], "active": [ 2 ], "kind": "graph", "visited": [ 0 ], "chosen": [] }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": [] }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": [] }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:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
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.
- Depth-first iterative-deepening
Richard E. Korf (1985). Research paper.