Graph traversal looks simple in single-threaded code, but concurrency makes it tricky. BFS and DFS rely on shared state: a frontier (queue or stack), a visited set, and often a parent map for path reconstruction. With multiple threads, you must ensure each node is processed exactly once, avoid duplicate work, and keep contention low so parallelism actually helps.

Understanding how to parallelize graph traversal teaches you to reason about dependencies, synchronization, and load balancing in ways that apply far beyond graphs.

In this chapter, we'll parallelize both BFS and DFS, analyze why they behave so differently under parallelization, and build production-ready implementations using level-synchronous processing, frontier-based exploration, and work-stealing patterns.

Problem Statement