最小スパニングツリーグラフについて

-4

PrimeとKruskal's algorithmsよりもアルゴリズムが優れています（より最適で高速です）。最小スパニングツリーグラフについて

出典

2017-08-09 Saeed VA

https://en.wikipedia.org/wiki/Minimum_spanning_tree#Faster_algorithms – DAle

PrimeのアルゴリズムとKruskalのアルゴリズムは、うまく実装されていれば本当に速く動作します。データセットのケースに最適なデータ構造を使用してください。実際には、ほとんどの場合、より高速なアルゴリズムは必要ありません。

アルゴリズムの並列実装が必要な場合は、Borůvka's algorithmを使用してください。

理論が最速のアルゴリズムが必要な場合は、Decision treesアルゴリズムをチェックします。

リニアalgorithmの特別なケースがあります。

出典

2017-08-09 12:57:34 knst

非常に大きな入力を持つ複雑なネットワークに最適なのはどれですか？ –

V頂点Eエッジを持つグラフの場合、KruskalのアルゴリズムはO（E log V）時間で実行され、PrimのアルゴリズムはO（E + V log V）の償却時間で実行されます。だから、E、Vを数え、それが良いと決める。プリムを使用するよりも多くの頂点があるが、あまりエッジがない場合。より多くの頂点がある場合は、Kruskalを使用します。定数は非常に重要であり、実装が悪いと非常に遅くなる可能性があるため、このアルゴリズムの優れた実装を使用してください。入力が非常に大きく、12コアのXeon（またはインスタンスが多いクラスタ）を使用している場合は、Boruvkaのアルゴリズムを使用してみてください。 – knst

最小スパニングツリーグラフについて

答えて

関連する問題