2

だから私はこのグラフを持っています

ここに画像の説明を入力

最小スパニングツリーを構築しようとしています。頂点 AI から始めて ABFED に進み、その後、D に隣接するすべての頂点が既にツリーの一部であることを考えると、どこにも行きません。どうすれば続行できますか?

また、最小スパニング ツリーの一部となる新しいエッジの値の範囲を計算するにはどうすればよいですか?

よろしくお願いします。

4

1 に答える 1

3

Prim のアルゴリズムがどのように機能するかについて、あなたは少し誤解していると思います。上記の説明に基づいて、Prim のアルゴリズムは次のように機能すると思われます。

  • 任意のノードから開始します。
  • まだ訪れていない現在のノードに接続されているすべてのノードを調べます。
  • これらのノードの中で最も安価なノードに移動します。
  • すべてのノードがカバーされるまで繰り返します。

これはPrim のアルゴリズムの仕組みに近いですが、正確には正しくありません。Prim のアルゴリズムには、「現在の」ノードの概念はありません。代わりに、追加したノードと追加していないノードの 2 つのノード セットがあります。Prim のアルゴリズムは次のように機能します。

  • 任意のノードから開始します。「in」セットに追加します。
  • 「in」セットにまだ追加されていない、「in」セットに接続されているすべてのノードを調べます。
  • これらのノードの中で最も安価なものを「in」セットに追加します。
  • すべてのノードが「in」セットに含まれるまで繰り返します。

上記のグラフでは、ノード A から開始しました。アルゴリズムに従って、A に接続されているすべてのノードを調べ、最も安価な (B) を取得して、「イン」セットに追加します。"in" セットには A と B が含まれています。

ここで、「in」セット内の任意のノードに接続されているすべてのノードを確認します。これらはノード D、F、E、および H です。これらのうち、最も安価なのは H であるため、H を「in」セットに追加します。これは現在、A、B、および H です。

「in」セット内の何かに接続されているすべてのノードをもう一度見てみましょう。これらはノード D、F、E、I、および G です。これらの中で最も安価なのは F であるため、それを追加します。

すべてのノードが追加されるまでこのプロセスを繰り返し、その過程で追加したエッジを追跡すると、グラフ全体の最小スパニング ツリーになります。

お役に立てれば！

于 2015-07-08T23:28:47.237 に答える