6

動的な最小全域木を作りたいです。n 個の頂点にまたがる既存の MS ツリーがあり、この新しい頂点から既存のすべての頂点にもう 1 つの頂点とエッジを追加します。新しいグラフの MST を効率的に更新するにはどうすればよいですか? O(n) が最適です。頂点の削除操作も効率化できますか?

4

1 に答える 1