2

ソースノードが与えられ、ノード間の各エッジが均一なコストを持つ、固定距離までの他のすべてのノードを見つける必要があるグラフの問題を見ています。そのため、標準の FIFO キュー手法を使用して幅優先検索を実装しましたが、一定の距離で BFS を停止すると問題が発生します。

DFS を使用していた場合、再帰呼び出しごとに現在の深さを渡すことができますが、ここではできません。グラフのノードを変更して、追加のパラメーター (距離) を保持することもできません。提案や参考文献はありますか？

4

3 に答える 3

3

2つのキューを使用して、それらの間を行き来するだけです。あるものから別のものに切り替えるたびに、深度カウントを1つ増やします。

詳述する...

「アクティブ」キューと「非アクティブ」キューを維持します。

アクティブキューからノードをポップします。そのネイバーを非アクティブなキューに追加します。アクティブキューが空になるまで繰り返します。次に、キューを交換します。

dこれにより、アクティブキュー内のすべてのノードまでの距離がである場合、非アクティブキュー内のすべてのノードまでの距離がであるという不変条件が維持されますd+1。追跡し、必要なときに停止するのに十分簡単です。

于 2013-03-08T21:14:15.093 に答える
2

キューに入れる値に深さを渡すことができます。各ノードに到達した深さを格納するために別の配列を保持することもできます。

于 2013-03-08T21:16:15.673 に答える
1

通過する頂点を、BFS のソースからの距離とともにカプセル化します。

別の可能性は、キュー内の頂点をマークすることです。通常、グラフのフレームワークでは、グラフの要素に重みを割り当てることができます。これは、目的に使用できるメカニズムです。

最後の 1 つの可能性は、BFS の 1 つのレベルのフロンティアが完全に処理された後に、実際にはグラフにないマーキング頂点をキューに挿入して、新しいレベルの BFS 深度がいつ開始されるかを知ることです。v u w x y MARKER s t j l kを除いて、これらすべてがグラフの頂点である場合、キューは次のようになりMARKERます。

于 2013-03-08T21:17:55.367 に答える