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

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

幅優先検索 Breadth-first search

　算法の二つ目のコラムでは、幅優先検索を扱います。筆者としては、幅優先検索は深さ優先検索と比べると消費するメモリが多い傾向があるなどのために、使いにくく感じていますが、アルゴリズムとしてはデータ構造としてキューが使えるのであれば、とても簡単に実装できるという利点があります。
　なお、グラフ、無向グラフ、有向グラフ、ノード、エッジなどの用語については、算法の一つ目のコラムで説明していますので、そちらをご覧ください。

　幅優先検索は、有向グラフ上の同じ高さのノードを優先してたどっていき、同じ高さのノードをすべて処理したら、次に一つ低い高さのノードを優先してたどっていくアルゴリズムです。同じ高さのノードを優先して探索していくので、幅優先検索と呼ばれています。目的のノードを検索したり、 ある階層にあるノードを全て求めるときに使用するアルゴリズムです。 アルゴリズム自体は、いろいろなところで説明されていますが、使い道については、あまり説明されていないようなので、どんなものに利用できるのかについて、 まず説明しようと思います。利用例としては、まず、探している駅がある路線に含まれるかどうかとか、3回乗り換えることで到達できる駅を全部あげるなどが考えられますが、駅がある路線に含まれるかどうかはハッシュ法などの別のアルゴリズムのほうが得意そうです。3回乗り換えることによってという問題は、幅優先検索のアルゴリズムそのものなので適していると思います。

　前置きが長くなってしまいましたが、幅優先検索について説明します。
　まず、下の図を見てください。下の図は、有向グラフに幅優先検索を適用した例です。スタートノードは、1番のノードで、同じ階層のノードがなくなったら（とは言っても1番のノードの階層にはノードが一つしかありませんが）、下の階層のノードについて処理していき、下の階層のノードがなくなったら処理を終了します。

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

BFS（ノード） ｛

　パラメタで渡されたノードをキューに積む。

　キューに積まれたノードがある限り以下を繰り返す。｛
　　キューからノードを一つ取り出し、ノードにつながれたすべてのエッジの行き先のノードをキューに積む。
　　ノードに関する目的の処理（例えば、検索していたノードかどうかの判定など）を行う。
　｝
　呼び出し元に復帰する。
｝

　下の図では、上の疑似プログラムがノードを処理する順番を番号で示しています。１から始まり、２、３とアルゴリズムの名前の通り同じ階層にあるノードを優先して進みます。ノード8でこれ以上処理するノードがキューになくなると、アルゴリズムを終了します。非常に単純なアルゴリズムなのですが、ノードがもし2階層しかなく、2階層目に大量のノードがあると、１のノードを処理した時に、1以外の全てノードをキューに積むことになってしまい、作業領域を大量に消費します。

　上の説明では、グラフがループしている場合に、処理が無限ループしてしまうという問題があります。これを避けるためには、既にキューに積まれているノードをキューに積まない仕掛けが必要となります。なお、この仕掛けを使う場合には、複数のノードから到達できるノードがあった場合に、そのノードは一回しか処理されませんから、すべてのルートを調べるというような目的の場合には、正しい答えが得られません。正しい答えを得るためには、さらに工夫が必要となります。

　幅優先検索は、一般的に深さ優先検索と比べて作業領域を多く必要としますが、プログラムの構造は単純で済みます。それぞれに長所短所があるので、特徴を生かした使い方が必要になります。