読者です 読者をやめる 読者になる 読者になる

daiizの自由帳

フレンチフライ トリュフ塩仕立て

深さ優先探索と幅優先探索

メモ tech

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

例えば,以下のような木が与えられたとする.

f:id:daiiz:20160427012631p:plain:w480

ここで「ノード「f」は存在するか?」という問いの設定で木を探索していくことを考える.この絵を見れば,木の全体を一気に見れるため,「存在する!」ということはほぼ一瞬で分かる.しかし,プログラムは木を一気には見れないため,ノードを1つずつ辿って見ていくことになる.深さ優先探索と幅優先探索とでは,辿る順番が異なる.

準備

上の木は,下のようなディレクトリ構造として表すことができる.ノードはフォルダ.

f:id:daiiz:20160427013419p:plain

ノードを辿るというのは,フォルダを開けることに対応する.表記が「▼ フォルダ名」となっているものは訪問済みであるノードであると言える.(「▶ フォルダ名」の段階では,まだ訪問されていない,スタックやキューに積まれている状態)

深さ優先探索

一度開けたフォルダが開けなくなるまで開き続けていくという順番で探索する.

まずはeについて:

https://i.gyazo.com/5cd4c39428176031ab46b63cc092a961.gif

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

https://i.gyazo.com/c62db6dd958090825c97b93882892466.gif

最後にwについて:

https://i.gyazo.com/24940b4c42413a514b7cdceab36bbbc8.gif

これで,探索完了.

幅優先探索

順番に1階層ずつ開いていく方法.まずは,ルートから数えて1階層目を開く:

https://i.gyazo.com/48043bd3c7eb349ed139a5e858404ad4.gif

続いて2階層目:

https://i.gyazo.com/bc87cf90c2284a43c476600ffc272cf3.gif

3階層目:

https://i.gyazo.com/0d7f8c65a7279604527af0e77ba4b398.gif

4階層目:

https://i.gyazo.com/e64318577752362d88a75880aa9260e0.gif

5階層目:

https://i.gyazo.com/b961746e7689c6bff3be3dc37f738b6b.gif

これで,探索完了.

f:id:daiiz:20160320041319p:plain:h65

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