検索MSTはプリム法

Question

を使用すると、いずれかのplz PRIMアルゴリズムを使用してMSTを検索する方法を私を助けることができます。 MSTのエッジを強調表示しThe Directed Minimum Spanning Tree Problemを引用

おかげ

Answer 1

..ノードがMSTに追加される順序を記述：

1. があればルートに入るアークを捨てます。 ルート以外の各ノードでは、最も小さいコストの で入力弧を選択します。選択されたn-1 のアークを集合Sとする。
2. サイクルが形成されない場合、G（N、S）はMSTである。それ以外の場合は続行します。
3. サイクル内のノードを擬似ノード （k）に変換し、外側のノード（i）からサイクル のノード（j）に入る各弧 のコストを変更します。以下の式に従ってサイクル を実行する。 j（j）、j）-min_ {j}（c（x（j）、j）） ここでc（x（j）、j） 、j）は、円弧のコストであり、jに入るサイクル内の
4. 修正コストの最小値を持つ入力円弧を選択します。 がSに同じ実ノードを入力する円弧を置き換えます 新しい選択アーク。
5. 移動契約グラフでステップ2に。

によってアルゴリズムの重要なアイデアは であるを有する置換アーク（単数または複数）を見つけます サイクル（もしあれば）を除去するための最小限の追加費用。指定された式 には、関連する追加コストが表示されます。