Edit the tree or graph, pick a start node, then press Play. DFS follows one path as deep as it can, then backs up to try the next branch, using a stack to remember the way back.
Not found yetOn the stackExploring nowFinishedColor shows the depth, the number of steps down from the start.
Step 0 of 0
Traversal order
Each node appears here the moment DFS first reaches it. The rows below group nodes by depth, the number of steps down the path from the start.
Adjacency table
Every node and the nodes it connects to. It updates as you edit the graph. Click a row to select that node.
Node
Connected to
Depth
Status
The algorithm
The highlighted lines are the ones running in the current step.
Depth-First Search (DFS) is a graph and tree traversal algorithm that follows one path as deep as it can before backing up — going down a branch until it hits a dead end, then returning to the most recent node that still has unexplored neighbours. It uses a stack (last in, first out) to keep track of the way back, either an explicit one or the call stack of a recursive function.
O(V + E)
Time complexity — every vertex and edge is visited once
O(V)
Space complexity — for the stack and the visited set, up to the length of the longest path
Stack
Core data structure — LIFO ordering sends the search deeper first
Backtracking
Dead ends pop off the stack and return to the last unfinished branch
How it works
Pick a start node, mark it as visited, and push it onto the stack.
Look at the node on top of the stack, without removing it, and check its neighbours one at a time.
If a neighbour has not been visited yet, mark it as visited and push it. DFS is now one step deeper.
If every neighbour has already been visited, pop the node off the stack. This is backtracking: DFS returns to the node underneath and carries on with its remaining neighbours.
Repeat steps 2–4 until the stack is empty. Every node reachable from the start has been visited by then.
Key properties
Depth first: DFS keeps going down one branch until it cannot go any further, and only then tries the next branch.
Completeness: DFS reaches every node that is connected to the start in a finite graph.
Not the shortest path: the first route DFS finds to a node can be long and winding, so the depth shown here is not the fewest possible steps.
Neighbour order matters: checking neighbours in a different order gives a different, equally valid DFS order. Here they are checked in the order the nodes were created (A, B, C…).
Stack vs. queue: swapping the stack for a queue turns the same basic algorithm into Breadth-First Search (BFS), which explores level by level instead.
Worked example
Same graph as the default example in the Visualizer. Start at A; neighbours are taken in alphabetical order.
Default tree. A is the start node.
Visit A. Stack: [A].
Go deeper to B (first neighbour of A), then to E. Stack: [A, B, E].
E is a dead end: pop it and back up to B.
From B, go to F, then I. Stack: [A, B, F, I].
I is a dead end: pop I, F, B (nothing left in each). Back at A.
From A, go to C, then G. Dead end: pop G, C.
From A, go to D, then H. Dead end: pop H, D, A. The stack is empty, so DFS stops.
Visit order: A → B → E → F → I → C → G → D → H. Each branch is followed to its end before backing up.
Where DFS is used
Cycle detection
Spotting loops in a graph, such as circular dependencies between tasks or modules.
Topological sorting
Ordering tasks so each one comes after everything it depends on, like build steps or course prerequisites.
Maze solving
Following a corridor to its end and backing up at dead ends until the exit is found.
Connected components
Finding every separate group of linked nodes, like clusters in a network or islands in a grid.
Backtracking puzzles
Trying one choice at a time and undoing it when it fails, as in Sudoku and N-Queens.
File systems
Walking a folder and all of its sub-folders before moving on to the next folder.
Switch back to the Visualizer tab to build a graph and watch each of these steps happen node by node.