MST を使用したグラフ (正の重みのエッジ) 一部のエッジ e が新しい値に変更された場合、完全に再作成せずに MST を更新する最良の方法は何ですか。これは線形時間で実行できると思います。また、1) e が既に MST の一部であるかどうか、および 2) 新しいエッジ e が元よりも大きいか小さいかに基づいて、別のアルゴリズムが必要になるようです。
29319 次
2 に答える
1
私のO（n）ソリューションは、エッジの変更を開始する前に、MSTを見つける必要があるという仮定に基づいています（グラフには示されていません）。これを行うには、O（n log n）で機能するクラスカルアルゴリズムを使用できます。副作用として、並べ替えられたエッジのリストが生成されます。そのコストはソートによって支配されるため、エッジの重みを変更する場合、O（log n）のソート済みリストから削除し、同じくO（log n）に新しい値で挿入し直して、最後にKruskalを呼び出すことができます。アルゴリズムもまた、エッジがソートされているため、線形時間で実行されます。
これはあなたが要求した線形の解決策ですが、より速く実行できるようです。
于 2012-03-29T21:09:00.487 に答える