codaBack to Academy
searching
Depth-First Search
Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack (or recursion) to keep track of vertices to visit next. DFS is foundational for detecting cycles, topological sorting, and finding connected components in graphs.
Use Cases
- •Detecting cycles in directed and undirected graphs
- •Topological sorting of dependency graphs
- •Solving maze and puzzle problems
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(V + E) | O(V + E) | O(V + E) |
| Space | O(V) | ||
Visualization
Implementation
Output
Click "Run Code" to see output...