一定量のメモリを持つBFS

Question

（グラフのサイズ）+一定量のメモリを使用して、つまり、どのノードが既に訪問されているかを記録せずに、ブーストファーストサーチを実行できますか？

Answer 1

いいえ、あなたはいつもあなたが訪れた場所を覚えておく必要があります。したがって、最悪の場合、すべてのノードの訪問済み状態を記録する必要があります。しかし、グラフの分岐因子と深さが主な要因です。グラフが大きく分岐しない場合は、そのようなものは必要ありません。分岐が多い場合は、最悪の場合があります。