aloalgo.comGraph Traversal (DFS, BFS)
Graph traversal means visiting all vertices in a graph. The two main approaches are Depth-First Search (DFS) and Breadth-First Search (BFS).Depth-First Search (DFS)
Explore as deep as possible before backtracking. Uses a stack (explicitly or via recursion).Recursive DFS
Iterative DFS
Breadth-First Search (BFS)
Explore level by level. Uses a queue. Guarantees shortest path in unweighted graphs.BFS Template
BFS Shortest Path
DFS vs BFS
| Aspect | DFS | BFS |
|---|---|---|
| Data Structure | Stack / Recursion | Queue |
| Order | Deep then backtrack | Level by level |
| Shortest Path | No | Yes (unweighted) |
| Space | O(height) | O(width) |
Grid Traversal
DFS and BFS work the same on grids. Each cell is a vertex, adjacent cells are neighbors.When to Use Which
Use DFS when:- Finding any path (not necessarily shortest)
- Detecting cycles
- Topological sorting
- Exhaustive search (backtracking)
- Finding shortest path in unweighted graph
- Level-order processing
- Finding nearest node with property X
Complexity
Both DFS and BFS have the same complexity:- Time: O(V + E) where V = vertices, E = edges
- Space: O(V) for the visited set
Was this helpful?
Company
Practice
Learn
© 2026 aloalgo.com. All rights reserved.