All Patterns
🕸️
hardPattern #06
Graph BFS / DFS
Explore all reachable nodes in a graph, tracking visited state.
What is this pattern?
Graph traversal requires explicit visited tracking (unlike trees). BFS with a queue finds shortest paths in unweighted graphs. DFS with recursion or a stack is ideal for connectivity, cycle detection, and topological ordering.
When to use it
- Counting connected components or islands
- Shortest path in unweighted graph → BFS
- Topological sort / dependency ordering → DFS or BFS (Kahn's)
- Cycle detection in directed graph → DFS with color states
- Multi-source BFS when starting from multiple nodes simultaneously
Key Insight
Mark a cell/node visited BEFORE pushing it onto the queue (BFS), not after popping — otherwise you push duplicates and get TLE. For DFS cycle detection, use three states: unvisited (0), in-stack (1), done (2).
Pro Content
The Java template and practice problems for this pattern are part of the Pro plan. Upgrade to unlock all patterns, 500+ problems, and Aria code reviews.
From ₹3,999 for a year · one-time, no auto-renewal