この質問は、有向グラフでサイクルを検出するための優れた答えを持っています。残念ながら、MapReduceバージョンを作成するのは簡単ではないようです。
具体的には、有向グラフからサイクルを削除するためのMapReduceアルゴリズムに興味があります。
幅優先探索（BFS）アルゴリズムを使用して評価しましたが、サイクルを遮断するために2つの異なるエッジが同時に削除される可能性があるという問題があります。このシナリオの影響は、削除できるエッジが多すぎることです。削除されるエッジの数を最小限に抑えながら、サイクルを削除することが重要です。
利用可能な証明を備えたソリューションが推奨されます！
ありがとう。
すべてのサイクルを削除したい場合は、ツリーになります。したがって、どのアルゴリズムを使用しても、|E|を削除します。-（n -1）エッジ。（もちろん正しかった場合）
ただし、問題は、エッジを削除するとグラフが切断されるかどうかです。このためには、エッジの順序付けを行う必要があります（辞書式順序としましょう）。次に、サイクル内の最大のエッジを常に削除する必要があります。[正しさの証明は非常に直接的なものだと思います。クラスカルアルゴリズムを使用するだけで、それらが同じになることがわかります。]
スパニングツリーアルゴリズムならどれでも問題を解決できます。最適化する対象（時間、メッセージの複雑さ、またはその他のパフォーマンスメトリック）に応じて、さまざまなアルゴリズムが見つかります。BFSは時間に最適です。c> 0のc（logn + m）メッセージ未満の問題を解決できるアルゴリズムはありません。
私がDAGに使用するのが好きなアルゴリズムはYO-YOと呼ばれています。アルゴリズムの説明は次の場所にあります：http ：//www.site.uottawa.ca/~flocchin/CSI4509/8-yoyo11_fr.pdf
このアルゴリズムを実装するには、反復マップリデュースが必要です。反復マップリデュースを中心とするmap-reduceフレームワークについては、http：//www.iterativemapreduce.org/を参照してください。または、 http：//www.johnandcailin.com/blog/cailin/breadth-first-graph-search-using-iterative-map-reduce-algorithmで、Hadoopを使用してグラフを幅優先探索する方法の実例を確認してください。反復マップreduceを使用します。