Skip to content

DepthFirstSearch

Jump to bottom
krishanthan4 edited this page Dec 16, 2025 · 1 revision

Depth First Search (DFS)

Problem Description

Implement depth-first search for graph traversal. DFS explores as far as possible along each branch before backtracking.

What is DFS?

DFS is a graph traversal algorithm that explores a graph by going as deep as possible down each path before backtracking.

Characteristics

  • Time Complexity: O(V + E) where V is vertices and E is edges
  • Space Complexity: O(V) for the visited set and stack/recursion
  • Traversal Strategy: Go deep first, then backtrack
  • Implementation: Stack (iterative) or Recursion

How It Works

  1. Start at a given node
  2. Mark it as visited
  3. Visit one of its unvisited neighbors
  4. Repeat step 3 recursively/iteratively
  5. Backtrack when no unvisited neighbors remain

Your Task

Implement the following methods in Depth_First_Search.java:

  1. dfs(Map<Integer, List<Integer>> graph, int start) - Iterative DFS using a stack
  2. dfsRecursive(Map<Integer, List<Integer>> graph, int start) - Recursive DFS
  3. dfsRecursiveHelper(...) - Helper method for recursion

Graph Representation

The graph is represented as an adjacency list:

Map<Integer, List<Integer>>
Key: vertex
Value: list of adjacent vertices

Test Cases to Consider

  • Single node graph
  • Disconnected graph (some nodes unreachable from start)
  • Cyclic graph
  • Linear graph (like a linked list)
  • Complete graph (all nodes connected)

Hints

  • Use a Set to track visited nodes
  • For iterative: Use a Stack (LIFO)
  • For recursive: Use the call stack naturally
  • Process a node when you visit it, not when you pop it

Applications

  • Finding connected components
  • Topological sorting
  • Detecting cycles
  • Maze solving
  • Puzzle solving

Follow-up Questions

  1. How would you detect a cycle using DFS?
  2. How would you find all paths between two nodes?
  3. What's the difference between DFS and BFS in terms of when you'd use each?
  4. How would you implement DFS for a tree vs. a graph?

Common Pitfalls

  • Forgetting to mark nodes as visited (causes infinite loops)
  • Not handling disconnected graphs
  • Stack overflow in recursive implementation for very deep graphs

Related Algorithms

  • Breadth First Search (BFS)
  • Topological Sort
  • Strongly Connected Components (Tarjan's/Kosaraju's)

Clone this wiki locally