c - Prim のアルゴリズムを Kruskal のアルゴリズムに変える方法は?

Question

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

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

Answer 1

Kruskal のコードをゼロから作成して、独自のソリューションでそれらを比較してみませんか? 学ぶための最良の方法。

Answer 2

変換するには、単一のツリーではなく、一時的な出力構造としてフォレスト（つまり、最初は各ノードがツリーであるツリーのセット）が必要です。次に、各ステップで、現在接続されていないノードをツリーに追加する最も安価な頂点を見つけるのではなく、グラフで最も安価なエッジを見つけ、新しいツリーを作成する場合（つまり、以前に接続されていない2つのノードを接続する場合）、そのツリーをフォレストを作成し、ソースツリーを削除します。それ以外の場合は、エッジを破棄します。Kruskalの適切な実装は、適切なPrimの実装よりもメモリを消費しますが、時間はかかりません。

しかし、2つの違いは非常に大きいです。おそらく、間に保持できるのは、いくつかのヘルパー関数といくつかのデータ構造だけです。変換ではなく、より高レベルのビルディングブロックを使用した書き直しです。

Answer 3

C++ に切り替えて、ブースト グラフ ライブラリ ( http://www.boost.org/ )を使用することを検討してみませんか?

両方のアルゴリズムの非常に優れた実装が含まれています。タイプセーフで高性能。kruskal_minimum_spanning_treeおよびprim_minimum_spanning_treeを参照してください。