Go as deep as you can down one path, then back up and try the next. Recursion or a stack keeps track of where you came from.
Used for
start at 7
DFS just reached the dead end 5. What does it do next?
Not quite. DFS backs up to the nearest node that still has an unvisited child. That is 9, whose other child is 2.
Step 1 of 6
Goal: visit every node. Depth-first search picks a direction and goes as deep as it can before turning back, like exploring a maze by always taking the next corridor.
Step 2 of 6
From the root, 7, go down the left side to 9.
Step 3 of 6
Keep going down to 5. It has no children: a dead end.
Step 4 of 6
Back up to 9 and try its other child, 2. Another dead end.
Step 5 of 6
Back up to the root and take the last branch: 11. Recursion remembers where to return to (a stack does the same). On a graph also keep a visited list so you never loop. This is depth-first search.
Step 6 of 6
Your turn.
Articulation Points (or Cut Vertices)Bridges in GraphStrongly Connected ComponentEulerian PathDepth-First Search (graph)Depth-First Search (tree)Graph
function dfs(node, seen = new Set()) { if (!node || seen.has(node)) return; seen.add(node); for (const next of node.neighbors) dfs(next, seen); return seen;}