Graphs · question

Question 7 of 60

How does depth-first search explore a graph, step by step?

beginner

Re-explain

Depth-first search follows one path as far as it can before backing up. You pick a start, mark it visited, then move to an unvisited neighbor and repeat. When a vertex has no unvisited neighbors left, you backtrack to the previous one and try its other branches.

You can drive this with recursion, which uses the call stack, or with an explicit stack.

function dfs(v, seen) {
  seen.add(v);
  for (const n of neighbors(v))
    if (!seen.has(n)) dfs(n, seen); // recurse deeper
}

The visited set stops you from looping forever on cycles. DFS visits each vertex once and scans each edge once, so it runs in O(V + E) time, the same as BFS.

That depth-first order makes DFS natural for whole-graph questions, such as detecting cycles, finding connected components and producing a topological order. It suits problems about the graph's overall structure rather than the nearest distance.

Rewriting in plainer words…

This answer doesn't lend itself to a diagram - it reads best . No credits were charged.

Why there's no diagram: “”

The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓

The diagram below the answer is the concept . Jump to it ↓

Tailored explanation · switch back to · ·

What should the new diagram focus on?

Guided practice for Graphs One question at a time. Answer out loud, get graded, see what you missed.

See it - interactive diagram

How the call stack grows and shrinks during DFS

const graph = {

A: ['B', 'D'],

B: ['C'],

C: ['A'], // cycle to A

D: [],

};

function dfs(v, seen) {

seen.add(v);

for (const n of graph[v])

if (!seen.has(n))

dfs(n, seen);

}

dfs('A', new Set());

Call stackthe path from the start

dfs(A)

Verticesv is the current vertex

ABCD

seen

1step

The search starts at A. Its call goes on the stack, and A joins the seen set, the record of visited vertices.

1 / 9

The call stack is the path DFS is on. It grows on the way down one branch and shrinks as DFS backs up to a vertex that still has an unvisited neighbor.

Other questions have diagrams like this too. Sign in to ask for one where it's missing - it's free.

Create a free account

How well did you know this?

AI:

Saved in this browser - sign in to keep your review list.

How should your speech become text?

Listening… your words appear above as you speak - tap Stop when you're done.

Recording · cr - tap Stop & transcribe when you're done.

Transcribing with AI…

Voice:

Keep going - a few more words and AI can grade it.

Interview lens How interviewers actually use this question

Likely follow-ups

How would you write DFS with an explicit stack instead of recursion, and does the visit order change? Push the start; pop, skip if seen, else mark and push unseen neighbors. Push them in reverse to match the recursive order.
Why might recursive DFS crash on a large graph when an iterative version does not? Each call adds a stack frame, so a long path can overflow the call stack. An explicit stack lives on the heap and grows as memory allows.
How would you use DFS to detect a cycle in a directed graph? Track the vertices on the current path, not just visited ones. An edge back to a vertex still on the path means a cycle.
What happens if the graph is disconnected, and how do you make sure every vertex gets visited? One call only reaches the start's component. Loop over all vertices and start a new DFS from each one still unvisited.
Can DFS find the shortest path between two vertices in an unweighted graph? Not in general. DFS reaches a vertex by whichever path it tries first. BFS visits in order of distance, so its first arrival is shortest.

What you can say

Depth-first search follows one path as deep as it can go, and only backs up when it hits a dead end.
You mark the start as visited, move to an unvisited neighbor, and repeat from there.
When a vertex has no unvisited neighbors left, you backtrack to the previous one and try its other branches.
You can drive it with recursion, which uses the call stack, or with an explicit stack, and the visited set is what stops you looping forever on a cycle.
Each vertex is visited once and each edge is scanned once, so it runs in O(V + E), same as BFS.
That makes it a good fit for structure questions like cycles, components and topological order, but if I need the nearest distance I'd use BFS instead.

Weak answers to avoid

Forgets the visited set Without it, DFS loops forever on any cycle and explores shared vertices again. Say you mark each vertex when you enter it and skip any already seen.
Describes level-by-level order, which is BFS Visiting all neighbors before going deeper is BFS. DFS commits to one neighbor and goes as deep as it can before it tries the next.
Gives the wrong complexity, like O(V*E) With an adjacency list each vertex is visited once and each edge scanned once, so it is O(V + E). Only an adjacency matrix makes it O(V^2).
Claims DFS finds shortest paths DFS reaches a vertex by whichever path it tries first, and that path may be long. For the nearest distance in an unweighted graph, use BFS.

Interview lens

Likely follow-ups, what you can say, and the weak answers to avoid.

Want a quick review of the fundamentals? See the Graphs cheatsheet.

← Back to all Graphs questions

Pro · $10/mo

51 of 60 Graphs answers are in Pro.

Full answers, code samples, and AI explanations that go simpler or deeper. Cancel anytime.

Full answers + code
AI explanations, simpler or deeper
1,000 AI credits / month
Cancel anytime

Get Pro → See plans & pricing →