Depth-First Search (DFS)

Question 1

What data structure is implicitly used in recursive DFS?

Accepted Answer

Stack — Recursion uses the Call Stack to track function calls, thus DFS behaves like a Stack-based traversal.

Question 2

DFS explores a graph by…

Accepted Answer

Going as deep as possible along a branch — Depth-First Search follows one path to its end, then backtracks to explore alternatives — naturally expressed with recursion or an explicit stack.

Question 3

What structure underlies DFS?

Accepted Answer

A stack — LIFO order produces the dive-then-backtrack behavior; recursion uses the call stack implicitly.

Question 4

What is DFS's time complexity on an adjacency list?

Accepted Answer

O(V + E) — Each vertex and edge is processed once, so DFS is O(V + E) with an adjacency list.

Question 5

DFS is the foundation of which ordering of a DAG?

Accepted Answer

A topological sort ordering — Pushing vertices onto a stack as their DFS finishes (postorder) and reversing yields a valid topological order of a DAG.

Question 6

To detect a cycle in a DIRECTED graph with DFS, you track…

Accepted Answer

Nodes currently sitting on the recursion stack — A back edge to a node still on the recursion stack (in-progress) signals a directed cycle; a plain visited set isn't enough.

Question 7

In an UNDIRECTED graph, DFS detects a cycle when it finds a visited neighbor that…

Accepted Answer

Is not the current node's immediate parent — Reaching an already-visited node other than where you came from means there's an alternate path forming a cycle.

Question 8

DFS finds STRONGLY connected components using algorithms like…

Accepted Answer

Tarjan's or Kosaraju's algorithm — Tarjan's uses low-link values in one DFS; Kosaraju's uses DFS on the graph then its transpose — both O(V+E) for SCCs.

Question 9

What is the space complexity of recursive DFS?

Accepted Answer

O(V) worst case for the full recursion stack — A long path makes the recursion as deep as O(V); very deep graphs can overflow the call stack, motivating an explicit stack.

Question 10

Articulation points and bridges (critical nodes/edges) are found via…

Accepted Answer

Via node discovery times and low-link ancestor values — Tracking each node's DFS discovery time and the lowest reachable ancestor (low-link) identifies cut vertices and bridges in O(V+E).

Go deep first

Test your knowledge

What data structure is implicitly used in recursive DFS?

Write the code

Number of Islands

Example Cases

When to reach for this

Interview Questions

References & Further Reading

Related topics

Love this visualization?