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.
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.
Step 0: Initial graph.
State at this checkpoint
{ "values": [ "∞", "∞", "∞", "∞", "∞" ], "active": [], "kind": "graph", "visited": [], "chosen": [] }Step 2: Visit node 1.
State at this checkpoint
{ "values": [ 1, 2, "∞", "∞", "∞" ], "active": [ 1 ], "kind": "graph", "visited": [ 0, 1 ], "chosen": [] }Step 3: Visit node 3.
State at this checkpoint
{ "values": [ 1, 2, "∞", 3, "∞" ], "active": [ 3 ], "kind": "graph", "visited": [ 0, 1, 3 ], "chosen": [] }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": [] }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:
- 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 | // 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.
- Depth-First Search and Linear Graph Algorithms
Robert Tarjan (1972). Research paper.