現代ではコンピュータはとても身近なものになりました。コンピュータの用途としてはシミュレーションなどの大規模計算を行う人工知能をつくるアプリを開発するなどなど多様なものが考えられますが、「探索」もまた、コンピュータを用いるモチベーションとして、最も基本的かつ重要なものの一つだと思います。探索とは、与えられた対象の中から、目的に合うものを見つけ出したり、最良のものを見つけ出したり、条件を満たすものを列挙したりする営みです。世の中における様々な問題は、探索によって、考えられる場合を調べ尽くすことによって原理的には解決できるものが多いです。﻿例えば、現在地から目的地まで最速でたどり着く方法を求める問題は、原理的には、現在地から目的地へ到達する経路をすべて列挙することで解決できます1。将棋やオセロの必勝法を求める問題は、原理的には、考えられる局面と局面遷移をすべて調べ上げることで求めることができます2。確かに実際上は、ありうる場合の数が膨大なために全探索手法の適用が困難なことも多いのですが、まずは「どうしたらすべての場合を調べつくせるか」を検討することは大変重要です。全探索アルゴリズムを考案することによって、解きたい問題の構造に対する深い理解を獲得し、結果的に高速なアルゴリズムの設計へと結ぶ付くことは珍しくないです。考えられる選択肢をすべて調べ上げる方法として「問題をグラフを用いて定式化する」という手法がしばしば極めて有効です。本記事ではグラフ上の探索、特に深さ優先探索について、色々な問題を解くことを通して慣れることを目指します。動的計画法などもそうですが「習うより慣れろ」の精神が大きな効果を生むテーマだと思います。本記事の構成は上のようになっています。章でグラフを計算機上でどのように扱うのがよいかについて述べています。章ではグラフ上の探索アルゴリズムについて一般的な話を書いています。章から入っていただけたらと思います。章が本記事の特徴をなすメインパートでグラフ探索に関する多数の例題を解いていきます。焦点を当てた記事も書きました。(先例では、知り合い関係)を表すものです。グラフは下図のように「丸」と「線」を用いて描画されることが多いです。対象物を丸で、対象物間の関係性を線で表します3。念のために、グラフを数学的に定義してみます。