問題タブ [kruskals-algorithm]

次のようなウィキペディアによる素集合データ構造を使用して、クラスカルのアルゴリズムをC++で実装しました。

私の質問は次のとおりです。これらの2行のコードが必要ですか？もしそうなら、彼らの重要性は何ですか？

1. int px=findset(x),py=findset(y); 代わりにマージでint px=parent[x],py=parent[y];
2. parent[x]=findset(parent[x]);の代わりにfindsetでreturn findset(parent[x]);

グラフを調べて、ある ID のすべてのインスタンスを新しい ID に変更しようとしましたが、それでもサイクルが発生しました。非環式解を解く計画とは?

誰かが2つのアルゴリズムのいくつかのアプリケーション、それらを使用できる場所とアプリケーションを教えてもらえますか？

Adaの Kruskal のアルゴリズムを参照すると、どこから始めればよいかわかりません。

実際にプログラムを書く前に、すべてを考えようとしていますが、どのデータ構造を使用すべきか、すべてをどのように表現するかについてかなり迷っています。

私の当初の考えは、隣接リストで完全なツリーを表すことでしたが、ウィキペディアを読むと、アルゴリズムは次のように述べられてcreate a forest F (a set of trees), where each vertex in the graph is a separate treeおり、非常に面倒にならずにこれを実装する方法がわかりません。

次にやるべきことは ですがcreate a set S containing all the edges in the graph、繰り返しになりますが、これを行う最善の方法が何であるかはわかりません。to、 、fromを含むレコードの配列を考えていましたが、 .weightで迷ってしまいましたforest。

最後に、エッジが 2 つのツリーを接続しているかどうかを知る方法を見つけようとしていますが、これをすべて行う最善の方法が何であるかはわかりません。

グラフ理論のトピックから次のコードがあります。最小スパニングツリーのクラスカルアルゴリズム

これは機能し、次の入力に使用します

ここで、頂点の数とエッジの数は4で、次のように出力されます。

私の質問は、意味上のエラーがありますか？また、配列と多くの変数を使用しましたが、このコードをショートさせることはできますか？私の（プログラミング）言語はc++です

ファイルから表現を読み取り、隣接リストに保存しています。次に、グラフを「graphviz 形式」で出力し、グラフに対して MST アルゴリズムを実行します。最後に、MST を「graphviz 形式」で出力します。私はC++でこれをやっています。

私の主な質問は、アルゴリズムに関するものです。Kruskals アルゴリズムを実装していますが、並べ替え機能が機能していません。

コンパイルすると、次のエラーが発生します。

'void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [ with _RandomAccessIterator = __gnu_cxx::__normal_iterator*, std::vector, std::allocator > > >, _Compare = bool (*)(Edges, Edges)] からインスタンス化'</p>

これが私のコードです：

特定のグラフの MST を見つけるためのクルスカルのアルゴリズムを研究していましたが、最初はすべての頂点をフォレストと見なす必要があるという基本的な概念を理解しています。その後、最小エッジを見つけて、エッジの頂点を 1 つのツリーに結合する必要があります。そして、すべての頂点を含むツリーが 1 つだけになるまで、これを再帰的に実行します。

そして、このアルゴリズムの次の実装に出くわしました。

私が理解していないのは、次の必要性です：

これら 2 つの while ループは正確には何をするのでしょうか?

編集：そしてまた必要性-

三角形の不等式に従うグラフで TSP の 3/2 近似を取得するためのクリストフィデス アルゴリズムを実装しています。Kruskal のアルゴリズムと隣接行列を使用して最小全域木を計算するためのコードは既にあります。

ここで、エッジを 2 倍にし、オイラー ツアーを見つけて、複製ノードをショートカットすることで、Christofides を実装したいと考えています。この手順を実行するにはどうすればよいですか? アルゴリズムと (オプションで) C コードが欲しいです。

ありがとう！

隣接行列グラフ表現を使用してCでクラスカルアルゴリズムを実装しました。問題は、セグメンテーション違反エラーがポップアップし続けることです。かなり前から何が問題なのかを突き止めようとしていて、見つけられないようです。問題、他の誰かが見てくださいませんか？ありがとう。

これが私のコードです：

これは、クラスカルのアルゴリズムに使用した擬似コードです。ここで使用したデータ構造は隣接行列です。私は成長の順序を取得しましたn^2。正しいかどうか知りたいです。