深さ優先探索をPythonで書く - Qiita

概要 勉強のため深さ優先探索をPythonで書いてみます。 ごく簡単な迷路のようなもののルート算出を深さ優先探索で対応します。 元々デザイン方面の学校卒なので、コンピューターサイエンス方面で知識的に雑な点などはご容赦ください。 深さ優先探索とは？ 深さ優先探索とは「とにかく行けるとこまで行ってそれ以上進めなくなったら一歩戻ってそこから探索する」という探索方法。 深さ優先探索と幅優先探索 たとえばグリッド上の迷路で考えてみます。上端のグリッドに迷路の入口があり、下端のグリッドに迷路の出口があるとします。 途中途中に通路の分岐や行き止まりもあるとします。 こういった際に進めるだけ先に進んで（深さ優先）、もし行き止まりで進めなくなったら直前の通路の分岐まで戻ってその分岐を進んで出口を目指すような探索方法です。 英語だとdepth-first search、略してDFSなどと表記されます。 解くべ