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

Question

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

谢谢

Answer 1

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

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

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

Answer 2

一般来说，有一些关于DFS和BFS的好信息：

• 广度优先搜索和深度优先搜索
• BFS和DFS之间的区别
• 广度优先搜索/深度优先搜索动画
• DFS 和 BFS 有什么区别？

特别是动画展示了BFS如何使用更多的并行概念。我认为BFS可以并行实现，但DFS没有并行解决方案。 DFS是一种线性算法，每个子节点调用一次。