About Depth-First Search
DFS explores a graph by following each branch as far as possible before backtracking. It uses a stack (explicit or via recursion) and is useful for cycle detection, topological sorting, and finding connected components. DFS does NOT guarantee shortest paths.
Complexity Analysis
- Time Complexity
- O(V + E)
- Space Complexity
- O(V)
- Difficulty
- intermediate
Key Concepts
Stack-Based Exploration
DFS uses a LIFO stack. The last node pushed is the first explored, causing the algorithm to go deep before wide.
Backtracking
When DFS reaches a dead end (no unvisited neighbors), it backtracks by popping the stack until it finds a node with unexplored neighbors.
Does NOT Find Shortest Paths
DFS may find a path to the target, but it is not guaranteed to be the shortest. Use BFS for shortest paths in unweighted graphs.
Common Pitfalls
Not shortest path
DFS can find a valid path but not the shortest one. The path depends on traversal order.
Infinite loops without visited check
In graphs with cycles, DFS will loop forever without a visited set.