BFS対DFSグラフ空間の複雑度

Question

幅の広い最初の検索にキューが含まれている場合、奥行きの最初の検索と幅の広い最初の検索では、エッジと頂点を持つグラフでどのくらいのメモリが必要ですか？

Answer 1

再帰的DFSは、現在処理されているすべてのノードの関数呼び出しとスタックフレームを必要とするため、最も課金されるメモリです。明示的なスタックおよびキューのデータ構造では、消費されるメモリに大きな違いはありません。一般的には、グラフの形状や現在スタック上またはキュー内にあるノードの数によって異なります。以前に処理された、またはまだ訪問されていないノードは、アルゴリズムによって消費されるメモリに影響しません。しかし、いくつかの極端な場合（星型グラフなど）には、グラフ全体を読むことがあります。しかし、もう一度それはグラフの構造に依存します。