DFS

- 深さ優先探索とは？深さ優先探索は、迷路やパズルのように複雑に入り組んだ経路の中から、特定の目的地への道筋を見つけるための方法です。まるで糸を手繰るように、まずは一つの道を可能な限り深く進んでいきます。もし行き止まりにぶつかってしまったら、引き返すのではなく、糸をたどりながら、前に分岐があった場所まで戻ります。そして、まだ進んでいない別の分岐を選び、再び深く進んでいくことを繰り返します。 例えるなら、広大な樹木の中を探索する様子を想像してみてください。深さ優先探索は、まず幹から一本の枝を選び、その枝の先端までたどり着くまで、ひたすらその枝を登り続けます。もし先端に行き着いても目的の果実が見つからなければ、分かれ道まで降りてきて、まだ探索していない別の枝を選び直します。そして、再びその枝の先端まで登っていくことを繰り返します。 このように、深さ優先探索は、とにかく深く掘り下げていくことに重点を置いた探索方法と言えます。目的の場所までの距離が分からなくても、根気強く探索を続けることで、最終的には目的地にたどり着くことができる点が大きな特徴です。