4

これは、私が苦労している模擬試験の問題です。

G = (V, E) を、正の重みを持つ重み付き無向連結グラフとします (重みが異なると仮定してもかまいません)。与えられた実数 r に対して、部分グラフ Gr = (V, {e in E | w(e) <= r}) を定義します。たとえば、G0 にはエッジがなく (明らかに接続されていません)、Ginfinity = G (仮定により接続されています) です。問題は、Gr が接続されるような最小の r を見つけることです。

BFS または DFS を繰り返し適用して問題を解決する O(mlogn) 時間アルゴリズムを説明してください。

本当の問題は、O(mlogn) でそれを行うことです。これが私が持っているものです：

r = min( w(e) )                            => O(m)
while true do                              => O(m) 
  Gr = G with edges e | w(e) > r removed     => O(m)
  if | BFS( Gr ).V | < |V|                   => O(m + n)
    r++ (or r = next smallest w(e))          
  else
    return r

それはなんと O(m^2 + mn) です。O(mlogn) に下げるためのアイデアはありますか? ありがとう！

4

2 に答える 2

3

次のアルゴリズムはどうですか？

最初に、グラフからすべてのエッジ (または を使用してすべての個別のエッジ長) のリストを取得し、それらを並べ替えます。O(m*log m) = O(m*log n) 時間かかります: m は通常 n^2 より小さいので、O(log m)=O(log n^2)=O(2*log n) =O(log n)。

r がエッジの重みに等しいことは明らかです。したがって、ソートされた配列のエッジのインデックスでバイナリ検索を実行できます。

試行するインデックスごとに、対応するエッジの長さを r として取り、BFS または DFS で長さ <= r のエッジのみを使用して、グラフの接続性を確認します。

二分探索の各反復には O(m) かかり、O(log m)=O(log n) の反復を行う必要があります。

于 2011-12-15T21:39:07.763 に答える
3

O(m) の外側のループになるすべての可能なエッジ コストを反復しています。すべてのエッジ >w(e) を破棄したときにグラフが切断される場合、 >w(e') についても切断されることに注意してくださいw(e') < w(e)。このプロパティを使用して、エッジ コストに対してバイナリ検索を実行できるため、これを O(log(n)) で実行できます。

lo=min(w(e) for e in edges), hi=max(w(e) for e in edges)
while lo<hi:
   mid=(lo+hi)/2
   if connected(graph after discarding all e where w(e)>w(mid)):
       lo=mid
   else:
       hi=mid-1
return lo

二分探索の複雑さは O(log (max_e-min_e)) (実際には O(log(edges)) まで下げることができ、エッジの破棄と接続性の決定は O(edges+vertices) で実行できるため、これはO((edge+vertices)*log(edges)) で実行できます。

警告: コードでこれをまだテストしていないため、バグがある可能性があります。しかし、アイデアはうまくいくはずです。

于 2011-12-15T21:40:09.607 に答える