为什么BFS比DFS更适合并行化？

Question

我读过BFS算法比DFS更适合并行执行。我很难理解为什么这应该是正确的直觉。谁能解释？

谢谢

Answer 1

BFS 是一种传播边界的过程。“传播”意味着将所有未访问的相邻顶点推送到队列中，并且它们可以独立处理。

在DFS中，顶点是沿着A->B->C这样的方向一一访问的。访问 B 必须在访问 C 之前发生。这是一个顺序过程，不容易并行化。

但事实是 BFS 和 DFS 都很难并行化，因为所有处理节点都必须知道全局信息。访问全局变量始终需要节点之间的同步和通信。