Levels as parallel batches
Breadth first search visits a graph in levels: all nodes at distance one, then distance two, and so on. The set of nodes at the current level is called the frontier. Because every node in a frontier is processed using the same already known distance, the whole frontier can expand in parallel.
Expanding a frontier
For each level the parallel algorithm:
- Takes the current frontier of nodes.
- Visits all their neighbors at once across threads.
- Collects unvisited neighbors into the next frontier.
The key hazard is two threads discovering the same neighbor. An atomic test and set on the visited flag ensures each node is claimed exactly once, even under a race.
Direction switching
When the frontier is large, scanning every unvisited node and asking if a parent is in the frontier, called the bottom up approach, can be far cheaper than the usual top down expansion. High performance BFS switches direction based on frontier size.
Key idea
Parallel BFS processes one frontier at a time so all nodes in a level expand together, using atomic claims to avoid double visits and switching to bottom up traversal when the frontier grows large.