6

STL キューを使用して、グラフに BFS (幅優先検索) を実装しています。そのノードがまだキューに存在しない場合は、そのノードをキューにプッシュする必要があります。ただし、STL キューではその要素を反復処理できないため、STL の検索機能を使用できません。

各ノードにフラグを使用して、訪問したときにそれらをマークし、フラグがfalseの場合にのみプッシュすることができますが、BFSを複数回実行する必要があり、毎回すべてのフラグをリセットする必要があるため、終了しましたフラグの代わりにカウンターを使用していますが、キュー内のアイテムを見つける標準的な方法があるかどうかを知りたいです。

4

2 に答える 2

7

BFS で「クローズド セット」の概念を実装していると思いますか? これを行う標準的な方法は、既に遭遇した要素の別のstd::setorを単純に維持することです。std::unordered_setそうすれば、O(lg n ) または O(1) ルックアップを取得できますが、サポートされている場合、キューを反復処理するには O( n ) 時間がかかります。

于 2012-05-11T12:06:14.217 に答える