水道管の問題を最適化するために Prim のアルゴリズムを使用することを考えています。隣接する頂点が見つかったエッジがある場合に隣接行列を初期化する方法に非常に困惑しています。エッジが存在するたびに重みを付けることを考えました。ただし、w(Vi,Vj) 自体は重み行列のように見えます。では、そもそもなぜ A{Vi,Vj} が必要なのでしょうか。
私がやろうとしているのは、アルゴリズムのアプローチを書き、後でプログラムを書き続けることだけです。以下でよろしいですか？
隣接行列 A{Vi,Vj} を設定します。ここで、Vi には訪問したすべてのノードが含まれ、Vj には訪問した Vi に隣接するすべてのノードが含まれます。以下のマトリックスは、特定の距離を介して隣接する家のペアと接続されているすべての家のペアを格納します。私は混乱しています
for each Vi:=1 to n do //Vith は i 番目の頂点で 、各 Vj:=1 to n do //Vjth は隣接するハウスのペアであり、その重みは if (Vi とVj) 次に、 A{Vi,Vj} を w(Vi,Vj) で 設定します。それ以外の場合(Vi と Vj の間にエッジが存在しない 場合)、 A[Vi,Vj]:=0を設定します。
最小スパニング ツリーの計算。
- 出力: 必要な水道管の合計を表示します。