クラスカルのアルゴリズムは次のとおりです。
MST-KRUSKAL(G,w)
1. A={}
2. for each vertex v∈ G.V
3. MAKE-SET(v)
4. sort the edges of G.E into nondecreasing order by weight w
5. for each edge (u,v) ∈ G.E, taken in nondecreasing order by weight w
6. if FIND-SET(u)!=FIND-SET(v)
7. A=A U {(u,v)}
8. Union(u,v)
9. return A
私の教科書によると：
1 行目のセット A の初期化には O(1) 時間がかかり、4 行目のエッジの並べ替え時間は O(E lgE) です。行 5 ～ 8 の for ループは、素集合フォレストに対して O(E) FIND-SET および UNION 操作を実行します。|V|とともに MAKE-SET 操作は、合計で O((V+E)α(V)) 時間かかります。ここで、α は非常にゆっくりと成長する関数です。G が接続されていると仮定しているため、|E| が得られます。<= |V|-1 であるため、互いに素な集合演算には O(E α(V)) の時間がかかります。さらに、α(V)=O(lgV)=O(lgE) であるため、クラスカルのアルゴリズムの総実行時間は O(E lgE) です。|E|<|V|^2 を観察すると、lg |E|=O(lgV) となり、クラスカルのアルゴリズムの実行時間を O(E lgV) と言い換えることができます。
4 行目のエッジをソートする時間が O(E lgE) であると推測する理由を説明していただけますか? また、総時間計算量が O((V+E)α(V)) であることをどのように取得しますか?
さらに、グラフ内のすべての辺の重みが 1 から |V| までの整数であるとします。クラスカルのアルゴリズムをどれだけ速く実行できますか? ある定数 W に対してエッジの重みが 1 から W の範囲の整数である場合はどうなるでしょうか?
時間計算量はエッジの重みにどのように依存しますか?
編集：
さらに、グラフ内のすべての辺の重みが 1 から |V| までの整数であるとします。クラスカルのアルゴリズムをどれだけ速く実行できますか?
私は次のように考えました：
クラスカルのアルゴリズムをより高速に実行するために、Counting Sort を適用してエッジを並べ替えることができます。
- 行 1 には O(1) 時間が必要です。
- 行 2 ～ 3 には O(v) 時間が必要です。
- 4 行目は O(|V|+|E|) 時間かかります。
- 行 5 ～ 8 には O(|E|α(|V|)) の時間が必要です。
- 行 9 は O(1) 時間を必要とします。
したがって、辺を解くために Counting Sort を使用すると、Kruskal の時間計算量は次のようになります。
私の考えが正しいか教えていただけますか？
また：
ある定数 W に対してエッジの重みが 1 から W の範囲の整数である場合はどうなるでしょうか?
ここでも Counting Sort を使用します。アルゴリズムは同じになります。時間複雑度は次のようになります。
- 行 1 には O(1) 時間が必要です。
- 行 2 ～ 3 には O(|V|) 時間が必要です。
- 行 4 は、O(W+|E|)=O(W)+O(|E|)=O(1)+O(|E|)=O(|E|) の時間を必要とします。
- 行 5 ～ 8 には O(|E|α(|V|)) の時間が必要です。
- 行 9 は O(1) 時間を必要とします。
したがって、時間計算量は次のようになります。
