Course contentsShow
← Computer Science
Lesson 716 of 2,87217. Graph Traversal AlgorithmsFree lesson

Path Finding with DFS

Use DFS to find paths between vertices by tracking parent pointers during traversal.

Path Finding with DFS

You'll learn how to use DFS to find and reconstruct paths between two vertices by tracking parent pointers during traversal.

The Core Idea

When DFS explores a graph, it naturally follows paths from the start vertex to deeper vertices. By recording where you came from at each step—storing a parent pointer for each visited vertex—you can later walk backwards from any destination to reconstruct the complete path.

Think of it like exploring a cave system with a ball of string. As you venture deeper (DFS), you leave breadcrumbs (parent pointers) showing which tunnel you came through. When you reach your goal, you can follow the breadcrumbs backward to find the route you took.

How It Works

  1. Track parents during traversal: When visiting a neighbor v from vertex u, record that u is the parent of v
  2. Stop when destination is found: DFS continues until it reaches the target vertex
  3. Reconstruct the path: Walk backwards from destination to source using parent pointers, then reverse to get the forward path

Important: DFS does not guarantee the shortest path—it finds a path, whichever one the traversal discovers first based on exploration order.

When to Use This

  • Finding any valid path (not necessarily shortest)
  • Maze solving where any exit route works
  • Puzzles where you need to track how you reached a state
  • When combined with backtracking for exhaustive path enumeration

Key Takeaway: By maintaining parent pointers during DFS traversal, you can reconstruct the path from source to any reachable vertex by walking backwards through the parent chain—though the path found depends on traversal order and isn't guaranteed to be shortest.