0

2 つの頂点 (A と B) とツリー (G) (無向単純グラフ) が与えられた場合 - G の A と B の間の単純なパスで頂点を見つけます。アルゴリズムは O(V) の複雑さで実行する必要があります。

たとえば、a と b の間の単純なパスで頂点を見つけます。

d<->k
k<->a
k<->b

答えは : k

目標を達成するために BFS を変更しようとしましたが、今のところうまくいかないようです。

助言がありますか？

4

1 に答える 1

3

距離を見つけた後で問題がパスの再構築にある場合は、次の方法で BFS を調整します。接続する 2 つの頂点のいずれかから始めて、BFS を実行します。発見したすべての頂点について、その前任者を保存します。エッジ を介してv頂点を発見した場合、 の前任者はです。その後、ターゲット頂点から開始し、ソース頂点に到達するまで前任者から前任者へと進むことで、パスを逆の順序で再構築できます。wu->wwu

例：

     J
      \
       \
        A
       / \
      /   \
     B     C
    / \     \
   /   \     \
  D     E     F
             / \
            /   \
           G     H
            \
             \
              I

Dからへのパスを計算するIと、次の先行操作があります。

pre[I]=G
pre[G]=F
pre[F]=C
pre[C]=A
pre[A]=B        //A was discovered during the BFS via the edge B->A, so pre[A]=B
pre[B]=D

また、パス上に存在しない前任者もいくつか存在するため、再構築時には問題になりません。この例では、次のものもあります

pre[J]=A
pre[E]=B
pre[H]=F

ただし、BFS のソースからDターゲットへのパスについては、I再構築中にそれらに遭遇しません。

から始まるパスを再構築すると、完全なパスが逆順になるまで、、次に、というようになりIます。I<-GI<-G<-F

1 つのターゲットへのパスのみを気にする場合は、ターゲットを検出した後で BFS を中止できます。ただし、これによって複雑さが変わることはありません。ただし、1 つのソース頂点からすべてのターゲットへのパスが必要な場合は、完全な BFS を実行します。これを行うと、前任者が任意のターゲット頂点へのパスを再構築できるようになります。

于 2013-03-29T17:50:48.763 に答える