私はC（www.bubblellicious.es/prim.tar.gz）でPrim's algorithmを実装しましたが、私はちょうどKruskal's algorithmにこれを変換する方法を疑問に思いました。プリンスのアルゴリズムをクルスカルのアルゴリズムに変えるには？
彼らは非常に似ているようだが、私はどのように私は新しいものに私の古いコードを変更することができます想像することはできません。あなたがいくつかのアドバイスや何かを与えるなら、それはおいしいでしょう。私はそれが簡単だと知っていますが、私はまだCプログラミングのn00bです...
Kruskalを一から書いて、あなたのソリューションでどのように比較すればよいのでしょうか？学ぶ最も良い方法。
変換するには、単一のツリーではなく一時的な出力構造として、フォレスト（最初は各ノードがツリーであるツリーのセット）が必要です。次に、各ステップではなく、あなたのツリーに現在接続されていないノードを追加する最も安い頂点を見つけることに、あなたは、グラフで最も安いのエッジを見つけて、それが新しいツリーを作成した場合（つまり、2つの以前に未接続のノードを接続する）に、そのツリーを追加しますソースツリーを削除します。それ以外の場合は、エッジを破棄します。クラスカルの 適切な実装では、より多くのメモリ集約型が、適切なプリム実装より集中短い時間です。
しかし、両者の違いは非常に大きいです。たぶん、あなたが保つことができるのは、いくつかのヘルパー関数といくつかのデータ構造です。変換ではなく、より高いレベルのビルディングブロックを使用して書き直します。
なぜC++に切り替えて、ブーストグラフライブラリ （http://www.boost.org/）を使用してみませんか？
それは非常によく、両方のアルゴリズムの実装が含まれています。型安全で高性能です。 kruskal_minimum_spanning_treeとprim_minimum_spanning_tree
質問に関連するコードをインラインで掲載すると、役に立つ反応を得る可能性がさらに高くなります。プリムのアルゴリズムは4行の擬似コードしかないので、半ダースのファイルのtarballが必要であるとは思えません。 –
さて、メインファイルだけを読むことができます。すべてのファイルを見る必要はありません。 –
これらのアルゴリズムは類似していないので、互いに変換することは有益です.Kruskalにはある種の優先度キューが必要ですが、Prim'sにはエッジのグローバルソートリストが必要です。最初から始める方が良いです。 –