algorithm - プリムのアルゴリズムを使用して最大スパニング ツリーを見つける

Question

最小頂点を選択する代わりに最大頂点を選択するようにアルゴリズムを変更して、最大スパニング ツリーを計算できますか?

エッジを無効にし、通常のプリムの最小スパニング ツリー アルゴリズムを適用することで、解決策を見つけました。

Answer 1

入力グラフをアルゴリズムにフィードしますが、重みは否定されます。Prim では、重みが正であると想定しているものはありません。否定された重みの最小値は、元の重みの最大値によって達成されます。