深さ優先探索について詳しく知りたいです！
一つ一つ手順を見ていけば理解できるようになるので一緒に学んでいきましょう！
深さ優先探索とは
深さ優先探索(Depth First Search)とは、木構造やグラフの探索を行う代表的な探索の一つです。
グラフ中の点や辺を複数参照することで目的の要素を見つける操作をします。
グラフを探索するときの基本的な操作を説明していきます。
深さ優先探索と一緒によく取り上げられる幅優先探索について学びたい方はこちらをクリック↓
今回は以下の迷路を探索することにします。
「a」はそれぞれ点の名称、「Z」は辺の名称となっています。
スタート地点は「a2」とします。
深さ優先探索の参照の流れ
1.まず参照する時には、辺で繋がっていて参照したことのない点に行く。
「a2」に繋がっている点は「a1」,「a3」と複数ありますが、確認だけしておき探索するのはどちらか片方だけします。
まずは左側の「a1」にします。
2.参照をした点から、まだ参照していないもので、参照できる点を探す。
幅優先探索と違って、「a2」から「a3」がまだ参照できますが、参照した点である「a1」から参照できる点があれば、先に参照をします。
「a1」から「a5」が参照できるので「a5」を先に参照します。
3.参照を繰り返し行なっていく。参照できなくなった時は、前に参照できる点があった場合はその点を参照する。
次は同じように「a5」から参照できる点を参照します。
以降同じように続いていきます。
最終的に探索し終えると以上の図になります。
特徴として、特定の細部を次々と探索しています。
幅優先探索では全体像を掴んでいくように探索しますが、深さ優先探索では特定の辺で繋がっているものを行き止まりが出るまで探索していく手法になります。
深さ優先木
おまけとして、深さ優先探索でどのように探索していったかがわかる深さ優先木を載せておきます。
まとめ
探索の代表的なものの一つである深さ優先探索を紹介しました！
落ち着いてみれば簡単な内容になっていますので、わからなかった場合はステップごとに切り分けて考えてみましょう。
よく迷路の探索アルゴリズムにも使われたりするので、覚えておくのも良いでしょう。
