数千から数百万のノードを持つグラフがあります。このようなグラフで考えられるすべてのサイクルを検出したいと考えています。
ハッシュテーブルを使用してエッジを保存します。( (ソース ノード,エッジの重み) -> (ターゲット ノード) )。
OCaml で効率的に実装するにはどうすればよいでしょうか?
Tarjan のアルゴリズムが最適なようです。
同じものを最も実装できるものは何ですか。
質問する
948 次
2 に答える
2
はい、強連結成分に対する Tarjan のアルゴリズムは優れたソリューションです。いわゆるパスベースの強力なコンポーネント アルゴリズムを使用することもできます。これは (慎重に行った場合) 同等の線形複雑度を持ちます。
合理的なデータ構造を選択すれば、それらは機能するはずです。プロトタイプの実装を実装してプロファイリングする前に、これ以上多くを語ることは困難です。
あなたのグラフ表現が何なのかわかりません: ハッシュ化されたキーは本当に(node,weight)カップルですか? では、特定のノードのすべての隣接ノードをどのように見つけるのでしょうか? 大規模なグラフ構造の場合、アクセス時間はもちろん、メモリ効率も最適化する必要があります。
于 2012-06-24T14:43:34.883 に答える
1
可能なすべてのサイクルを本当に見つけたい場合、最悪の場合、問題は少なくとも指数関数的に見えます。完全なグラフの場合、ノードの空でないサブセットごとに異なるサイクルが得られます (最後のノードから最初のノードへのリンクを含む)。さらに、すべてのサブセットのすべての巡回置換により、異なるサイクルが得られます。グラフのスパース性に応じて、問題は実際には扱いやすいものになる可能性があります。
于 2012-06-24T14:59:53.683 に答える