(1) [AI で頻繁に使用される] グラフ検索アルゴリズムでは、DFS の主な利点はスペース効率です。これは、BFS での主な利点です。ただし、訪問したノードを追跡すると、訪問したすべてのノードをメモリに保存する必要があるため、この利点が失われます。訪問したノードのサイズは時間の経過とともに大幅に増加することを忘れないでください。また、非常に大きな/無限のグラフの場合、メモリに収まらない可能性があります。
(2) DFS が無限分岐[無限グラフ内] にある場合があります。無限分岐は、終わらない [常に「より多くの息子」を持つ] 分岐であり、ターゲット ノードに到達しないため、DFS の場合、この分岐を無限に拡張し続け、適切な分岐を「見逃す」可能性があります。それが目的のノードにつながります。
おまけ:
DFS
と BFS を組み合わせて使用することで、比較的小さなメモリ サイズを維持しながら、DFS のこの欠陥を克服できます。
従来のDFSアルゴリズムはノードを追跡します。ローカル検索アルゴリズムは状態を追跡せず、記憶喪失で動作します。したがって、ループは主に無限のブランチ（無限の可能な状態を持つブランチ）を参照していると思います。その場合、DFSは単純にダウンし、1つのブランチに集中しすぎます。
サイクルをチェックしないと、DFS は 1 つのノードでスタックしてターゲットを見つけることができませんが、BFS は常に次の深さのすべてのノードに展開されるため、サイクルが存在する場合でも、最終的にはターゲットを見つけます。
簡単に言え
ば、グラフにサイクルが含まれる可能性があり、DFS を使用している場合は、サイクルを考慮する必要があります。一方、BFS は、効率を犠牲にしてサイクルを無視するオプションを提供します。これは、少数のノードを検索する場合に受け入れられることがよくあります。