木構造の探索（幅優先・深優先）
意味・解説
ツリー構造（木構造）の全ノードを訪問するための2つの主要な手法。横方向に進む幅優先探索と、縦方向に突き進む深優先探索。
幅優先探索(BFS)はキュー(FIFO)を用い、ルートに近い順に探索する。深優先探索(DFS)はスタック(LIFO)を用い、リーフ（葉）に到達するまで深く探索する。計算量はいずれもノード数$N$に対して $O(N)$ となる。
くわしく
「迷路の解き方」の戦略の違いです。
1.幅優先探索：
根から近い階層を全て調べてから次へ進みます。最短経路を見つけるのに適しています。
2.深優先探索：
行けるところまで深く進み、行き止まったら戻ります。メモリ消費を抑えやすく、パズルやチェスの先読みに使われます。ポイントは、AIの探索アルゴリズムやネットワークの経路計算、ファイルシステムの検索など、コンピュータサイエンスのあらゆる基盤となる動きだからです。
例文
ディレクトリ構造の全ファイルを検索する際、メモリ使用量を抑えるために深優先探索アルゴリズムを採用した。
同義語: 走査 (Traversal)
分類: グラフ理論 / 探索アルゴリズム