問題タブ [kruskals-algorithm]

グラフ上の最小パスを見つけることができるように、クラスカル関数を作成しました。しかし、私はバブルソートでそれを行いました。qsort を使用して動作させ、構造体を動的にして、より効率的にできるようにしようとしています。

使用されているすべての機能は機能していますが、疑問がある場合は私に尋ねて投稿できます. pd(dynamcc partition)リンクとしてユニオン検索を使用しています。

私のコードは次のとおりです。

スパニングツリーとカットは密接に関連していることはすでに見てきました。これが別の接続です。クラスカルのアルゴリズムがスパニングツリーに追加する最後のエッジを削除しましょう。これにより、ツリーが2つのコンポーネントに分割され、グラフにカット（S、S）が定義されます。このカットについて何が言えますか？使用しているグラフが重み付けされておらず、クラスカルのアルゴリズムがそれらを処理するために、そのエッジがランダムに均一に順序付けられていると仮定します。ここに注目すべき事実があります。少なくとも1/n ^ 2の確率で、（S、S）はグラフの最小カットであり、カットのサイズ（S、S）はSとSの間で交差するエッジの数です。これは、プロセスをO（n ^ 2）回繰り返し、見つかった最小カットを出力すると、Gの最小カットが高い確率で生成されることを意味します。重み付けされていない最小カットのO（mn ^ 2 log n）アルゴリズムです。

• これは、クラスカルのアルゴリズムを使用してグラフを処理するためのn ^ 2のユニークな方法があるという事実に依存しませんか？つまり、クラスカルのアルゴリズムが10ノードのグラフを処理するための3つの固有の方法しかない場合、この処理をn ^ 2回繰り返しても、n^2の固有の「最後のエッジ」は生成されません。一意の最終カットがn^2未満（つまり、一意の「最後のエッジ」がn ^ 2未満）のシナリオでは、どのように機能しますか？

• 合計でn^2未満のエッジがある場合はどうなりますか？たとえば、9つのエッジしかない10個のノードの連結グラフを作成できます。つまり、アルゴリズムを何度繰り返しても、n^2個の一意の「最後のエッジ」はありません。この状況でどのように機能しますか？

• すべてのエッジをループして、エッジが最小カットであるかどうかを確認する方が簡単ではないでしょうか。nノードのグラフでは、一意のエッジの最大数はn + n-1 + n-2 ... + 1エッジであり、n^2未満です。また、n^2がn^2 log n未満であることを考慮すると、これが高速であるため、すべてのエッジをループするだけではどうでしょうか。

無向重み付きグラフ G(V,E) で最小スパニング ツリーを見つけるクラスカルのアルゴリズムを実装しようとしています。私の実装では、素集合を使用してアルゴリズムを高速化しています。コードは次のとおりです。

エラーなしでコンパイルされますが、結果は得られません。たとえば、この入力を与えると：

出力はまったく生成されません。誰でも私を助けることができますか？前もって感謝します。

編集：コメントでエラーがあると思われる場所を見つけました。は空であるため、は常にtreeであると結論付けます。したがって、間違いは関数にあるに違いありませんが、私はそれを見つけることができません。if(!same_component(array[g.edges[i].v], array[g.edges[i].u]))falsesame_component

私は教科書でこの質問に出くわしました：

「一般に、プリム、クラスカル、ダイクストラのアルゴリズムの時間計算量は何に依存していますか?」

a. グラフ内の頂点の数。
b. グラフ内のエッジの数。
c. 両方とも、グラフ内の頂点とエッジの数について。

あなたの選択を説明してください。

したがって、ウィキペディアのプリム、クラスカル、およびダイクストラのアルゴリズムによると、最悪の場合の時間の複雑さはO(ElogV)、それぞれO(ElogV)およびO(E+VlogV)です。答えはcだと思いますか？しかし、なぜ？

Prim のアルゴリズムと Kruskal のアルゴリズムはどちらも最小全域木を生成します。cut プロパティによると、ツリーの総コストはこれらのアルゴリズムで同じになりますが、複数の選択肢に直面したときにアルファベット順に選択することを考えると、これら 2 つのアルゴリズムが同じ総コストで異なる MST を与える可能性はありますか? . たとえば、エッジ A->B および B->C について max(source,dest) を比較し、A->B からの A と B->C からの B を比較します。

ありがとうございました

結果を出力ファイルに保存する際に問題があります。おそらく機能に問題があるのでしょうが、それを見つけて修正することはできません。誰が何が悪いのか知っていますか?

プログラムのコード:

これは入力ファイルです ("In0303.txt"):

そして、これは出力ファイルで作成する必要があるものです: ("Out0303.txt"):

私はwikipeidaを読んでいて、Kruskalの疑似コードを次のように見つけました:

私は何をしているのかよくわかりませんFIND_SET().Wikipediaには次の説明があります：

そのエッジが 2 つの異なるツリーを接続する場合、それをフォレストに追加し、2 つのツリーを 1 つのツリーに結合します。

2 つの異なるツリーが接続されているかどうかをチェックしていると思いますが、これは実際にはどういう意味ですか?

重複の可能性:
Kruskal vs Prim

Prim のアルゴリズムよりも Kruskal のアルゴリズムを使用して、最小スパニング ツリーを見つけるのはいつですか? 種類ごとに、どのような種類の入力グラフとノードが適していますか? スペースと時間に関して、それらのいずれかを使用する方が効率的なのはどのような場合ですか?

あるものを他のものよりもはるかに優れたものにする彼らの特定のインプットはありますか?

タイトル通り。クラスカルのアルゴリズムでノードをメモリに保持する最適な方法は何ですか?またその理由は何ですか?

私は教科書Introduction to Algorithms別名を読んでいます、私はcで使用アルゴリズムCLRSを実装したいです、私が知りたいのは、どのグラフ実装を使用すべきか、隣接リストまたは隣接行列ですか？隣接リストを使用するときにソートするのは直感的ではないと思います。隣接リストの表現は、次のように隣接リストを定義するときに混乱します。mstkruskaledgesedge

エッジをソートするとき、上で定義されたノードを指すためのポインターの配列を使用したいのですが、問題は、上で定義された構造体がstart pointエッジのを見つけることができないということend pointです。だから私はこのように構造体を変更しました：

私が聞きたいのは、次のように隣接リストを定義しても大丈夫ですか？またはより良い練習がありますか？または、隣接行列を使用する必要があります（インターネットを検索するときに行列を使用してクラスカルを実装する人がいるのを見たので）？なぜ？英語が下手でごめんなさい。どんな助けでもありがたいです。