問題タブ [kruskals-algorithm]

Prim のアルゴリズムをいつ使用し、 Kruskal の最小スパニング ツリーをいつ見つけるべきなのか疑問に思っていました。どちらも簡単なロジックで、最悪のケースも同じです。唯一の違いは、データ構造が少し異なる可能性がある実装です。では、決め手は何ですか？

Prim のアルゴリズムを C (www.bubblellicious.es/prim.tar.gz) で実装しましたが、これをKruskal のアルゴリズムに変換する方法を考えていました。

それらは非常に似ているようですが、古いコードを新しいコードに変更する方法が想像できません。アドバイスなど頂ければ有難いです。それが簡単なのはわかっていますが、私はまだ C プログラミングの初心者です ...

私はクルスカルのアルゴリズムを実装しており、スレッドを利用したいと考えています。ただし、これを行うためのアルゴリズムについて十分に知っているかどうかはわかりません。

私が想像しているのは、グラフのさまざまな部分が解決され、最後に接続されることです。誰かが私を正しい方向に向けることができますか? ありがとう。

疎なグラフと密なグラフに関して、Prim と Kruskal の時間の複雑さが異なる理由を理解しようとしています。それぞれがどのように機能するかを示すいくつかのアプレットを使用した後でも、グラフの密度がアルゴリズムにどのように影響するかについて、まだ少し混乱しています。誰かが私に正しい方向への微調整をしてくれることを願っています。

重複の可能性：
クラスカルvsプリム

krukshalのアルゴリズムまたはPrimsアルゴリズムのどちらが最小全域木を見つけるのに優れていますか？

Prim と Kruskal の両方のアルゴリズムを記述して、C++ または Java で最小全域木を見つけることができますが、O(mlogm) または O(mlogn) を使用して Haskell でそれらを実装する方法を知りたいです (純粋な関数型プログラムの方が優れています)。どうもありがとう。

http://en.wikipedia.org/wiki/Disjoint_sets

http://en.wikipedia.org/wiki/Kruskal's_algorithm

素集合に使用されているデータ構造の結合/検索...

私自身のベンチマークとなる C++ Kruskal の実装を探しています...良いものをいくつか知っている場合は、共有してください!

この質問が少し広範である場合は申し訳ありませんが、最小コストのスパニング ツリーを作成する方法を理解するのに苦労しています。これは、問題がある場合は C++ にあります。

私が理解していることから、クラスカルを使用して、スパニング ツリーを構築するための最小コスト エッジを選択します。私の考えは、エッジを最小ヒープに読み込むことです。そうすれば、最小コストでエッジを取得するためにトップから削除できます。

これまでのところ、minheap と union-find のセットしか実装できませんでした。union-find の目的と、スパニング ツリーを作成するためのソート アルゴリズムについてはまだわかりません。

アドバイスをいただければ幸いです。

編集: ユニオンの検索、minheap、kruskals、および並べ替えアルゴリズムに限定されているわけではなく、何もする必要もありません。これらは講師が提案した項目にすぎません。

Kruskal の最小スパニング ツリーのアルゴリズムの逆は機能しますか? つまり、すべてのステップで最大の重み (エッジ) を選択するということですか?

最大スパニングツリーを見つけるための他のアイデアはありますか?