¶ Graph Traversal (BFS, DFS)
¶ Competitive programming
/jpg/image.png)
¶ Introduction to Graph Traversal (BFS, DFS) in Competitive Programming
When you first step into the world of competitive programming, everything seems to revolve around arrays, strings, and a handful of greedy ideas. But as you explore deeper, you start seeing graphs everywhere — sometimes disguised as grids, sometimes wrapped inside relationships, sometimes presented as “roads and cities,” and sometimes hidden in problems that hardly mention the word “graph.”
Sooner or later, every serious competitive programmer realizes one thing: graphs aren’t just a topic — they’re an entire universe, and the key to navigating that universe begins with the two simplest, most powerful tools ever created in algorithmic thinking: Breadth-First Search (BFS) and Depth-First Search (DFS).
These two techniques form the backbone of nearly every advanced graph concept — from shortest paths to connected components, from cycle detection to bipartite checks, from tree algorithms to dynamic programming on graphs, from topological sorting to articulation points, bridges, SCCs, and even solving puzzles and grid problems.
And they are so elegantly simple that you can describe both in a few lines of logic, but so deep that you can keep discovering new patterns and applications for years.
This course begins with those two humble explorers — BFS and DFS — and from there, step by step, it grows into a complete mastery of graph concepts that competitive programming demands.
¶ Why BFS and DFS Matter So Much
Competitive programming problems often appear overwhelming at first glance: huge constraints, tricky relationships, and dozens of cases that seem impossible to track. But when you look closer, many of them simplify into something beautiful — nodes connected to each other by edges.
And once you model the problem as a graph, the next step is almost always one of two things:
- explore the graph layer by layer (BFS), or
- explore it by diving deep until you can’t go further (DFS)
You can think of BFS as the methodical person who visits neighbors in neat concentric circles, and DFS as the curious adventurer who keeps following paths until they reach dead ends. Despite these contrasting personalities, both strategies reveal different aspects of the graph’s structure.
In competitions, these two approaches help you answer questions like:
- Are two nodes connected?
- What’s the shortest path on an unweighted graph?
- Is this graph bipartite?
- Does a cycle exist?
- What’s the size of a connected component?
- Can you reach a certain state from another?
- How many steps does it take to escape a grid?
- Which nodes belong to the same region in a maze?
- How do you efficiently generate all reachable configurations?
These problems appear in contest after contest — div2, div3, ICPC regionals, CodeChef Cook-Offs, and everywhere else.
The coders who master BFS and DFS early on move through these challenges effortlessly. Those who don’t often try to reinvent the wheel under pressure, and the wheel almost always breaks.
¶ The Simplicity That Hides Incredible Power
BFS and DFS are simple enough to write in a minute or two, but powerful enough to unlock some of the hardest problems in graph theory. That’s the beauty of them.
BFS:
- uses a queue
- explores neighbors in layers
- naturally gives shortest paths in unweighted graphs
- helps detect reachability efficiently
- is perfect for grid-based shortest path problems
DFS:
- uses a stack (explicit or recursive)
- dives into depth until it can’t
- helps find cycles
- forms the basis of tree algorithms
- is crucial for classification of edges, topological sorting, articulation points, bridges, and SCCs
When you fully understand these tools, you begin to see problems differently. What once felt like a string of unrelated puzzles now feels like variations of the same idea — explore, classify, understand connectivity.
¶ Graphs Hide in More Places Than Most Beginners Realize
Part of what makes graph traversal so important is how often graphs appear in disguise. Consider these common competitive programming patterns:
- A grid where you can move up, down, left, right
- A series of transformations between numbers
- A state machine where each operation leads to new states
- A puzzle like sliding tiles or knight moves
- A social network with follow relationships
- A set of strings connected by allowed transitions
- A road map with constraints
- A tree representing dependencies or hierarchies
All of these are graphs — even if the problem never uses the word “node” or “edge.”
BFS and DFS give you the ability to uncover that hidden structure. And once you see the “graph inside the problem,” solutions fall into place with clarity.
¶ The Emotional Side of Mastering Graph Traversal
Many competitive programmers remember the exact moment graph traversal clicked for them. It’s usually not during an easy problem. It’s often during a contest where they’re stuck, panicked, and unsure how to proceed — until suddenly they realize:
“This entire thing is just a graph. If I run DFS from here or BFS from there, everything will fall into place.”
And it does.
With traversal mastered, your confidence grows. Problems that seemed intimidating before become opportunities. Questions that once felt complicated now feel manageable. With practice, even 2000-node or 200000-node graphs stop feeling scary.
You start trusting BFS and DFS like old companions who never let you down.
¶ Why Traversal Is the Gateway to All Graph Concepts
This course on BFS and DFS isn’t meant to stop at the basics — it’s meant to take you deep into graph theory. These two traversals are the foundation of everything else you will learn, including:
- detecting cycles in directed and undirected graphs
- checking bipartiteness
- connected components
- topological sorting
- shortest paths in unweighted graphs
- tree DFS and subtree queries
- Euler tours
- DP on trees and DAGs
- finding bridges and articulation points
- strongly connected components
- lowest common ancestor
- path decomposition techniques
- graph coloring
- flow networks (even they build on traversal ideas for residual graphs)
Every major graph topic branches from BFS and DFS. If you build a strong core here, every other graph concept becomes easier to learn.
¶ The Practical Strengths of BFS and DFS in Competitions
Let’s talk about what makes these traversals such practical tools in a high-pressure contest environment:
1. They’re incredibly fast.
With adjacency lists, BFS and DFS run in O(V + E). That’s perfect for large constraints.
2. They’re memory-light.
They fit comfortably within memory limits even for huge graphs.
3. They’re flexible.
From grids to trees to abstract states — they adapt effortlessly.
4. They’re predictable.
You know exactly how they behave. No hidden complexities.
5. They’re easy to code under pressure.
A few lines of implementation that you’ll write hundreds of times until it becomes second nature.
6. They scale with competitive programming constraints.
Even graphs with 200k nodes, millions of edges, or large dimensions work beautifully with BFS or DFS.
7. They build habits that translate into higher-level graph thinking.
Once you know traversal well, you naturally start thinking about parent tracking, depth, edge types, component IDs, or visited arrays — all essential for advanced topics.
¶ Understanding BFS: The Layered Explorer
BFS sees the world in layers. It starts from a node and spreads outward, touching all nodes at distance 1 first, then distance 2, and so on. That simple behavior is the reason BFS is the champion when it comes to shortest paths on unweighted graphs.
Competition problems like:
- minimum steps in a grid
- shortest path in a maze
- minimum operations to convert one number to another
- spreading problems (flood fill, multi-source BFS)
- problems with level structure (like bipartite check)
are almost always solved with BFS.
The characteristic “wave-like” manner in which BFS expands is legendary. It sees everything close to the source before venturing further. This is perfect when you need to guarantee optimal solutions in terms of steps, layers, or distances.
¶ Understanding DFS: The Depth-Seeking Investigator
DFS is the opposite personality — it doesn’t move in layers; it pushes deep into the unknown until it reaches a dead end. That small difference makes DFS capable of revealing structures that BFS cannot see as easily:
- discovering cycles
- classification of edges into tree/back/forward/cross
- generating depth ordering
- identifying articulation points
- identifying bridges
- performing topological tasks
- exploring subtrees
- solving tree queries
- performing Euler tours or subtree flattening
Each of these advanced topics might look complicated at first, but when you see them as natural consequences of DFS behavior, they become surprisingly intuitive.
DFS is your microscope into the graph. It shows you depth, hierarchy, discovery time, finishing time — the internal rhythm of the graph.
¶ The Mindset Needed for Becoming Good at Graph Traversal
To master BFS and DFS, you don’t need to memorize formulas or complex theory. You need intuition.
This intuition grows when you experiment:
- drawing graphs
- tracing how BFS layers expand
- visualizing DFS as a recursive journey
- noticing how trees form naturally
- watching how visited arrays prevent cycles
- exploring edge directions
- looking at flow through each edge
As you solve more problems, you begin to feel the graph. You sense where traversal should begin, where cycles might hide, which nodes to ignore, and where the answer lies.
This course is designed to nurture that intuition. Every concept will be explained from a problem-solver’s perspective, not as dry academic theory but as practical, competitive insight.
¶ The Beginning of a Meaningful Journey
Graph traversal is not a small topic. It is a mindset, a style of thinking, and the heart of graph algorithms. Once you grow comfortable with BFS and DFS, every graph problem — no matter how complex — begins to feel approachable.
And that’s exactly what this course aims to give you: not just knowledge, but confidence.
Confidence to approach any graph, break it down, explore it methodically, and pull out the solution hidden within. Confidence to rely on BFS and DFS as tools that will never let you down. Confidence to see problems from angles that most beginners miss.
By the time you complete all 100 articles in this course, graph traversal will feel like second nature. You’ll be able to code BFS or DFS almost without thinking, and you’ll be able to apply these traversals in sophisticated, creative, and deeply strategic ways.
This introduction is just the doorway. What lies ahead is one of the most enriching journeys in competitive programming — a journey that leads you from simple traversal to advanced graph mastery.
¶ Graph Traversal (BFS, DFS)
¶ Beginner Level (1-30)
1. Introduction to Graphs in Competitive Programming
2. Understanding Graph Representations: Adjacency Matrix
3. Understanding Graph Representations: Adjacency List
4. Introduction to Breadth-First Search (BFS)
5. Implementing BFS: Iterative Approach
6. Introduction to Depth-First Search (DFS)
7. Implementing DFS: Recursive Approach
8. Implementing DFS: Iterative Approach
9. Comparing BFS and DFS: Use Cases and Differences
10. BFS for Shortest Path in Unweighted Graphs
11. DFS for Connectivity in Undirected Graphs
12. BFS for Connectivity in Undirected Graphs
13. DFS for Cycle Detection in Undirected Graphs
14. BFS for Cycle Detection in Undirected Graphs
15. DFS for Cycle Detection in Directed Graphs
16. BFS for Cycle Detection in Directed Graphs
17. DFS for Topological Sorting in Directed Acyclic Graphs (DAGs)
18. BFS for Topological Sorting in Directed Acyclic Graphs (DAGs)
19. DFS for Finding Strongly Connected Components (SCCs)
20. BFS for Finding Strongly Connected Components (SCCs)
21. DFS for Finding Articulation Points in Graphs
22. BFS for Finding Articulation Points in Graphs
23. DFS for Finding Bridges in Graphs
24. BFS for Finding Bridges in Graphs
25. DFS for Bipartite Graph Checking
26. BFS for Bipartite Graph Checking
27. DFS for Tree Diameter Calculation
28. BFS for Tree Diameter Calculation
29. DFS for Subtree Size Calculation
30. Basic Problems on BFS and DFS in Competitive Programming
¶ Intermediate Level (31-60)
31. Optimizing BFS: Using Queues Efficiently
32. Optimizing DFS: Using Stacks Efficiently
33. BFS with Multiple Sources: Multi-Source BFS
34. DFS with Multiple Sources: Multi-Source DFS
35. BFS with Layers: Level-Order Traversal
36. DFS with Timestamps: Entry and Exit Times
37. BFS for Shortest Path in Weighted Graphs: 0-1 BFS
38. DFS for Eulerian Path and Circuit Detection
39. BFS for Eulerian Path and Circuit Detection
40. DFS for Hamiltonian Path and Circuit Detection
41. BFS for Hamiltonian Path and Circuit Detection
42. DFS for Finding Longest Path in DAGs
43. BFS for Finding Longest Path in DAGs
44. DFS for Finding Maximum Matching in Bipartite Graphs
45. BFS for Finding Maximum Matching in Bipartite Graphs
46. DFS for Finding Minimum Vertex Cover in Bipartite Graphs
47. BFS for Finding Minimum Vertex Cover in Bipartite Graphs
48. DFS for Finding Maximum Independent Set in Bipartite Graphs
49. BFS for Finding Maximum Independent Set in Bipartite Graphs
50. DFS for Finding Minimum Edge Cover in Bipartite Graphs
51. BFS for Finding Minimum Edge Cover in Bipartite Graphs
52. DFS for Finding Maximum Flow in Networks
53. BFS for Finding Maximum Flow in Networks
54. DFS for Finding Minimum Cut in Networks
55. BFS for Finding Minimum Cut in Networks
56. DFS for Finding Minimum Spanning Tree (MST)
57. BFS for Finding Minimum Spanning Tree (MST)
58. DFS for Finding All-Pairs Shortest Paths (APSP)
59. BFS for Finding All-Pairs Shortest Paths (APSP)
60. Intermediate Problems on BFS and DFS in Competitive Programming
¶ Advanced Level (61-90)
61. Advanced Techniques for BFS: Bidirectional BFS
62. Advanced Techniques for DFS: Iterative Deepening DFS (IDDFS)
63. Advanced Techniques for BFS: A* Search Algorithm
64. Advanced Techniques for DFS: Depth-Limited DFS
65. Advanced Techniques for BFS: Beam Search
66. Advanced Techniques for DFS: Backtracking with DFS
67. Advanced Techniques for BFS: Best-First Search
68. Advanced Techniques for DFS: Branch and Bound with DFS
69. Advanced Techniques for BFS: Dijkstra's Algorithm
70. Advanced Techniques for DFS: Bellman-Ford Algorithm
71. Advanced Techniques for BFS: Floyd-Warshall Algorithm
72. Advanced Techniques for DFS: Johnson's Algorithm
73. Advanced Techniques for BFS: Kruskal's Algorithm
74. Advanced Techniques for DFS: Prim's Algorithm
75. Advanced Techniques for BFS: Borůvka's Algorithm
76. Advanced Techniques for DFS: Tarjan's Algorithm
77. Advanced Techniques for BFS: Kosaraju's Algorithm
78. Advanced Techniques for DFS: Gabow's Algorithm
79. Advanced Techniques for BFS: Hopcroft-Karp Algorithm
80. Advanced Techniques for DFS: Dinic's Algorithm
81. Advanced Techniques for BFS: Edmonds-Karp Algorithm
82. Advanced Techniques for DFS: Push-Relabel Algorithm
83. Advanced Techniques for BFS: Hungarian Algorithm
84. Advanced Techniques for DFS: Kuhn's Algorithm
85. Advanced Techniques for BFS: Ford-Fulkerson Algorithm
86. Advanced Techniques for DFS: Capacity Scaling Algorithm
87. Advanced Techniques for BFS: Goldberg-Tarjan Algorithm
88. Advanced Techniques for DFS: Sleator-Tarjan Algorithm
89. Advanced Techniques for BFS: Link-Cut Trees
90. Advanced Problems on BFS and DFS in Competitive Programming
¶ Expert Level (91-100)
91. Designing Custom BFS Algorithms for Specific Applications
92. Designing Custom DFS Algorithms for Specific Applications
93. Designing Custom BFS Algorithms for Real-Time Systems
94. Designing Custom DFS Algorithms for Real-Time Systems
95. Designing Custom BFS Algorithms for Large-Scale Systems
96. Designing Custom DFS Algorithms for Large-Scale Systems
97. Designing Custom BFS Algorithms for Parallel Systems
98. Designing Custom DFS Algorithms for Parallel Systems
99. Open Problems in BFS and DFS in Competitive Programming
100. Future Directions in BFS and DFS Algorithms