algorithm - エッジを含め、エッジを持つものの中で重みが最小のスパニング ツリーを生成する

Question

エッジ e を含み、その重みがエッジ e を持つすべてのスパニング ツリーの中で最小になるように、グラフ G の最小スパニング ツリーを見つけたいと考えています。

Answer 1

重みを 0 に設定し、お気に入りの MST アルゴリズムを実行することで、そのエッジ (およびツリーを維持するスパニング ツリーに含めたいその他のエッジ) のエッジの重みを設定できます。