4

元のグラフと元の MST はわかっています。ここで、グラフ内のエッジの重みを変更します。Prim と Kruskal 以外に、古い MST から新しい MST を生成する方法はありますか?

4

3 に答える 3

2

これが私がそれをする方法です：

  • 変更されたエッジが元のMSTにある場合：
    • その重量が減った場合、もちろんそれは新しいMSTになければなりません。
    • 重みが増加した場合は、元のMSTから削除し、残っている2つのサブツリーを接続する最も重みの小さいエッジを探します（これにより、元のエッジが再度選択される可能性があります）。これは、2つのサブツリーを保持する素集合データ構造を構築し、残りのエッジを重みで並べ替えることにより、クラスカルのような方法で効率的に実行できます。異なるセットの端点を持つ最初のエッジを選択します。素集合データ構造からエッジをすばやく削除する方法を知っていて、クラスカルのアルゴリズムを使用して元のMSTを構築した場合は、ここでそれらを再計算することを回避できます。
  • さもないと：
    • その重量が増加した場合、もちろんそれはMSTの外に残ります。
    • 重量が減った場合は、元のMSTに追加します。これにより、サイクルが作成されます。サイクルをスキャンして、最も重いエッジを探します（これにより、元のエッジが再度選択される可能性があります）。このエッジを削除します。多くのエッジミューテーションを実行する場合は、Floyd-Warshallアルゴリズムを使用してすべてのペアの最短経路を計算することにより、循環検出が高速化される可能性があります。次に、最初に新しいエッジを除外し、MST内の2つのエンドポイント間の最短パスを探すことで、サイクル内のすべてのエッジを見つけることができます（そのようなパスは1つだけになります）。
于 2012-11-18T06:45:22.960 に答える
2

j_random_hacker によって提案された線形時間アルゴリズムに加えて、次の本「Handbook of Data Structures and Applications」 (第 36 章) またはこれらの論文: Dynamic graphs、Maintaining Minimum Spanning Trees in Dynamic Graphsで準線形アルゴリズムを見つけることができます。

于 2012-11-18T09:05:44.540 に答える
2

結果が同じでも、問題を少し変えることができます。

  1. 元の MST の構造を取得し、各頂点から DFS を実行すると、各頂点ペア間のツリー パスで最大加重エッジを取得できます。このステップの複雑さは O(N ^ 2) です
  2. 1 つのエッジの重みを w に変更する代わりに、重みが w である元の MST に新しいエッジ (u,v) を追加していると仮定できます。エッジを追加すると、ツリーにループが作成され、ループの 1 つのエッジをカットして新しい MST を生成する必要があります。明らかに、パス (a,b) の追加エッジと最大エッジを比較することしかできません。このステップの複雑さは O(1) です。
于 2012-11-21T07:54:53.453 に答える