どのような意味で、DFSはBFSより高速ですか？

Question

DFSとBFSについて読んでいるうちに、DFSはBFSより高速であり、メモリが少なくて済むという声明が出ました。

私の実装は両方ともC++であり、DFS用のスタックとBFS用のキューを作成します。誰かが何を説明してください、どのように速度とメモリの要件が違うのですか？

Answer 1

• メモリ要件：キューサイズは幅によって束縛されるのに対し、スタックサイズは深さに拘束されます。 n個のノードを持つ平衡二分木の場合、スタックサイズはlog（n）ですが、キューサイズはb O（n）になります。すべてのケースでBFSに明示的なキューは必要ないかもしれないことに注意してください。可能であれば、子インデックスのスタックを十分に保つことができます。

• スピード：それは当てはまりません。完全な検索のために、両方のケースがかなりの余分なオーバーヘッドなしにすべてのノードを訪問する。一致する要素が見つかったときに検索を中止することができれば、検索された要素が通常レベル上にあるため検索ツリーで上位に表示されるのが一般的です。検索された要素が一般に比較的深く、多くの要素の1つが十分である場合、DFSはより高速になる可能性があります。