「深さ優先探索」と「幅優先探索」を初めて勉強したとき,これらの探索の動きを比較するためにMacのFinderを使ったディレクトリの探索で例えると分かりやすかった.当時やってたことをここに書いてみる.
例えば,以下のような木が与えられたとする.

ここで「ノード「f」は存在するか?」という問いの設定で木を探索していくことを考える.この絵を見れば,木の全体を一気に見れるため,「存在する!」ということはほぼ一瞬で分かる.しかし,プログラムは木を一気には見れないため,ノードを1つずつ辿って見ていくことになる.深さ優先探索と幅優先探索とでは,辿る順番が異なる.
準備
上の木は,下のようなディレクトリ構造として表すことができる.ノードはフォルダ.

ノードを辿るというのは,フォルダを開けることに対応する.表記が「▼ フォルダ名」となっているものは訪問済みであるノードであると言える.(「▶ フォルダ名」の段階では,まだ訪問されていない,スタックやキューに積まれている状態)
深さ優先探索
一度開けたフォルダが開けなくなるまで開き続けていくという順番で探索する.
まずはe
について:

e
より深いところでこれ以上開けなくなったところで,q
へ:

最後にw
について:

これで,探索完了.
幅優先探索
順番に1階層ずつ開いていく方法.まずは,ルートから数えて1階層目を開く:

続いて2階層目:

3階層目:

4階層目:

5階層目:

これで,探索完了.

gifアニメーション溢れるページになった.