11.2 Depth-First Search (DFS) Algorithm

Depth-First Search (DFS) is a powerful graph traversal algorithm that explores branches deeply before backtracking. It's like exploring a maze, going as far as possible down each path before turning back. DFS uses a stack to keep track of vertices, making it perfect for solving maze-like problems and detecting cycles.

DFS can be implemented recursively or iteratively, with each approach having its own advantages. The algorithm's time complexity is O(V + E), where V is the number of vertices and E is the number of edges. DFS has numerous applications, from finding paths in graphs to topological sorting and solving puzzles.

Depth-First Search (DFS) Algorithm

DFS algorithm fundamentals

Top images from around the web for DFS algorithm fundamentals

• 

  CS 360: Lecture 17: Depth-First Search View original

  Is this image relevant?

• 

  Depth-first search - Wikipedia View original

  Is this image relevant?

• 

  Depth-first search - Wikipedia View original

  Is this image relevant?

• 

  CS 360: Lecture 17: Depth-First Search View original

  Is this image relevant?

• 

  Depth-first search - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for DFS algorithm fundamentals

• 

  CS 360: Lecture 17: Depth-First Search View original

  Is this image relevant?

• 

  Depth-first search - Wikipedia View original

  Is this image relevant?

• 

  Depth-first search - Wikipedia View original

  Is this image relevant?

• 

  CS 360: Lecture 17: Depth-First Search View original

  Is this image relevant?

• 

  Depth-first search - Wikipedia View original

  Is this image relevant?

1 of 3

• Graph traversal algorithm explores as far as possible along each branch before backtracking (maze, decision tree)
• Visits all vertices by exploring each vertex's neighbors before moving to next unvisited vertex (city map, social network)
• Traverses both directed (one-way roads) and undirected graphs (two-way paths)
• Explores graph by going deep before backtracking
• Uses stack data structure to track vertices to visit (stack of papers, browser history)
• Implemented using recursion or iteration with stack
• Detects cycles, explores all paths, solves maze-like problems (labyrinth, escape room)

Stack-based and recursive DFS implementation

• Recursive implementation:
  • Base case: If current vertex already visited, return
  • Mark current vertex as visited
  • Recursively visit all unvisited neighbors of current vertex (explore all rooms before returning)
• Iterative implementation using stack:
  • Create stack and push starting vertex (stack of locations to visit)
  • While stack not empty:
    1. Pop vertex from stack (remove top location)
    2. If popped vertex not visited:
    • Mark vertex as visited (check off location)
    • Push all unvisited neighbors onto stack (add adjacent unvisited locations)

Time and space complexity of DFS

• Time complexity:
  • Worst case: DFS visits all vertices and edges (explore every room and hallway)
  • Graph with $V$ vertices and $E$ edges, time complexity is $O(V + E)$
• Space complexity:
  • DFS requires space to store stack of vertices (locations to remember)
  • Worst case: stack may contain all vertices, space complexity $O(V)$
  • Recursive implementation uses stack space for function calls, up to $O(V)$ worst case (call stack)

Applications of DFS in graph problems

• Detecting cycles in graph:
  • During DFS, if edge leads to already visited vertex (except parent), cycle exists (circular path)
  • Detects cycles in directed (one-way streets) and undirected graphs (bidirectional paths)
• Exploring all paths:
  • Explores all possible paths from starting to target vertex (all routes from A to B)
  • Solves maze-like problems, finds path between vertices (escape room, treasure hunt)
• Topological sorting of directed acyclic graph

  DAG

  (task dependencies, course prerequisites)
• Finding strongly connected components in directed graph (social circles, web pages)
• Solving puzzles and games involving exploring all states or configurations (Rubik's cube, chess)