-1

グラフで、すべてのエッジの重みが同じであるとします=1。BFSアルゴリズムを変更して、AからBまでの最短距離SDを見つける方法を説明します。これは、呼び出しSD（A、B）で、Aが開始頂点、Bが終了頂点です。SDの問題に対する考えられるすべての答えを検討してください。

4

1 に答える 1

2

BFS はそのままで、A と B が同じ接続グラフ上にあると仮定して、A と B の間の最短距離を与えることができます。

通常、BFS は開始ノードを取得し、その近隣を一度に 1 レベルずつ検出します。つまり、距離 1 にあるすべてのノードを検出し、次に距離 2 にあるすべてのノードを検出するというようになります。

SD を A から B に返す新しいバージョンの BFS を呼び出しましょう: BFS_D

したがって、最初の変更は、1 つではなく 2 つのパラメーターを与えることです。BFS_D の戻り型はブール値になります。

ここで、A から B へのパスがあるか、ないかの 2 つの可能性があります。

パスがある場合、ある時点で、ノード キューから B を取得します。2 番目のキューを使用して各ノードのレベルを保存できるため、A から B までの距離を見つけることができます。

パスがない場合は、B を見つけることなく、A を含むすべての接続されたグラフを単純に検出します。基本的に、アクセスするノードがなくなると、false または Infinity を返すだけです。

A == B という 3 番目のケースが発生する可能性があります。コードがこのケースを正しく処理することを確認する必要があります。

ウィキペディアのコードに基づいて変更された BFS の簡単な実装を次に示します。

procedure BFS_D(G,A,B):
      create a queue Q // This will store the undiscovered nodes
      create a queue D // This will store the level (distance) of each node
      enqueue A onto Q
      enqueue 0 onto D
      mark A
      while Q is not empty:
          t ← Q.dequeue()
          td ← D.dequeue()
          if t is equal to B:
              return td
          for all edges e in G.incidentEdges(t) do
              // G.opposite returns adjacent vertex 
             o ← G.opposite(t,e)
             if o is not marked:
                  mark o
                  enqueue o onto Q
                  enqueue (td + 1) onto D
      return Infinity // We have discovered all the nodes without find B, there is no path
于 2012-10-16T05:07:13.343 に答える