这question对于检测有向图中的循环有一个很好的答案。不幸的是,制作它的 Map Reduce 版本似乎并不容易。
具体来说,我对用于从有向图中删除循环的 Map Reduce 算法感兴趣。
我已经使用广度优先搜索 (BFS) 算法进行了评估,但我看到的一个问题是可能会同时删除两个不同的边以切断一个循环。这种情况的影响是可以删除太多边。重要的是删除循环,同时尽量减少删除的边数。
有证明的方案优先!
谢谢。
最佳答案
您需要一个迭代 map reduce 来实现这个算法。参见 http://www.iterativemapreduce.org/对于以迭代 map reduce 为中心的 map-reduce 框架。或者 http://www.johnandcailin.com/blog/cailin/breadth-first-graph-search-using-iterative-map-reduce-algorithm有关如何使用 Hadoop 使用迭代 map reduce 通过图形进行广度优先搜索的工作示例。
关于algorithm - 用于从图中删除循环的 Map Reduce 算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6077481/