20

私は大学で次の問題を提示されました：

G =（V、E）を、エッジe∈Eでコストc e > = 0の（無向）グラフとします。Gで最小コストの全域木Tが与えられていると仮定します。ここで、新しいエッジがGに追加され、2つのノードv、tv∈Vをコストcで接続するとします。

  1. Tが最小コストのスパニングツリーであり、新しいエッジがGに追加されているかどうかをテストするための効率的なアルゴリズムを提供します（ただし、ツリーTには追加されません）。アルゴリズムを時間O（| E |）で実行します。O（| V |）時間でできますか？ツリーTとグラフGを表すためにどのデータ構造が使用されるかについての仮定に注意してください。
  2. Tが最小コストのスパニングツリーではなくなったとします。線形時間アルゴリズム（時間O（| E |））を与えて、ツリーTを新しい最小コストスパニングツリーに更新します。

これは私が見つけた解決策です：

Let e1=(a,b) the new edge added
Find in T the shortest path from a to b (BFS)
if e1 is the most expensive edge in the cycle then T remains the MST
else T is not the MST

動作しているように見えますが、問題がO（| E |）時間であるのに対し、O（| V |）時間でこれを簡単に実行できます。私は何かが足りないのですか？

ちなみに私たちは誰にでも助けを求めることが許可されているので私は浮気していません：D

4

3 に答える 3

8

正しい方法でツリーを保存すれば、最短経路検索で BFS よりも優れた結果を得ることができますが、あなたは正しい考えを持っています。

Tの1 つのノードrがルートであり (マトリックスまたは隣接リスト グラフ構造でツリー エッジをマークしている場合、そこから任意のノードと BFS を選択してこの構造を生成できます)、他の各ノードには親ポインターと深度カウント。Tでaとbの間の最短経路を見つけるには、次のようにします。

  1. aを「より深い」ノードにします。必要に応じて交換します。
  2. a からbまたはrに到達するまで親リンクをたどり、たどったパスを保存し、アクセスしたノードをマークします。
  3. bに到達した場合、最短経路は通過したとおりです。
  4. rに到達した場合は、 bからルートまでトラバースします。aからrへのトラバーサルで到達したノードに到達したら、停止します。2 つが出会う場所で合流すると、Tに最短経路ができます。

このアルゴリズムの有効性の証明は、読者の課題として残されています。これは BFS のような O(|V|) ですが、一般的に高速になります。実際に O(|V|) 時間を必要とする MST 構成はごくわずかです。もちろん、親リンク ツリーの生成には最初から O(|V|) の時間がかかるため、これは特定の状況でのみ役立ちます。 MST。

別のコメンターが言ったように、グラフに MST がある場合は接続されていることに注意してください。<= |E| したがって、O(|V|) < O(|E|)。

また、ツリーを O(|V|) 時間で修正するには、必要に応じて、サイクルで最も長いエッジを見つけて削除し、新しいエッジに置き換えます。これを親リンク MST で効率的に行うことも、読者の課題です。

于 2010-04-29T22:38:23.510 に答える
0

BFSで十分だと思います。そして、その複雑さは O(|V| + |E|) ですが、ツリー |E| にあります。は |V| より小さい つまり、O(|V|) は O(2|V|) です。

于 2010-04-29T07:38:19.983 に答える
-1

あなたのステップFind in T the shortest path from a to bはオーダー E オペレーションだと思います。

于 2010-04-28T19:52:07.037 に答える