Giraph，Graphchi或Pregel的广度优先实现

Question

是否有人知道在任何一种图形处理系统（Giraph，Pregel或Graphchi）中是否首先存在宽度（来自多个源）。

或者请告诉在任一系统上的一些更容易的实现。

Answer 1

在Giraph用户邮件列表中，可以找到几个讨论 - 我猜也是一个实现 - BFS实现。

我在过去做这种类型的搜索为Giraph，他们可在：

https://github.com/MarcoLotz/GiraphBFSTO

它们之间的区别在于，一个是目标导向，另外一个是结构导向。

虽然他们不是从多个起始顶点，可以很容易地修改代码来支持它:)

Answer 2

您正在寻找多种子广度优先搜索（BFS）算法。

对于Giraph，这仍然是一个未解决的问题，可以在这 feature request阅读。

对于Pregel，您不能指望找到任何开放算法，因为Pregel是Google的一个闭源图表系统。

我想最简单的就是使用Github中的代码，并分别为每个源执行它。优化算法的运行时复杂度的一个想法是对第一个种子顶点执行BFS，并将结果用于后续顶点种子（第一个BFS导致生成树，对于任何给定的种子顶点，可以很容易地将其转换为BFS顺序）。尽管如此，KISS建议简单地为k个种子顶点执行k次BFS，直到遇到性能问题（由于BFS的线性运行时复杂性而不太可能发生）。