MST を持つグラフ (正の重みのエッジ) で、あるエッジ e が新しい値に変更された場合、MST を完全に作り直すことなく更新する最適な方法は何ですか。これは線形時間で実行できると思います。また、1) e がすでに MST の一部であるかどうか、2) 新しいエッジ e が元のエッジよりも大きいか小さいかに基づいて、異なるアルゴリズムが必要になるようです。
ベストアンサー1
4つのケースがあります:
エッジは MST にあり、エッジの値は減少します。
現在のMSTは依然としてMSTですエッジは MST 内になく、エッジの値が減少しています:
この辺をMSTに加えると、ちょうど1つのサイクルが得られます
。サイクルプロパティMST では、そのサイクルにある最高値を持つエッジを見つけて削除する必要があります。これは、dfs または bfs を使用して実行できます。複雑度は O(n) です。エッジは MST にあり、エッジの値を増やします。
このエッジを MST から削除します。これで、接続する必要がある 2 つの接続コンポーネントができました。両方のコンポーネントを O(n) (bfs または dfs) で計算できます。これらのコンポーネントを接続する最小の値を持つエッジを見つける必要があります。エッジを値の昇順で繰り返します。複雑度は O(n) です。エッジは MST に存在せず、エッジの値が増加しています。
現在のMSTは依然としてMSTです