岩通ソフトシステム株式会社はソフトウェア開発からサービスまでをトータルで提供するソリューションプロバイダです。

　算法は、数学的には計算の方法を表すそうですが、情報処理の世界ではアルゴリズムを表すことになっています。とはいっても、 算法という言葉は、情報処理の世界では、ほとんど使われなくなっていますので、言葉自体を知っている人も少なくなってきています。今はアルゴリズムと呼べば、みんなが理解できると思います。
　アルゴリズムを使う利点ですが、多くは簡単には解決できない問題を解決していて、その解法が正しいことが証明されており、さらに無料で使うことができるということだと思います。自分でアルゴリズムから考えていたら、いくら時間があっても足りないので、先人の知恵を借りるということになります。

深さ優先検索 Depth-first search

　筆者は、10年以上にわたってプログラムを使いアルゴリズムを実現してきました。与えられたテーマの関係で、ほとんどがグラフ理論のアルゴリズムで、 有向グラフを扱ったものでした。無向グラフと有向グラフを下図に示します。グラフとは、丸で表されるノード（下図で１，２，３と番号が記述された丸）と丸を結ぶ線で表されるエッジから構成されるモデルで、 有向グラフとは丸を結ぶ線の部分が矢印となり行ける方向を示すモデルを表し、無向グラフはエッジに方向性がないモデルを指します。筆者が何回か使うチャンスがあったアルゴリズムに、深さ優先検索（depth-first search）というものがあり、最近ではWikipediaでも、取り上げられているので、かなりポピュラーなアルゴリズムとなっています。

　深さ優先検索は、有向グラフ上のノードをエッジに従ってたどっていき、目的のノードに到達するパスを求めたり、 あるノードからあるノードに向かうパスがいくつあるかを計算するときに使用するアルゴリズムです。 アルゴリズム自体は、いろいろなところで説明されていますが、使い道については、あまり説明されていないようなので、どんなものに利用できるのかについて、 まず説明しようと思います。利用例としては、まず、電車の乗換案内のような、全ルートを洗い出して、一番早いルートや一番安いルートを探すというものであります。この場合には、各エッジに発車時刻、到着時刻、料金などのデータをあらかじめ格納しておいて、そのデータを深さ優先検索をしながら比較するということになります。ただし、一番早いや一番安いルートを探索するのであれば、ダイクストラ法の方が適していますが。また、別の利用例としては、プログラムのテストカバレッジのように、我々が書くプログラムについて何種類のルートを持っていて、 全てのルートの組合せをテストするには、何通りのルートや組合せを通さなければならないかという問題を解くのにも適しています。筆者の場合には、まさに、このすべてのルートを導き出すことに使用したこともありますし、別な適用ではネットワーク経路のコスト計算や予約などを行う処理に使用しました。

　前置きが長くなってしまいましたが、深さ優先検索について説明します。
　まず、下の図を見てください。下の図は、上の図の有向グラフに深さ優先検索を適用した例です。スタートノードは、1番のノードで、これ以上進めなくなった（つまり、4番のノードに到達した）ら、別のルートを探しに行き、別のルートがなくなったら処理を終了します。

　疑似プログラムで処理を説明します。前提として、各ノードは複数のエッジをリンクできるデータ構造を持っており、各エッジは行き先のノードをリンクできるデータ構造を持っているものとします。また、到達経路を格納するために十分な領域を持っているものとします。

DFS（ノード） ｛

　渡されたノードを到達経路に格納する。

　渡されたノードのすべてのエッジについて繰り返す。｛
　　エッジの行き先のノードを求め、エッジとノードを到達経路を示す領域に格納する。
　　行き先ノードをパラメタとしてDFSを再起呼び出しする。
　　ループの先頭で格納した到達経路を削除する。
　｝
　ノードにエッジが一つもなければ、目的地に到着したので、到達経路の情報を使用して目的の処理（例えば見つけたルートの印刷など）を行う。
　プログラムの先頭で格納した到達経路を削除する。
　呼び出し元に復帰する。
｝

　下の図では、上の疑似プログラムがエッジを処理する順番を番号で示しています。１から始まり、２、３とアルゴリズムの名前の通り深い方を優先して進みます。ノード4でこれ以上進めなくなると、４でバックトラックし、まだ選んでいないのノード３から出ているエッジを５で選んで処理し、ノード4でこれ以上進めなくなりますから、６、７、８とバックトラックし、ノード１から出ているまだ選んでいないエッジを９で選びます。あとは１で選んだノード2に進んだ以降の処理と同じ処理を行います。なお、実際には、ノードから出ているエッジが複数ある場合には、どのエッジを先に処理しても構いません。また、図中の赤色の線は、再起呼び出しを行うポイントを示しています。

　上の説明では、グラフがループしている場合に、処理が無限ループしてしまうという問題があります。これを避けるためには、現在の通ってきた経路を構成するエッジに通過マークを付けて、既に通過マークがついているエッジを選ばないようにすれば避けることができます。また、同じところに戻ってくるループ（東京駅から山手線を一周して、また東京に戻り、そこから地下鉄に乗るようなケース）を通らないようにするのであれば、通過ノードにマークをつけて既に通過したノードは通らないようにするなどを考慮する必要があります。また、プログラムのカバレジの場合には、ループしないルートしか選ばないようにすると問題になりますので、例えば、0回、1回、2回・・・ループを回すという考え方をする必要があります。

　深さ優先検索は、一般的に幅優先検索と比べて作業領域が少なくて済み、C言語のようにスタックがあり再起呼出しが行える場合には、比較的簡単に実装することができます。ただし、再起呼出しが行えず、スタックがない実行環境でも、実装は、それほど難しくないと思います。