algorithm - Primのアルゴリズムを使用して有向グラフのMSTを見つける

Question

PRIM アルゴリズムを使用して MST を見つける方法を教えてください。MST のエッジを強調表示し、ノードが MST に追加される順序を書きます..ありがとう

Answer 1

有向最小スパニング ツリー問題の引用:

1. ルートに入るアークがある場合は破棄します。ルート以外の各ノードについて、コストが最小の入力アークを選択します。選択した n-1 個のアークを集合 S とする。
2. サイクルが形成されない場合、G(N,S) は MST です。それ以外の場合は続行します。
3. 形成されたサイクルごとに、サイクル内のノードを擬似ノード (k) に縮小し、次に従って、サイクル外のノード (i) からサイクル内のノード (j) に入る各アークのコストを変更します。方程式。
   c(i,k)=c(i,j)-(c(x(j),j)-min_{j}(c(x(j),j)) ここで c(x(j),j)は、j に入るサイクルのアークのコストです。
4. 疑似ノードごとに、修正コストが最も小さい入力アークを選択します。S の同じ実ノードに入るアークを、新しく選択したアークに置き換えます。
5. 収縮したグラフでステップ 2 に進みます。

アルゴリズムの重要なアイデアは、もしあればサイクルを排除するための最小の追加コストを持つ置換アークを見つけることです。与えられた方程式は、関連する追加コストを示しています。