問題タブ [kruskals-algorithm]

クラスカルのアルゴリズムを使用して im R(3.0.0 - Linux x32) 最小スパニング ツリーを計算するにはどうすればよいですか?

次のように、igraph (0.6.5) ライブラリを使用して重み付き完全グラフを作成します。

そして、プリム（igraph）で最小スパニングツリーを計算できます

しかし、残念なことに "igraph" には Kruskal のアルゴリズムが実装されていません。

生成されたグラフを data.frame として表すことができます。

Rでクルスカルのアルゴリズムでmstを計算する簡単な方法はありますか?

エッジ e を含み、その重みがエッジ e を持つすべてのスパニング ツリーの中で最小になるように、グラフ G の最小スパニング ツリーを見つけたいと考えています。

グラフ G の辺の重みが [0,1] に一様に分布しているとします。どちらのアルゴリズム プリムまたはクラスカルが高速になりますか? ソートはクラスカルアルゴリズムのボトルネックステップであるため、特定のソートアルゴリズムを利用できるため、クラスカルになると思います。

グラフに頂点を追加するコードを作成し、エッジの重みを更新してから、最小スパニング ツリーを見つけます。やったと思うのですが何かエラーがあるようで見つけられません。Valgrindを使ったシステムで、MSTの呼び出しで「サイズ4の無効な書き込み」「サイズ4の無効な読み込み」と表示される、しかし、私はそれがうまくいくと思います.Valgrindの全体のエラーは

次のコードは like によって呼び出されます

結果は (1,2) (2,4) (3,4) になります。

そして電話する

結果は (1,2) (1,3) (2,4) になります。

実行するためにシステムに送信され、上記のように呼び出されますが、上記の多くの時間サイクルで呼び出されます。

ArrayList<Edge>重複した値を削除する必要があります 。Edgeクラスは次のとおりです

Krushkal のアルゴリズムを実装するために、グラフの最小全域木を計算したいと考えています。それを計算するには、リストからすべての重複を削除する必要があります。したがって、srcNode、destNode、および edgeWeight を使用して、この種のデータ構造から重複する値を削除するのに最適なアルゴリズムはどれでしょうか。Edge

私はすでに MST を計算しており、新しいノード v をグラフに追加し、インシデント エッジを G に追加して更新しようとしています。ただし、新しいエッジから最も近い頂点まで新しい MST を計算する必要があります。 Kruskal のアルゴリズムを適用して、既存の MST の 2 つの MST を接続します。これが正しい選択であるかどうか、またこのアルゴリズムの実行時間はどのくらいになるかはわかりませんが。

クラスカルのアルゴリズムを実装して、MST の重みの合計を見つけようとしています。私の問題は、各ノードの親を設定する場所のどこかにあると思いますが、小さな例では問題なく動作しますが、大きな例ではサイクルが検出されず、最終的な答えが間違っているため、わかりません。私の発見は間違っているかもしれませんが、よくわかりません。これが私のコードです：