エッジ長が制約されている場合の最小スパニングツリーの高速アルゴリズム？

Question

0からU-1の範囲にある負でない整数の辺の長さを持つ有向グラフがあるとします。このグラフの最小スパニングツリーを計算する最も速いアルゴリズムは何ですか？ KruskalのアルゴリズムO（m log n））やPrimのアルゴリズム（O（m + n log n））などの既存の最小スパニングツリーアルゴリズムを引き続き使用できます。しかし、Uが小さい場合には、これをもっと良くすることが可能であると思います。

エッジの長さがある範囲に制限されているという事実を利用できる、従来のMSTアルゴリズムと競合するアルゴリズムはありますか？

ありがとうございます！

Answer 1

Fredman-Willardは、単位コストRAMの整数辺長のO（m + n）アルゴリズムを示しました。 ChazelleはO（mα（m、n）+ n）アルゴリズムを与えました。これは、長さの制限がない限り（長さは比較のみをサポートする不透明なデータ型です） （アルファは逆アッカーマン関数である）、Karger-Klein-Tarjanはランダム化O（m + n）アルゴリズムを与えた。

私はダレンの考えがO（m + n + U）時間アルゴリズムにつながるとは思わない。 Jarnik（ "Prim"）はプライオリティキューを単調に使用しないため、バケットは複数回スキャンされる可能性があります。 Kruskalは、分離したデータ構造を必要とします。これはO（m + n）にはできません。

Answer 2

整数のエッジウェイトを使用すると、バケッティングを使用して、最悪のケースであるO(1)の複雑さを持つ優先度キューを実現できますが、追加のO(U)のスペースが複雑になります。

上記のMSTアルゴリズムでは、比較ベースの優先度キューをこの整数構造体で置き換えることができるため、複雑さの要件の中でO(log(n))の依存性を取り除くことができます。 O(n + m)のスタイルで全体的に複雑になると思います。

基本的には、セットアップの各リストはそのバケットに関連付けられている（整数！）コストでインデックス化された圧縮されたリンクされたリストの集合、この構造は、各項目ができるという事実に基づいています

struct bucket_list 
{ 
    _cost; // array[0..N-1] holding current cost for each item 

    _head; // array[0..U-1] holding index of first item in each bucket 

    _next; // array[0..N-1] where _next[i] is the next item 
      // in a list for the ith item 

    _prev; // array[0..N-1] where _prev[i] is the last item 
      // in a list for the ith item 
}; 

を一度に1つのバケットリストにしか存在しません。

この構造に基づいて、あなたは最悪の場合、これらの操作のためのO(1)複雑達成することができます：あなたは、単にスキャンする現在の最小バケットにインデックスポインティングを維持プライオリティキューとしてこの構造を使用するには

push(item, cost); // push an item onto the head of the appropriate bucket list 

_pop(item, cost); // _pop an item from (anywhere!) within a bucket list 

update(item, old_cost, new_cost); // move an item between buckets by combining 
            // push and _pop 

を。次にコストの低いアイテムを取得する場合は、このバケットからヘッドアイテムをポップするだけです。バケツが空の場合は、空でないものを見つけるまでバケットインデックスを増やします。

もちろん、Uが非常に大きくなり、余分なスペースの複雑さが増し、バケット上のアイテムのスパース配信の可能性があるため、この種のアプローチは魅力的ではありません。