Overview
Depth-First Search (DFS) explores a graph by going as deep as possible along one branch before backtracking to try another. It commits to a direction and follows it until it hits a dead end or the goal, then retreats to the last unexplored fork.
DFS is easy to implement with recursion or an explicit stack, but on a grid it wanders far from the start and offers no guarantee that the path it finds is the shortest.
How Depth-First Search works
- Push the start node onto a stack (or begin a recursive call) and mark it visited.
- Take the node on top of the stack and pick one unvisited neighbour.
- Descend into that neighbour, marking it visited and recording its parent.
- When a node has no unvisited neighbours, backtrack to the previous node and try another branch, until the goal is reached.
When to use it
- Maze generation and simply testing whether a path between two cells exists.
- Graph tasks like cycle detection, topological sort, and finding connected components.
- Avoid it when you need the shortest path — its route is often far longer than necessary.
Complexity analysis
Like BFS, DFS touches every vertex and edge once, so it runs in O(V + E) time. Its space is O(V) for the visited set and the recursion or explicit stack, whose depth can equal the longest path. DFS is not a shortest-path algorithm.
Frequently asked questions
Why doesn't DFS find the shortest path?
DFS commits to one branch and follows it to the end before considering alternatives, so it can reach the goal by a long, winding route while a shorter path sits unexplored. BFS or Dijkstra guarantee the shortest path.
When is DFS the better choice?
When you only need to know if a path exists, want to explore or generate a maze, or are solving structural graph problems like cycle detection where exploring deeply is exactly what you want.