私は調査を行っており、質問に固執しています：
最小スパニング ツリー (プリム アルゴリズム) を使用していますが、ツリー内の 1 つのノードが削除されました。最適性が維持されるようにツリーを再編成する方法はありますか?
ここでいくつかの提案を探しています。あなたの助けに感謝します。
ありがとうございました！
3 に答える
1
ツリー内のノードを削除すると、グラフが複数の切断されたコンポーネントに分割される場合があります。最悪の場合、すべてのエッジが 1 つの中央ノードから他のすべてのノードにつながる MST を想像してみてください。スターのように。この場合、セントラル ノードを削除すると、MST 全体をやり直す必要があります。したがって、短い答えは次のとおりだと思います-削除するノードによって異なります。解決策は、前述の aix のように実行することです。ノードが削除されたために切断されたすべてのコンポーネントを見つけて、それらを貪欲に接続します。これは、0 (リーフ ノードが削除された場合) から n-1 (スターの中心が削除された場合) まで拡張できます。
于 2011-03-18T16:51:29.630 に答える
-1
削除された頂点が MST の葉だった場合は、何もする必要はありません。スパニング ツリーがまだあり、最適のままです。
葉ではなかった場合は、2 つのサブツリーがあります。必要なのは、2 つのサブツリーの間に存在する最短のエッジでそれらを再接続することだけです。そのエッジを見つける最良の方法は、おそらく、プリムのアルゴリズムに使用したデータ構造を使用することです (または、頂点のすべてのペアを考慮して O(n^2) で)。
于 2011-03-18T15:28:55.850 に答える