我读过一些资料，称BFS算法比DFS更适合并行实现。我有点难以理解这个结论的内涵。有人能够解释一下吗？
谢谢。
谢谢。
为什么BFS比DFS更适合并行化？ 注：BFS和DFS均为常见的搜索算法，其在计算机科学中被广泛应用。
6
- azphare
2个回答
3
BFS是一种传播边界的过程。“传播”意味着将所有未访问的相邻顶点推入队列中，并且它们可以被独立处理。
在DFS中，顶点沿着方向逐个访问，例如A->B->C。访问B必须发生在访问C之前。这是一个顺序过程，很难并行化。
但实际上，BFS和DFS都很难并行化，因为所有处理节点都必须知道全局信息。访问全局变量总是需要节点之间的同步和通信。
在DFS中，顶点沿着方向逐个访问，例如A->B->C。访问B必须发生在访问C之前。这是一个顺序过程，很难并行化。
但实际上，BFS和DFS都很难并行化，因为所有处理节点都必须知道全局信息。访问全局变量总是需要节点之间的同步和通信。
- onesuper
2
除非空间有分支，否则这不是一次搜索。使用正确的语言/工具很容易在发现分支时进行分叉，从而进行并行DFS搜索。通信可以限制为向树“上传递”信息，并且可以在数据上不使用锁定来完成；只需保持一个答案数组，每个分支一个，并让父级等待子级搜索完成（这正是DFS中发生的事情）。几乎所有高性能的国际象棋程序都这样做。 - Ira Baxter
...平均分支因子为2，深度为10的DFS空间有2^10个分支...这是巨大的潜在并行性。即使平均分支因子低于2，这样的搜索也会产生有趣的并行性。 - Ira Baxter
0
关于DFS和BFS，有一些很好的信息：
特别是动画展示了BFS如何使用更多的并行概念。我认为BFS可以被实现为并行算法，但是DFS没有并行解决方案。 DFS是一个线性算法，每个子节点只会被调用一次。
- pearcoding
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接