Why is BFS better suited to parallelization than DFS?

Question

I've read that the BFS algorithm is better suited to parallel implementation than DFS. I'm having trouble grasping the intuition of why this should be true. Can anyone explain?

Thanks

Answer 1

BFS is a procedure of propagating frontiers. 'Propagate' means push all their unvisited adjacent vertices into a queue, and they can be processing independently.

in DFS, the vertices are visited one by one along a direction such as A->B->C. Visiting B must occur before visiting C. It's a sequential procedure which can not be parallelized easily.

But the truth is both BFS and DFS are hard to parallelize because all the processing nodes have to know the global information. Accessing global variables always requires synchronizations and communications between nodes.