問題タブ [kruskals-algorithm]

私はクラスカルのアルゴリズムを C++ で構築しようとしており、その一部を書きました。コードは次のとおりです。

しかし、何らかの理由で (int j = 0... ループ中に vertex_sets 配列が変更され、なぜこれが発生するのかわかりません。したがって、print ステートメントを使用します。

私はの出力を得る

これは、ループの 4 回目の反復中になんらかの理由で、インデックス 0 の vertex_sets の値が 0 から 3 に変化していることを意味します。その理由はわかりません。なぜこれが起こっているのか誰にもわかりますか？

Kruskal のアルゴリズムが BFS を使用して実装され、サイクルを作成してエッジを追加するかどうかを確認した場合、アルゴリズムの全体的な Big-O 実行時間はどのくらいになりますか?

Kruskal の MST 構築アルゴリズムは貪欲だと言われていますが、このアルゴリズムは Prim のアルゴリズムとは異なり、局所的最小値ではなく大域的最小値を選択します。Kruskalのアルゴリズムが貪欲なアプローチと見なされる方法を誰かが説明できますか?

クラスカルのアルゴリズムは次のとおりです。

私の教科書によると：

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) 時間を必要とします。

したがって、時間計算量は次のようになります。

C++ で Kruskal アルゴリズムを実装しようとしています。ベクトルが使用されているYouTubeビデオの指示に従いました。ビデオではコードが正確に実行されていることが示されていますが、同じコードが私の PC でコンパイルされることさえありません。問題がわかりません。コードは次のとおりです。 #include #include using namespace std;

C ++でO（n log n）でKruskalのアルゴリズムを実行する方法を学ぶことに興味があります。O（n ^ 2）で実行されるソリューションを使用してアルゴリズムを実装しました。そのためのコードは以下のとおりです。

O(n log n) で Kruskal を実行できることはわかっていますが、どうすればこれを実行できるかわかりません。すべてのヒントをいただければ幸いです。

だから私はこのグラフを解決する必要があります.私はそれを解決する方法について一般的な考えを持っていますが、これを間違っている場合は私を修正してください.

したがって、MST を見つけるには、グラフでクルスカルス アルゴリズムを実行する必要があります。

これが、このクルスカルス アルゴリズムの擬似コードです。

Kruskal(V,E) A = null; for each v が V に含まれる make disjoint set(v) E を重みで徐々にソート for each(v1, v2) が E に含まれる if

だから私が最初にすることは、最短距離のノードを見つけることですよね?

1)

d(h,s) = -3 であるため、S から H への距離が最短であると仮定します。

だから A = {(h,s)}

だから今、私たちはこのパターンに従います

2) A = {(h,s),(s,f)}

3) A = {(h,s),(s,f)(s,n)}

4) A = {(h,s)(s,f)(s,n)(f,k)}

5) A = {(h,s)(s,f)(s,n)(f,k)(s,m)} (h から n へのパスが既に作成されているため、H から N をスキップします。 s )

6) A = {(h,s)(s,f)(s,n)(f,k)(s,m)(d,b)}

7) A = {(h,s)(s,f)(s,n)(f,k)(s,m)(d,b)(b,m)}

では、すべてのエッジに接続するパスがあるので、これで問題ありません。

しかし、私が理解していないのは、複数の頂点を通るパス[u、v]よりも短い距離[u、v]があることです。たとえば、d[d,m] は、最初に B を通過する p[d,m] よりも短くなります。私は何か間違ったことをしていますか？