2

サンプルの問題では、重み付きグラフG =（V、E）のMSTTが与えられています。問題は、新しい頂点vとそのすべてのエッジをグラフに追加する場合、この新しいG * =（VU v、 E *）。

これまでの私の唯一のアイデアは次のとおりです。

add min( out(v) ) to T
for each edge e in out(v) do
  let u be the other vertex of e
  if there exists a lower weight path from v to u then
    remove all edges in that path from T
    add e to T

2つの問題：

  1. 切断された可能性のある頂点をどうすればよいですか
  2. これは間違いなくO（| V | log | V |）ではありません

これどうやってするの？

4

2 に答える 2

2

線形時間でそれを行うこともできます（新しいエッジの数（たとえばk）がnと比較してかなり少ない場合）。新しいMSTが新しい頂点をカバーする必要があることはわかっています。したがって、新しいエッジの少なくとも1つを追加する必要があります。したがって、最小値のエッジをMSTに追加する必要があります（これを証明できます）。複数の新しいエッジが変更される場合があります。したがって、新しいエッジを昇順で並べ替えます。最初のエッジをグラフに追加します。今、私たちは新しいサイクルを持っています。グラフトラバーサルを実行すると、サイクルが検出され、このサイクルから最大値のエッジが削除されます。次に、もう1つの新しいエッジを追加して、手順を繰り返します。

複雑さは、新しく追加されたエッジの数（n + m）倍です（ほぼ線形）。

于 2013-02-24T23:12:41.060 に答える
0

最終的に、MSTがすでにMSTに含まれているエッジの中にあり、新しいエッジが追加されていることがわかります。

したがって、グラフを取得するすべての新しいエッジを追加します。これに対して通常のMSTアルゴリズム（Boruvka、Kruskal、Prims）を実行すると、ソリューションが得られます。

この中のエッジは=（V-2）であるため、最初に（V-1）が追加されます= 2V-1アルゴリズムは、必要な時間制限を達成します。

于 2012-01-29T19:17:03.937 に答える