Depth First Search Visualization
Depth-First Search (DFS) explores a graph by going as deep as possible along each branch before backtracking. Think of it as navigating a maze by following one path to its end before trying another. It uses a stack (often via recursion) to keep track of its path, making it highly effective for cycle detection, pathfinding, and solving puzzles.
DFS (using stack)
stack = new Stack()
stack.push(src)
mark src as visited
while stack is not empty:
u = stack.pop()
for each neighbor v of u:
if v is not visited:
stack.push(v)
mark v as visited
DFS (recursive)
DFS(u):
mark u as visited
for each neighbor v of u:
if v is not visited:
DFS(v)
AI Summary
(5 credits)
Common Interview Questions
How is DFS used to detect cycles in Directed graphs vs Undirected graphs?
In directed graphs, a cycle exists if DFS encounters a node currently in the active recursion stack. In undirected graphs, a cycle exists if DFS encounters an already visited neighbor that is not the direct parent node.
Explain the Time and Space complexity of DFS for an adjacency list vs adjacency matrix representation.
Adjacency List: Time O(V + E), Space O(V) (visited array + recursion stack). Adjacency Matrix: Time O(V²), because scanning adjacent neighbors requires iterating over all V entries per vertex.
What happens if DFS is executed recursively on a graph with 100,000 linear vertices? How to mitigate?
Deep linear graph traversals using recursion cause Stack Overflow errors due to call stack limit bounds. Mitigation: Convert recursive DFS to Iterative DFS using an explicit stack data structure.
How does DFS assist in Topological Sorting?
Topological Sort pushes nodes to a stack upon completing their post-order DFS traversal. Popping the stack produces a valid topological order for a Directed Acyclic Graph (DAG).
💬 Discussion
Sign in to join the discussion
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0