algorithm - Edge の重みの範囲がわかっている場合の Prim のアルゴリズム

Question

グラフ内のすべての辺の重みが 1 から |V| の範囲の整数であるとします。Prim のアルゴリズムをどれくらい速く実行できますか? ある定数 W に対してエッジの重みが 1 から W の範囲の整数である場合はどうなるでしょうか?

プリムのアルゴリズムは最小ヒープの実装に基づいているため、エッジの重みに関する知識は手順の高速化には役立ちません。これは正しいです？

Answer 1

この制約により、O(V)/O(W)それぞれスペースを使用するヒープを実装できますが、 O(1)insert 操作とO(1)extract-min 操作があります。O(1)実際には、Prim のアルゴリズムに必要なすべての操作を得ることができます。ヒープの時間の複雑さはメイン アルゴリズムの複雑さに影響するため、デフォルトの汎用実装よりも優れたものになる可能性があります。