algorithm - 一定量のメモリを備えたBFS

Question

（グラフのサイズ）+一定量のメモリのみを使用して、つまり、どのノードがすでにアクセスされているかを記録せずに、幅優先探索を実行することは可能ですか？

Answer 1

いいえ。訪問した場所を常に覚えておく必要があります。したがって、最悪の場合、すべてのノードの訪問済み状態を記録する必要があります。ただし、グラフの分岐係数と深さが主な要因です。グラフがあまり分岐しない場合は、そのようなものは必要ありません。高度に分岐している場合は、最悪の場合になりがちです。