MST用線形時間アルゴリズム

Question

重みの数が少ないとき（つまり、2つの異なる重みしか持てない）、線形時間アルゴリズムを使用してグラフのMSTを見つけることができるかどうか疑問に思っていました。

Googleでは、PrimのKruskalのBoruvka以外のものは見つかりませんでしたが、この特殊なケースで実行時間を短縮するプロパティはありません。私はBFS（MSTがウェイトが一様であることがわかる）の修正が必要な線形時間にすることを推測しています。

Answer 1

プリムのO(V lg V)ランタイムのlg V要因の原因は、次の候補エッジを見つけるために使用されるヒープです。限られた数の重みがある場合、一定時間内に挿入と削除を行う優先キューを設計することが可能であると確信しています。これは、PrimをO(V)に減らします。

優先度キューについては、可能なすべての重みをインデックスで囲む配列で十分だと思います。各要素は、その重みを持つ要素を含むリンクリストを指しています。次の要素を取り出すリスト（「最低」の空でないもの）を求めるには、まだd（別個の重みの数）の因子がありますが、dが定数の場合は、大丈夫です。

Answer 2

Aasmund Eldhusetの答えを精緻化する：MSTの重みが0,1,2,3、...、U-1の範囲の数値に限定されている場合、既存のアルゴリズムの多くを実行することができますUが定数であれば（ほぼ）線形時間である。

たとえば、Kruskalのアルゴリズムを考えてみましょう。 Kruskalのアルゴリズムの最初のステップは、ウェイトを昇順にソートすることです。基数ソートを使用する場合はO（m + U）、基数ソートを使用する場合はO（m lg U）の時間でこれを行うことができます。 Uが定数である場合、これらのソートステップの両方は線形時間をとる。したがって、この場合、Kruskalのアルゴリズムを実行するための実行時間はO（m α（m））になります。α（m）は逆Ackermann関数です。これは、制限要因が分離集合フォレストを維持するランタイムになるためです。

また、プリムのアルゴリズムを見てください。ノードまでの候補距離の優先キューを維持する必要があります。すべての辺が範囲[0、U]にあることがわかっている場合は、可能な優先度ごとに1つのUバケットの配列を格納するだけで、これを非常に単純な方法で行うことができます。プライオリティキューに挿入すると、アイテムを正しいバケットにダンプするだけで済みます。要素を削除して下部のバケットに移動することによって、減少キーを実行できます。バケットをスキャンしてfind-minを実行することができます。これにより、アルゴリズムランタイムがO（m + nU）になります。これは、Uが定数の場合は線形です。