Graph Algorithms

Depth-First Search (DFS)

Master the depth-first approach to graph traversal

What is DFS?

Depth-First Search explores as far as possible along each branch before backtracking. It uses a stack (or recursion) to remember vertices to visit.

Key Features:

  • Goes deep before going wide
  • Uses stack or recursion
  • Memory efficient for deep graphs
  • Great for cycle detection

Complexity

Time: O(V + E)
Space: O(V)

Algorithm Steps

  1. Start at root vertex, mark as visited
  2. Explore first unvisited neighbor
  3. Recursively apply DFS to neighbor
  4. Backtrack when no unvisited neighbors
  5. Continue until all reachable vertices visited

Applications

Pathfinding

Maze solving, finding any path between vertices

Cycle Detection

Detecting cycles in directed and undirected graphs

Topological Sort

Ordering vertices in directed acyclic graphs

Connected Components

Finding strongly connected components

Code Implementation

DFS vs BFS

Use DFS when:

  • Memory is limited
  • Solution is deep in tree
  • Need to detect cycles
  • Topological sorting needed

Use BFS when:

  • Need shortest path
  • Solution is shallow
  • Level-order traversal needed
  • Exploring by levels

Ready to Understand DFS Visually?

Don't just read about it. Use our interactive graph visualizer to explore graph structures using Depth-First Search (DFS), see recursion and the call stack in action, and track node updates dynamically.

Launch DFS Visualizer →