1

グラフ G の最小スパニング ツリーを見つけるアルゴリズムを作成するように求められましたが、G の各頂点がスパニング ツリー T の葉であるという条件があります。グラフに 2 つ以上の要素がある場合、これはどのように可能でしょうか? G に頂点 a、b、c が含まれていると仮定すると、スパニング ツリーは a--b--c のようになるため、この場合 b はリーフではありません。

アルゴリズムの解決策を探しているわけではありません。スパニング ツリーを葉だけで構成する方法を理解したいだけです。

これが質問の正確な文言です 質問

助けてくれてありがとう

4

1 に答える 1

4

問題は、S がグラフの頂点 V のサブセットであると述べています。葉以外のノードが存在する場合があります。ただし、これらの内部ノードが S にないことを確認する必要があります。S が V と等しい場合は正しいでしょう。

于 2016-02-14T21:11:31.930 に答える