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
- Start at root vertex, mark as visited
- Explore first unvisited neighbor
- Recursively apply DFS to neighbor
- Backtrack when no unvisited neighbors
- 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
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