このページでは、基本的な探索アルゴリズムである「深さ優先探索」と「幅優先探索」について解説していきます。
Contents
深さ優先探索
まずは、深さ優先探索について解説していきます。
深さ優先探索とは
深さ優先探索とは、その名の通り、深さを優先して探索するアルゴリズムになります。もう少し噛み砕いて言えば「スタートからの距離が遠い候補を優先しながら探索対象を探索するアルゴリズム」になります。
スポンサーリンク
深さ優先探索で迷路を解く
深さ優先探索は「迷路でゴールを探索する例」で考えるとイメージが湧きやすいと思います。
例えば、下の図の迷路でスタート（S のマス）からゴール（G のマス）を探索する例について考えてみましょう！
白色のマスは通路を表しており、灰色のマスは壁を表しています。通路は通過可能ですが、壁は通過不可となります。また迷路外に出ることもできません。
これくらいの迷路であれば、頭の中でスタートからゴールまでの経路が一瞬で描けるのではないかと思います。が、実際にあなたが迷路のスタートにいると仮定し、さらにゴールの位置が実際に探索しないと分からないという前提がある場合、どのように試行しながらゴールを目指すのかについて考えてみていただくと、深さ優先探索のイメージが湧きやすいと思います。
深さ優先探索でゴールを探索する場合は、下記のような手順で探索を行うことになります。
まず、迷路の開始はスタートのマスになります。横方向の座標を i、縦方向の座標を j とすれば、各マスの座標は (i, j) で表すことができることになり、迷路におけるスタートのマスは座標 (3, 3) ということになります。
ということで、スタートの座標 (3, 3) のマスがゴールであるかをまず確認します。ゴールであれば探索は完了となります（今後も、移動後のマスで毎回ゴールであるかどうかの確認を行うことになるのですが、この確認については以降の説明では省略します）。
ゴールでなかった場合は、次の探索先のマスを決定して移動し、同様に探索を試行していくことになります。この次の探索先の決め方が深さ優先探索と幅優先探索との違いになります。
今回の迷路の場合、スタート地点は分岐路になっており、次の探索候補としては、スタート地点から上下左右方向に１マスだけ移動した次の４つのマスが挙げられます（前述の通り (3, 3) はスタートの座標です）。
- (
3,2)：(3,3) から上方向に１マス移動したマス - (
3,4)：(3,3) から下方向に１マス移動したマス - (
2,3)：(3,3) から左方向に１マス移動したマス - (
4,3)：(3,3) から右方向に１マス移動したマス
図で考えると、下の図の迷路における青マスになります。また、現在の探索位置はオレンジマスで示しています。
前述の通り、深さ優先探索は「スタートからの距離が遠い候補を優先しながら探索対象を探索するアルゴリズム」です。で、ここで挙げられた４つの候補は全てスタートからの距離が等しいマスとなります。
こういった「スタートからの距離が一番遠い探索候補」が複数存在する場合は、それらの中のどの探索候補を次の探索先に選んでも問題ありません。つまり、上記の４つの候補のうちのどれを選んでも良いことになります。今回はスタートの上側のマスである (3, 2) を次の探索先としたいと思います。
移動後のマスは分岐路ではなく、進めるマスは上方向と下方向の２つになります。
ですが、下方向に進んだ場合は探索済みのマスに戻ることになります。探索済みのマスに戻ってしまうと、また同じ経路を辿ってゴールを探索することになってしまうため、探索済みのマスは探索候補から除外するようにします（図では探索済みのマスは濃いグレーのマスで表現していきたいと思います）。
さて、ここで今までに見つけた探索候補を整理すると下記の４つとなります。(3, 3) と (3, 2) に関しては既に探索済みのマスなので、候補からは除外されることになります。
- (
3,4)：(3,3) から下方向に１マス移動したマス - (
2,3)：(3,3) から左方向に１マス移動したマス - (
4,3)：(3,3) から右方向に１マス移動したマス - (
3,1)：(3,2) から右方向に１マス移動したマス
図で考えると、下の図の迷路における青マスになります。
そして、前述の通り、深さ優先探索は「スタートからの距離が遠い候補を優先しながら探索対象を探索するアルゴリズム」です。
ここで、上記の４つの候補それぞれにおけるスタートからの距離について考えると、(3, 1) のみはスタートからの距離が２マス分であるのに対し、他の候補はスタートからの距離が１マス分となります。そのため、深さ優先探索でゴールを探索する場合、次の探索先は「スタート地点からの距離が一番遠い候補」である (3, 1) のマスとなります。
そして、(3, 1) を探索することで、また新たな探索候補 (3, 0) が見つかることになります。次は、その新たな探索候補 (3, 0) を含めて次の探索先を決めます。この際にも、今まで通り「スタート地点からの距離が一番遠い候補」を選ぶことになります。つまり、(3, 1) のマスの次の探索先は (3, 0) のマスとなります。
このように、深さ優先探索においては、今まで見つけた候補のうち、スタート地点から一番距離が遠い候補を優先して選択しながら探索を行なっていくことになります。
もう少し迷路におけるゴールの探索を進めてみましょう！
この深さ優先探索の考え方に従って探索を進めていくと、次は下の図のようにまた新たな分岐路に出くわすことになります（この時点の探索候補は青マスで示しています）。
この時点での探索候補のマスは下記の５つになります（前述の通り、一度探索した通路は候補に入れません）。
- (
3,4)：(3,3) から下方向に１マス移動したマス - (
2,3)：(3,3) から左方向に１マス移動したマス - (
4,3)：(3,3) から右方向に１マス移動したマス - (
5,1)：(5,0) から下方向に１マス移動したマス - (
6,0)：(5,0) から右方向に１マス移動したマス
また、現在位置の分岐路である (5, 0) はスタート地点から５マス分離れた位置なので、下側２つのマスである (5, 1) と (6, 0) は共にスタート地点から６マス分離れた位置となります。それに対し、上側３つのマスはスタート地点からの距離が１マス分のみです。したがって、これらの候補の中でスタート地点からの距離が一番遠い候補は (5, 1) と (6, 0) ということになります。
さらに、(5, 1) と (6, 0) に関してはスタート地点からの距離は同じなので、この場合はどちらの候補を次の探索先に選んでも問題ありません。今回は、次の探索先に (5, 1) を選びたいと思います。
この場合、次は下の図のように行き止まりに出くわすことになります。
ちょっと今までと異なるケースですね！行き止まりのマスを探索した場合、新たな次の探索候補は見つからなかったことになります。ですが、次の探索先の決め方は今までと同じです。つまり、現時点の探索候補の中で「スタート地点からの距離が一番遠い候補」を選べば良いです。
今回は、先ほどの分岐路における右方向のマス (6, 0) が「スタート地点からの距離が一番遠い候補」となりますので、(6, 0) のマスに進み、また同様の考え方でゴールを探索していくことになります。
このように行き止まりに到達したとしても、次の探索先の決め方は他のケースと同じです。つまり、いかなる場合でも探索候補の中から「スタート地点からの距離が一番遠い候補」を優先して次の探索先を選択していけば良いだけです。このようにして探索を行うアルゴリズムが深さ優先探索になります。
スタートからゴールに到達可能である場合、いずれはゴールが見つかり、ゴールの探索に成功することになります。スタートからゴールに到達不可である場合は、いずれは探索候補が存在しなくなり、その時点でゴールの探索に失敗することになります（スタートから到達できる全てのマスを調べたがゴールが見つからなかった）。
グラフで深さ優先探索を考える
先ほどは迷路の例を用いて深さ優先探索について考えましたが、一般的には探索アルゴリズムは下の図のようなグラフを用いて説明されることが多いです。
グラフにおける、一番上側のノード（根ノード）がスタートを表しています。また、各ノードが探索候補を表しており、ノード間にエッジ（枝）がある場合、互いのノードから他方のノードに辿ることが可能であることを表しています。つまり、一方のノードを探索した際に、他方のノードが新たに探索候補として見つかることを表しています。
このようにグラフで表した場合、深さ優先探索では名前の通り、深さを優先して探索を行なっていきます。つまり、今まで探索を行なったノードから辿れるノードのうち、一番深い位置にあるノードを優先して探索を行います。
迷路の時と異なる言い方をしていますが、上記のように探索を行えば、スタート（根ノード）からの距離が遠いノードが優先されて探索が行れていくことになり、実質的に迷路の時と同じような考え方で探索を行うことになります。
例えば、この節の最初に見せたグラフの場合、下の図の青字で示す順番で各ノードが探索されていくことになります。途中で探索対象が見つかった場合は、その時点で探索は終了となります（他の経路を試しても良いですが）。
こういったグラフは迷路と全く関係ないようにも思えますが、実は迷路はグラフで表すことが可能です。例えば下の図における右側のグラフは左側の迷路をグラフ化したものになります。
迷路の各マスに数字を割り振っており、各マスがグラフにおける同じ数字が割り振られたノードに対応しています。
例えば、迷路におけるマス 0 はマス 1 〜 マス 4 に辿る事が可能です。このマス 0 はグラフのノード 0 に対応しており、このノードからもノード 1 〜 ノード 4 に辿る事が可能です。他のマスやノードも同様に、同じマス（同じノード）に辿れるようにそれぞれが対応している事が確認できると思います。
このようにグラフ化できるの迷路だけではありません。様々な探索問題をグラフとして表すことができます。つまり、グラフに対する探索を実現しておけば、様々な探索問題を解くことができるようになることになります（探索問題をグラフ化し、グラフに対して探索を行う）。
ページの後半で深さ優先探索（および幅優先探索）のサンプルプログラムを紹介しますが、そこでは迷路に対して深さ優先探索を行う例だけでなく、グラフに対して深さ優先探索を行う例も紹介していきたいと思います。
幅優先探索
次は、幅優先探索について解説していきます。
スポンサーリンク
幅優先探索とは
幅優先探索とは、深さ優先探索とは逆で、探索候補の中から「スタートからの距離が近い候補を優先しながら探索対象を探索するアルゴリズム」になります。
幅優先探索で迷路を解く
幅優先探索に関しても、深さ優先探索同様に迷路の例で考えていきたいと思います。
幅優先探索でゴールを探索する場合は、下記のような手順で探索を行うことになります。
まず、迷路の開始はスタート地点になります。つまり、スタートは (3, 3) のマスになります。また、今回の迷路の場合、スタート地点は分岐路になっており、次の探索先の候補としては、スタート地点から上下左右方向に１マスだけ移動した下記の４つマスが挙げられます。
- (
3,2)：(3,3) から上方向に１マス移動したマス - (
3,4)：(3,3) から下方向に１マス移動したマス - (
2,3)：(3,3) から左方向に１マス移動したマス - (
4,3)：(3,3) から右方向に１マス移動したマス
図で考えると、下の図の迷路における青マスになります。また、現在の探索位置はオレンジマスで示しています。
前述の通り、幅優先探索は「スタートからの距離が近い候補を優先しながら探索対象を探索するアルゴリズム」です。で、ここで挙げられた４つの候補は全てスタート地点からの距離が等しいマスとなります。
なので、深さ優先探索同様に、幅優先探索においても、これら４つの候補のうちのどれを選んでも問題ありません。今回は上方向のマスである (3, 2) を次の探索先に選択したいと思います。
移動後のマスは分岐路ではなく、進めるマスは上方向と下方向の２つになります。ですが、これも深さ優先探索同様に、通過済みのマスは次の探索候補から除外します。
ここで今までに見つけた探索候補を整理すると下記の４つとなります（探索済みのマスは除外しています）。
- (
3,4)：(3,3) から下方向に１マス移動したマス - (
2,3)：(3,3) から左方向に１マス移動したマス - (
4,3)：(3,3) から右方向に１マス移動したマス - (
3,1)：(3,2) から右方向に１マス移動したマス
図で考えると、下の図の迷路における青マスになります。
そして、前述の通り、幅優先探索は探索候補の中から「スタートからの距離が近い候補を優先しながら探索対象を探索するアルゴリズム」です。そのため、幅優先探索でゴールを探索する場合、次に進むマスは「スタート地点からの距離が一番近い候補」である (3, 4)、(2, 3)、(4, 3) のいずれかとなります。
ただし、これら３つのマスは全てスタート地点からの距離が同じなので、どれを選んでも問題ありません。
今回は下方向の (3, 4) を探索したいと思います。(3, 4) を探索した際には、新たに (3, 5) のマスが探索候補として見つかることになります。
ここで現時点の探索候補を整理すると下記の４つとなります。
- (
2,3)：(3,3) から左方向に１マス移動したマス - (
4,3)：(3,3) から右方向に１マス移動したマス - (
3,1)：(3,2) から右方向に１マス移動したマス - (
3,5)：(3,4) から下方向に１マス移動したマス
次の探索先も同様の考え方で決めることになりますので、スタート地点から一番距離が近い候補は (2, 3) と (4, 3) のマスの一方を探索することになります。そして、その次に探索を行うのは他方側のマスということになります。
こんな感じで、幅優先探索の場合は、最初にスタート地点で見つけた探索候補が優先して探索されていくことになります。スタート地点で見つけた探索候補が全て探索された際に、続いてスタート地点から次に近い探索候補が優先されて探索されていくことになります。
つまり、(2, 3) と (4, 3) のマスの両方が探索が完了された際には、スタートから１マス分のみ離れたマスが探索候補から全て除外されるため、次はスタートから２マス分のみ離れたマスが優先して探索されていくことになります（下の図における青マス）。
同様のことを繰り返せば、先にスタート地点から距離が近い候補が探索されていき、次第にスタート地点から距離が遠い候補が探索されていくことになります。
スタート地点からゴールに到達可能である場合、上記の考え方で探索を行えばいずれはゴールに到達して探索が完了することになります。スタートからゴールに到達不可である場合は、いずれは次に辿れる探索候補が存在しなくなり、その時点でゴールの探索に失敗することになります（スタートから到達できる全てのマスを調べたがゴールが見つからなかった）。
このように、候補の中から「スタートからの距離が近い候補を優先しながら探索対象を探索するアルゴリズム」が幅優先探索になります。
グラフで幅優先探索を考える
深さ優先探索 でも解説したように、迷路のような探索問題はグラフで表現することができます。
そして、深さ優先探索では深い位置のノードを優先するのに対し、幅優先探索においては浅い位置のノードを優先して探索が行われることになります。
深さ優先探索が縦方向にどんどん探索を進めていくのに対し、幅優先探索は横方向に幅をどんどん増やす形で探索を進めていくことになります。そのため、幅優先探索と呼ばれています。
例えば、上の図におけるグラフの場合、下の図の青字矢印で示す順番で探索が行われることになります。
スポンサーリンク
深さ優先探索と幅優先探索の違い
深さ優先探索と幅優先探索の探索の仕方については理解して頂けたでしょうか？
次は、深さ優先探索と幅優先探索の違いに焦点を当てて解説をしていきたいと思います。
優先する候補の違い
深さ優先探索と幅優先探索における探索の仕方の違いは１点のみです。
この違いは優先する候補の選び方であり、深さ優先探索が「スタートから距離が遠い候補」を優先して次の探索先として選択するのに対し、幅優先探索では「スタートから距離が近い候補」を優先します。
探索の仕方の違いが「優先する候補の選び方のみ」であるため、実装に関しても違いは「優先する候補の選び方のみ」となります。この点に関しては、後述の 深さ優先探索の実装 と 幅優先探索の実装 で詳細を解説します。
最初に見つかる経路の違い
ただし、優先する候補の選び方異なるため、探索結果や探索の効率等が深さ優先探索と幅優先探索とに違いがあります。
幅優先探索：最初に見つけた経路が最短経路となる
一番特徴的な違いは「最初に見つかる経路」になると思います。
幅優先探索は、前述の通りスタートから距離の近い候補を優先して探索を行うことになります。距離の近い候補を先に探索することになるため、幅優先探索によって最初に探索対象が見つかった場合（迷路の場合はゴールが見つかった場合）、その探索対象を見つけるまでに経由した経路はスタートから探索対象までの最短経路となります。
深さ優先探索：最初に見つけた経路が最短経路とは限らない
その一方で、深さ優先探索の場合は、距離の近い候補を優先して探索するアルゴリズムではないため、最初に見つかった探索対象までの経路はスタートから探索対象までの最短経路とは限りません。
例えば下の図のような迷路に対してゴールの探索を深さ優先探索で行なった場合、スタート地点で見つけた探索候補の中から最初に上方向のマスを選んでしまうと、青矢印の経路を辿って探索が行われることになります。
この経路でもゴールの探索には成功するのですが、図を見れば明らかなように、この青矢印の経路は最短経路ではありません。
それに対し、スタート地点で見つけた探索候補の中で最初に右方向のマスを選んだ場合、緑矢印の経路を辿って探索が行われることになり、この場合、スタート地点からゴールまでの経路は最短経路となります。
このように、深さ優先探索を実行した場合、最初に見つけた探索対象への経路が最短経路であるとは限りません。具体的に言えば、「スタートからの距離が同じ候補」が複数存在する場合、そのうちのどれを優先して選ぶのかによって、最初に見つけた探索対象への経路が最短経路であるかどうかが変わってしまいます。
そのため、深さ優先探索で最短経路を見つけたい場合は、まず探索対象への全経路を洗い出し、その全経路のスタートから探索対象までの距離を調べる必要があります。つまり、最短経路を見つけ出すためには全探索を行う必要があります。
ですので、最短経路を見つける目的で探索を行うのであれば幅優先探索を行う方が効率が良いです。
スポンサーリンク
探索の失敗の有無
探索候補の数が有限である場合、深さ優先探索においても幅優先探索においても、スタートから探索対象に到達可能であれば理論的には必ず探索に成功します。
ただし、プログラムで探索を行う場合、時間的 or メモリ使用量的に探索に失敗することもあり得るので注意してください。例えば迷路のマス数が多すぎると探索候補となるマス数が多くなり、それを記録するためのメモリが足りなくなる可能性もあります。また、迷路のマスが多すぎると探索に時間がかかりすぎて探索が完了しないよう可能性もあります。
このように、現実的には探索に失敗する場合もあるのですが、理論的には、前述の通り、探索候補の数が有限である場合、深さ優先探索においても幅優先探索においても、スタートから探索対象に到達可能であれば探索に成功することになります。
深さ優先探索では探索に失敗することもある
ですが、探索候補の数が無限である場合、スタート地点から探索対象が到達可能であったとしても、深さ優先探索では探索に失敗することがあります。
例えば、下の図のような迷路では無限に続く経路が存在することになります。現実世界では実現不可な迷路かもしれませんが、ゲームの世界などではこういった迷路やマップは結構存在するのではないかと思います。
この迷路の場合、深さ優先探索を行い、さらにスタート地点から最初に上方向に進んでしまうと無限に続く経路に進んでしまうことになって探索が終了しません。つまり探索に失敗することになります。
深さ優先探索ではスタートからの距離が遠い探索候補が優先して探索されますので、スタート地点から離れれば離れるほど優先度が高くなります。当然、無限に続く経路に入ってしまうと、その方向の探索候補の優先度がどんどん高くなるため、ずっと同じ方向に対して探索が行われることになって探索が終了しないことになります。
幅優先探索では基本的には確実に探索に成功する
それに対し、幅優先探索の場合はスタートからの距離が短い探索候補が優先して探索されますので、上の図のような無限に続く経路のマスの探索優先度が下がり、他のマスの方が優先して探索されることになります。そのため、スタート地点から探索対象に到達可能であれば、いずれは探索に成功することになります（下の図は幅優先探索でゴールを探索した際の各マスの探索順の一例を青字で示したものになります）。
ただし、必ず探索に成功するというのは理論的な話であり、現実的には時間的に or メモリ使用量的に探索に失敗する可能性はあります。
また、幅優先探索の場合でも、スタートから探索対象が到達不可であり、さらに探索候補の数が無限の場合は、探索が永遠に続けられることになってしまいます。つまり探索が終わりません。幅優先探索においても、この点には注意が必要となります。
条件を追加して候補数を有限にすることも可能
実は、このような非現実的な無限に続く経路が存在しない場合であっても、迷路の場合、一度探索したマスも再度探索候補としてしまうような場合には深さ優先探索で探索に失敗してしまう可能性があります（探索候補が減らないので、無限に探索候補が存在することになる）
そのため、深さ優先探索 や 幅優先探索 の説明時には、一度通過したマスは探索候補としない前提の下で探索を実施しました。実は、この前提を加えることで無限に探索されることを防いでいたのです。
この例のように、探索問題によっては条件を加えることで無限に探索されることを防ぎ、深さ優先探索でも確実に探索を行うようなことも可能になります。
探索速度の違い
また、探索速度（時間計算量）の違いもあります。
最短経路が見つける速さは幅優先探索の方が安定する
最初に見つかる経路の違い でも説明しましたが、最短経路を見つける目的で探索を行うのであれば幅優先探索の方が無難だと思います。なぜなら、幅優先探索では「スタート 〜 最初に見つけた探索対象」の経路が必ず最短経路となるからです。
最悪ケースでは同程度
また、探索対象が存在しない場合などの最悪のケースにおいては、幅優先探索・深さ優先探索ともに同程度の探索時間になります。
迷路のケースで考えれば、探索対象が存在しない場合は全ての通路のマスを探索することになるため、通路のマス数分の探索を実施する必要があります。つまり、深さ優先探索でも幅優先探索でも探索に必要な計算量は通路のマスの数に比例することになり、通路のマスの数を N とすれば、計算量のオーダーは O (N) となります。
また、グラフで考えた場合は、エッジの総数を E とすれば計算量のオーダーは O (E) となります。
使用メモリの違い
ここまでの解説を読めば、幅優先探索の方が優れた探索の方にも思えるかと思います。
幅優先探索は最初に見つけた経路が最短経路となり、スタートから探索対象に到達可能である場合、必ず探索対象を見つけることも可能となります（理論的には）。それに対し、深さ優先探索の場合は最初に見つけた経路は最短経路とは限りませんし、スタートから探索対象に到達可能であっても、探索候補の数が無限にあると探索対象を見つけることに失敗する可能性もあります。
上記の点から幅優先探索の方が優れた探索のようにも思えますが、幅優先探索は深さ優先探索に比べて劣っている点があります。それが「使用メモリ量が大きくなる」という点になります。
幅優先探索の場合は指数関数的に使用メモリが増加
幅優先探索においても、深さ優先探索においても、探索候補を覚えておくためのメモリが必要になります。
この使用メモリの量に関してはグラフの構造で考えた方がわかりやすく、各ノードからの分岐の最大数を B、木の深さの最大数を M とした場合、幅優先探索の使用メモリは B の M 乗に比例することになるようです。
つまり、指数関数的に使用メモリが大きくなるため、ノード数が多い場合、例えば迷路であれば通路数が多い場合はメモリが不足して探索に失敗してしまうことがあります。理論的には探索可能でも、メモリという現実的な要素によって失敗してしまうことになります。
深さ優先探索の場合は線形的に使用メモリが増加
それに対し、深さ優先探索の場合の使用メモリ量は B * M に比例することになり、幅優先探索に比べると使用メモリ数が抑えることができます。ですので、幅優先探索に比べるとメモリ不足が原因で探索に失敗する可能性は少なくなります。
この辺りの解説は下記ページで詳しく行われているので参考にしてみてください。
あくまでもイメージですが、深さ優先探索の場合はゴール or 行き止まりを見つけることを優先して探索することになるのですが、幅優先探索の場合は選択肢（探索候補）を見つけることを優先して探索が行われることになり、選択肢を覚えておくためのメモリが大きくなる傾向にあります。
スポンサーリンク
深さ優先探索の実装
続いては、深さ優先探索の実装方法および、サンプルプログラムについて紹介していきたいと思います。
深さ優先探索の実装方法
深さ優先探索 でも解説したように、深さ優先探索とは「スタートからの距離が遠い候補を優先しながら探索対象を探索するアルゴリズム」です。
これは「後から見つけた探索候補を優先しながら探索対象を探索するアルゴリズム」と言い換えることができます。
スタートからの距離が遠い候補が優先されるため、ある時点で探索を行なっている位置は、その時点で挙がっている探索候補の中で一番遠い位置であることになります。さらに、その位置で見つかる探索候補は今いる位置よりも必ずスタートからの距離が遠い候補となるため、当然その時点で挙がっている探索候補よりもスタートからの距離が遠い候補となります（探索済みの位置を除けば）。
例えば、下の図は 深さ優先探索 の章で深さ優先探索で迷路を解く際の動作を説明した時に用いた図になりますが、最初に探索を行なったスタート地点で見つけた探索候補（(3, 4) と (2, 3) と (4, 3)）よりも、最後に探索を行なった (5, 0) のマスで見つけた探索候補（(5, 1) と (6, 0)）の方がスタートからの距離が長くなっています。
これはたまたまではなく、深さ優先探索で探索を行う場合は、必ず後から見つけた探索候補の方が先に見つけた探索候補よりもスタートからの距離が長くなります。
つまり、深さ優先探索に則って探索を行う場合、後から見つけた探索候補は先に見つけた探索候補よりもスタートからの距離が遠いことになり、後から見つけた探索候補を優先して探索していくことになります。
したがって、深さ優先探索で探索を行いたい場合、後から見つけた探索候補から先に探索を行えば良いことになります。
このような探索は、スタックというデータ構造を利用することで簡単に実現することができます。
スタックについては下記ページで解説していますので、スタックについてご存知ない方や詳しく知りたい方は読んでみていただければと思います。
【C言語/データ構造】スタックとキューの配列での実装方法
スタックはデータの保存や取得を行うための仕組みであり、取得を行う際、後から保存されたデータが先に取得されるという特徴を持っています。
つまり、保存するデータを探索候補（迷路の場合はマスの座標）とし、探索候補が見つかった際にスタックに対して探索候補を保存するようにしてやり、次の探索先はそのスタックから取得するようにすることで、後に見つけた探索候補が優先して取得されるようになります（下の図では、探索候補を (4, 3)・(2, 3)・(3, 4)・(3, 2) の順でスタックに保存を行なっています）。
さらに、その探索先で新たに探索候補が見つかった場合は、同様にしてスタックに対して見つかった探索候補を保存し、さらに次の探索先はスタックからの取得によって決定します。これを繰り返していけば、自然と深さ優先探索での探索を実現することができます。
したがって、深さ優先探索は次のような手順を踏むことで実現することができることになります。
- スタートと探索対象の位置を決める
- スタートの位置をスタックに保存する
- スタックから次の探索先を取得する
- 取得に失敗した場合は探索対象が存在しないため探索終了
- 現在の探索先が探索対象であれば探索対象が見つかったことになるので探索終了
- 現在の探索先を探索済みとする
- 現在の探索先から辿ることが可能な探索候補をスタックに保存する
- 探索候補が同時に複数見つかった場合、見つかった全ての探索候補をスタックに保存
- 3. に戻る
上記の手順に従って探索を行うように実装すれば、深さ優先探索での探索を実現することができます。
ただし、特にC言語の場合は、ここで使用するスタックが標準で用意されていないため、別途他の人が作ったスタックを使用するか、自身でスタックを実装して作成する必要があります。この点が深さ優先探索を実現するのに難しいというか、面倒な点になると思います。
一方で、Python などの場合は標準でスタックが用意されているため、深さ優先探索も簡単に実現することが可能になります。
次に紹介するサンプルプログラムでは、スタックの実装も含めたものを紹介しますが、スタックの実装方法については先程も紹介した下記ページで説明していますので、スタックの実装の説明に関しては本ページでの詳細な説明は省略させていただきます。
【C言語/データ構造】スタックとキューの配列での実装方法
また、実はスタックを用意しなくても深さ優先探索を実現することも可能です。再帰呼び出しを利用することで、スタックを用意しなくても深さ優先探索を実現することができます。
この再帰呼び出しを利用した深さ優先探索に関しては下記ページで解説を行なっているため、このページではサンプルプログラム等の紹介は省略させていただきます。
【C言語】「再帰呼び出しの動き・メリット・書き方」を迷路を解いて理解する
深さ優先探索のサンプルプログラム（迷路）
ということで、先ほど紹介した手順に従って探索を行うように実装したサンプルプログラムを紹介していきます。
深さ優先探索で迷路を解くプログラム
下記が、迷路におけるゴールを深さ優先探索で探索するサンプルプログラムのソースコードとなります。
#include <stdio.h>
#include <stdbool.h>
/* 迷路のサイズ */
#define MEIRO_WIDTH 13
#define MEIRO_HEIGHT 9
#define PATH 0 /* 通路 */
#define WALL 1 /* 壁 */
#define GOAL 2 /* ゴール */
#define PASSED 3 /* 通過したマス */
/* 管理するデータの上限個数 */
#define MAX_NUM (MEIRO_WIDTH * MEIRO_HEIGHT)
#define STACK_SIZE MAX_NUM
/* マスの位置情報 */
typedef struct POS {
int i; /* マスのi座標 */
int j; /* マスのj座標 */
} POS_T;
/* スタック構造体 */
typedef struct STACK {
/* データの最後尾 */
int tail;
/* スタックされているデータ */
POS_T data[STACK_SIZE];
} STACK_T;
STACK_T stack;
/* 迷路を表す配列(0:通路、1:壁) */
static int maze[MEIRO_HEIGHT][MEIRO_WIDTH] =
{
{1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,1,1,1},
{1,0,1,1,1,1,1,1,1,0,1,0,1},
{1,0,0,0,0,0,0,0,1,0,0,0,1},
{1,1,1,1,1,1,1,0,1,1,1,0,1},
{1,0,0,0,0,0,0,0,0,0,1,0,1},
{1,0,1,0,1,0,1,1,1,0,1,0,1},
{1,0,0,0,0,0,0,0,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1}
};
/* スタックを初期化する関数 */
void initStack(STACK_T *stack){
/* スタックを空に設定 */
stack->tail = -1;
}
/* PUSHする関数 */
void push(STACK_T *stack, POS_T *input){
/* スタックが満杯なら何もせず関数終了 */
if(stack->tail >= STACK_SIZE - 1){
printf("スタックが満杯でPUSHできません\n");
return;
}
/* データをデータの最後尾の１つ後ろに格納 */
stack->data[stack->tail + 1] = *input;
/* データの最後尾を１つ後ろに移動 */
stack->tail = stack->tail + 1;
}
/* POPする関数 */
POS_T *pop(STACK_T *stack){
POS_T *ret;
/* スタックが空なら何もせずに関数終了 */
if(stack->tail == -1){
printf("スタックが空です\n");
return NULL;
}
/* データの最後尾からデータを取得 */
ret = &(stack->data[stack->tail]);
/* データの最後尾を１つ前にずらす */
stack->tail = stack->tail - 1;
/* 取得したデータを返却 */
return ret;
}
/* (i,j) が通過可能なマスかどうかを確認する関数 */
bool check(int i, int j) {
bool ret = true;
if (i < 0 || i >= MEIRO_WIDTH || j < 0 || j >= MEIRO_HEIGHT) {
/* (i,j) は迷路外なので通過不可 */
ret = false;
}
if (maze[j][i] == WALL) {
/* (i,j) は壁なので通過不可 */
ret = false;
}
if (maze[j][i] == PASSED) {
/* (i,j) は通過済みなので通過不可 */
ret = false;
}
return ret;
}
/* スタート(i,j)からゴールを探索する関数*/
bool search(int s_i, int s_j) {
POS_T pos;
bool ret;
/* 次の探索候補としてスタートのマスの情報をスタックに格納 */
if (check(s_i, s_j)) {
pos.i = s_i; /* スタートのi座標*/
pos.j = s_j; /* スタートのj座標*/
push(&stack, &pos); /* スタックにマスの情報を格納*/
}
while (true) {
int i, j;
/* スタックから次の探索候補のマスを取得*/
POS_T *next = pop(&stack);
if (next == NULL) {
/* 次の探索候補がない場合は探索失敗 */
ret = false;
break;
}
/* 探索するマスの座標を取得 */
i = next->i;
j = next->j;
if (maze[j][i] == GOAL) {
/* 探索対象が見つかったので探索成功 */
printf("ゴールに到着\n");
ret = true;
break;
}
/* 探索済みのマスに印をつける */
maze[j][i] = PASSED;
/* 現在探索中のマスから辿れる次の探索候補をスタックに格納 */
if (check(i, j - 1)) {
/* 上方向に辿れる場合 */
pos.i = i; /* 上方向のマスのi座標 */
pos.j = j - 1; /* 上方向のマスのj座標 */
/* 上方向のマスを探索候補としてスタックに格納*/
push(&stack, &pos);
}
if (check(i, j + 1)) {
/* 下方向に辿れる場合 */
pos.i = i; /* 下方向のマスのi座標 */
pos.j = j + 1; /* 下方向のマスのj座標 */
/* 下方向のマスを探索候補としてスタックに格納*/
push(&stack, &pos);
}
if (check(i - 1, j)) {
/* 左方向に辿れる場合 */
pos.i = i - 1; /* 左方向のマスのi座標 */
pos.j = j; /* 左方向のマスのj座標 */
/* 左方向のマスを探索候補としてスタックに格納*/
push(&stack, &pos);
}
if (check(i + 1, j)) {
/* 右方向に辿れる場合 */
pos.i = i + 1; /* 右方向のマスのi座標 */
pos.j = j; /* 右方向のマスのj座標 */
/* 右方向のマスを探索候補としてスタックに格納*/
push(&stack, &pos);
}
}
return ret;
}
int main(void) {
initStack(&stack);
/* ゴールの位置を設定 */
maze[5][3] = GOAL;
/* スタート位置を(1,3)として開始 */
if (search(1, 3)) {
printf("ゴールが見つかりました！\n");
} else {
printf("ゴールが見つかりません！\n");
}
return 0;
}迷路を解くサンプルプログラムの解説
上記ソースコードにおいては、２次元配列 maze が迷路を表しています。1 のマスが通路であり、0 のマスが壁を表しています。要は、1 は通過可能なマスであり、0 は通過不可なマスとなります。
このように maze を宣言しておくことで、(i, j) 座標のマスが通路 or 壁であるかどうかは maze[j][i] から取得することが可能となります（maze[i][j] ではないので注意してください）。
また maze にはスタートとゴールが設定されていませんので、main 関数の中で maze[5][3] = GOAL を実行することで (3, 5) 座標のマスをゴールに設定し、さらに次に説明する search 関数の引数に (1, 3) を指定することで、(1, 3) 座標のマスをスタートに設定しています。
そして、search 関数は、２次元配列 maze で定義される迷路における「ゴールを探索する関数」になっています。迷路のスタートは、前述の通り引数 i と j によって与えられるものとしています（つまりスタートは (i, j) 座標となります）。
search 関数でやっていることは 深さ優先探索の実装方法 で示した手順 2. 〜 8. そのものになります。スタックにデータを保存する関数は push、スタックからデータを取得する関数は pop としており、さらにスタックに保存するデータは、ソースコードの冒頭で定義を行なっているPOS_T 構造体としています。
スタック関連の関数の詳細については下記ページで解説していますので、詳しく知りたい方は下記ページをご参照いただければと思います。
【C言語/データ構造】スタックとキューの配列での実装方法
また、スタックに保存するデータである POS_T はマスの横方向の座標 i と縦方向の座標 j を管理する構造体となっていますので、スタックに探索候補の座標を POS_T のデータとして保存するようにしてやれば、次の探索先はスタックから取得した POS_T のデータの座標から決定することができるようになっています。
迷路の場合、現在探索しているマスの上・下・左・右に存在する４つのマスが新たに見つかる探索候補となるのですが、そのマスが迷路外・壁・探索済みの場合は探索候補から除外する必要があります。そのため、座標 (i, j) のマスが探索候補となりうるかどうかを判断する関数として check を用意しています。
したがって、探索候補をスタックに保存する処理は、現在探索しているマスの上・下・左・右に存在する４つのマスそれぞれに対し、そのマスの座標を引数に指定して check 関数を実行し、true が返却された場合のみ、すなわちその座標のマスが探索候補となりうる場合のみ、その座標を POS_T 構造体のデータとしてスタックに保存することで実現することになります。
この辺りの解説を踏まえて search 関数を読んでいただければ、search 関数で深さ優先探索がどのように実現されているのかを理解していただけるのではないかと思います。
深さ優先探索で迷路を解くプログラム（経路表示あり）
ただし、先ほど紹介したソースコードの search 関数は、単にスタートからゴールに到達可能かどうかを判断する関数となっています。経路は表示されません。
次は、スタートからゴールに到達可能である場合に、経路も表示できるようにしていきたいと思います。
経路を表示する方法はいくつかあると思いますが、今回はマスを探索する際に、そのマス自身と、そのマスに到達する直前に辿ったマスも記録するようにし、探索中のマスから直前に辿ったマスを遡れるようにしていきたいと思います。
これを実現するために、まず POS_T 構造体を下記のように変更します。
/* マスの位置情報 */
typedef struct POS {
int i; /* マスのi座標 */
int j; /* マスのj座標 */
int b_i; /* １つ前に辿ったマスのi座標 */
int b_j; /* １つ前に辿ったマスのj座標 */
} POS_T;この構造体の意味合いは、基本的にはマスの座標 (i, j) を管理するものになりますが、b_i と b_j メンバを追加し、これらでそのマスに直前に訪れたマスの座標 (b_i, b_j) も記録できるようにしていきます。
また、探索を行なったマスを管理するために下記のように配列 trace を用意し、探索を行うたびに、その探索を行なったマスを trace に記録していくようにしていきます。
POS_T trace[MEIRO_HEIGHT * MEIRO_WIDTH];あとは、search 関数の中では単に探索を行うだけでなく、探索したマスの情報（および直前に辿ったマスの情報）を配列 trace に記録するようにし、ゴールに到達した際に、trace を利用してゴールからスタートまでの経路を求め、それを出力するようにしていけば、スタートからゴールまでの経路の表示も行うことができるようになります。
これらの解説を踏まえ、先ほど紹介したソースコードを変更して経路を表示できるようにしたものが下記となります。
#include <stdio.h>
#include <stdbool.h>
/* 迷路のサイズ */
#define MEIRO_WIDTH 13
#define MEIRO_HEIGHT 9
#define PATH 0 /* 通路 */
#define WALL 1 /* 壁 */
#define GOAL 2 /* ゴール */
#define PASSED 3 /* 通過したマス */
/* 管理するデータの上限個数 */
#define MAX_NUM (MEIRO_WIDTH * MEIRO_HEIGHT)
#define STACK_SIZE MAX_NUM
/* マスの位置情報 */
typedef struct POS {
int i; /* マスのi座標 */
int j; /* マスのj座標 */
int b_i; /* １つ前に辿ったマスのi座標 */
int b_j; /* １つ前に辿ったマスのj座標 */
} POS_T;
/* スタック構造体 */
typedef struct STACK {
/* データの最後尾 */
int tail;
/* スタックされているデータ */
POS_T data[STACK_SIZE];
} STACK_T;
STACK_T stack;
POS_T trace[MEIRO_HEIGHT * MEIRO_WIDTH];
POS_T route[MEIRO_HEIGHT * MEIRO_WIDTH];
/* 迷路を表す配列(0:通路、1:壁) */
static int maze[MEIRO_HEIGHT][MEIRO_WIDTH] =
{
{1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,1,1,1},
{1,0,1,1,1,1,1,1,1,0,1,0,1},
{1,0,0,0,0,0,0,0,1,0,0,0,1},
{1,0,1,1,1,1,1,0,1,1,1,0,1},
{1,0,0,0,0,0,0,0,0,0,1,0,1},
{1,0,1,0,1,0,1,1,1,0,1,0,1},
{1,0,0,0,0,0,0,0,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1}
};
/* スタックを初期化する関数 */
void initStack(STACK_T *stack){
/* スタックを空に設定 */
stack->tail = -1;
}
/* PUSHする関数 */
void push(STACK_T *stack, POS_T *input){
/* スタックが満杯なら何もせず関数終了 */
if(stack->tail >= STACK_SIZE - 1){
printf("スタックが満杯でPUSHできません\n");
return;
}
/* データをデータの最後尾の１つ後ろに格納 */
stack->data[stack->tail + 1] = *input;
/* データの最後尾を１つ後ろに移動 */
stack->tail = stack->tail + 1;
}
/* POPする関数 */
POS_T *pop(STACK_T *stack){
POS_T *ret;
/* スタックが空なら何もせずに関数終了 */
if(stack->tail == -1){
printf("スタックが空です\n");
return NULL;
}
/* データの最後尾からデータを取得 */
ret = &(stack->data[stack->tail]);
/* データの最後尾を１つ前にずらす */
stack->tail = stack->tail - 1;
/* 取得したデータを返却 */
return ret;
}
/* (i,j) が通過可能なマスかどうかを確認する関数 */
bool check(int i, int j) {
bool ret = true;
if (i < 0 || i >= MEIRO_WIDTH || j < 0 || j >= MEIRO_HEIGHT) {
/* (i,j) は迷路外なので通過不可 */
ret = false;
}
if (maze[j][i] == WALL) {
/* (i,j) は壁なので通過不可 */
ret = false;
}
if (maze[j][i] == PASSED) {
/* (i,j) は通過済みなので通過不可 */
ret = false;
}
return ret;
}
/* ゴールまでの経路を出力する関数 */
void printRoute(int num_trace) {
int n;
int count = 0;
/* ゴールからスタートまでの経路をrouteに格納 */
/* 最後に通過したマスの情報のtrace上の位置 */
n = num_trace - 1;
while (true) {
POS_T pos = trace[n]; /* 通過したマスの情報を取得 */
route[count] = pos; /* 通過したマスを覚えておく */
count++;
if (pos.b_i == -1 && pos.b_j == -1) {
/* 通過したマススタートなら終了 */
break;
}
for (int m = n - 1; m >= 0; m--) {
/* posの前に通過したマスの情報が格納されているtrace上の位置を探索 */
if (trace[m].i == pos.b_i && trace[m].j == pos.b_j) {
/* posの前に通過した位置はtrace[m]に格納されている */
n = m;
break;
}
}
}
/* ゴールからスタートまでの経路を逆順に表示 */
for (int m = count - 1; m >= 0; m --) {
printf("(%d,%d) ", route[m].i, route[m].j);
}
printf("\n\n");
}
/* スタート(i,j)からゴールを探索する関数*/
bool search(int s_i, int s_j) {
POS_T pos;
int num_trace;
bool ret;
/* 次の探索候補としてスタートのマスの情報をスタックに格納 */
if (check(s_i, s_j)) {
pos.i = s_i; /* スタートのi座標*/
pos.j = s_j; /* スタートのj座標*/
pos.b_i = -1; /* スタートの前の位置は存在しないため-1にしておく */
pos.b_j = -1; /* スタートの前の位置は存在しないため-1にしておく */
push(&stack, &pos); /* スタックにマスの情報を格納*/
}
num_trace = 0;
while (true) {
int i, j;
/* スタックから次の探索候補のマスを取得*/
POS_T *next = pop(&stack);
if (next == NULL) {
/* 次の探索候補がない場合は探索失敗 */
ret = false;
break;
}
/* 探索するマスの座標を取得 */
i = next->i;
j = next->j;
/* 探索するマスを探索済のマスとして覚えておく */
trace[num_trace] = *next;
num_trace++;
if (maze[j][i] == GOAL) {
/* 探索対象が見つかったので探索成功 */
printf("ゴールに到着\n");
printRoute(num_trace);
ret = true;
break;
}
/* 探索済みのマスに印をつける */
maze[j][i] = PASSED;
/* 現在探索中のマスから辿れる次の探索候補をスタックに格納 */
if (check(i, j - 1)) {
/* 上方向に辿れる場合 */
pos.i = i; /* 上方向のマスのi座標 */
pos.j = j - 1; /* 上方向のマスのj座標 */
pos.b_i = i; /* 上方向のマスの前に辿ったマスのi座標 */
pos.b_j = j; /* 上方向のマスの前に辿ったマスのj座標 */
/* 上方向のマスを探索候補としてスタックに格納*/
push(&stack, &pos);
}
if (check(i, j + 1)) {
/* 下方向に辿れる場合 */
pos.i = i; /* 下方向のマスのi座標 */
pos.j = j + 1; /* 下方向のマスのj座標 */
pos.b_i = i; /* 下方向のマスの前に辿ったマスのi座標 */
pos.b_j = j; /* 下方向のマスの前に辿ったマスのj座標 */
/* 下方向のマスを探索候補としてスタックに格納*/
push(&stack, &pos);
}
if (check(i - 1, j)) {
/* 左方向に辿れる場合 */
pos.i = i - 1; /* 左方向のマスのi座標 */
pos.j = j; /* 左方向のマスのj座標 */
pos.b_i = i; /* 左方向のマスの前に辿ったマスのi座標 */
pos.b_j = j; /* 左方向のマスの前に辿ったマスのj座標 */
/* 左方向のマスを探索候補としてスタックに格納*/
push(&stack, &pos);
}
if (check(i + 1, j)) {
/* 右方向に辿れる場合 */
pos.i = i + 1; /* 右方向のマスのi座標 */
pos.j = j; /* 右方向のマスのj座標 */
pos.b_i = i; /* 右方向のマスの前に辿ったマスのi座標 */
pos.b_j = j; /* 右方向のマスの前に辿ったマスのj座標 */
/* 右方向のマスを探索候補としてスタックに格納*/
push(&stack, &pos);
}
}
return ret;
}
int main(void) {
initStack(&stack);
/* ゴールの位置を設定 */
maze[5][3] = GOAL;
/* スタート位置を(1,3)として開始 */
if (search(1, 3)) {
printf("ゴールが見つかりました！\n");
} else {
printf("ゴールが見つかりません！\n");
}
return 0;
}前述の通り、search 関数では POS_T のデータに探索候補のマスの座標だけでなく、その探索候補の直前に訪れたマスの座標、すなわち、現在探索しているマスの座標をセットした上で、スタックに保存を行うようにしています。
また、探索したマスの情報（POS_T のデータ）は配列 trace にも先頭から順番に保存するようにしています。
さらに、ゴールに到達した際には、新たに用意した関数 printRoute を呼び出して経路の表示を行うようにしています。printRoute はゴールに到達した際に呼び出される＆探索したマスの情報は配列 trace の先頭から順番に保存されるため、printRoute 呼び出し時には、配列 trace の一番後ろに保存されている POS_T のデータはゴールのマスに対応する情報となります。
したがって、配列 trace の一番後ろの要素はゴールのマスの情報を示す POS_T のデータとなります。つまり、下記を実行することで、pos はゴールのマスの情報を示す POS_T のデータとなります（n は trace の要素数になります）。
POS_T pos = trace[n];さらに、pos.b_i と pos_b_j はゴールの直前に訪れたマスの座標ということになります。つまり、この pos.b_i を i に、pos.b_j を j に持つ POS_T のデータは、pos の直前に訪れたマスの情報を示すデータということになります。
そのデータは配列 trace に保存されているはずなので、配列 trace のどの位置（添字）に保存されているのかを下記で探索しています。
for (int m = n - 1; m >= 0; m--) {
/* posの前に通過したマスの情報が格納されているtrace上の位置を探索 */
if (trace[m].i == pos.b_i && trace[m].j == pos.b_j) {
/* posの前に通過した位置はtrace[m]に格納されている */
n = m;
break;
}
}上記の探索終了後の n は trace[n].i == pos.b_i と trace[n].j == pos.b_j を満たす n ですので、trace[n] の POS_T のデータは pos の直前に訪れたマスの情報となります。つまり、ゴールの直前に訪れたマスの情報になります。
さらに、while ループの先頭に戻り、この trace[n] を新たな pos として同様のことを行えば、今度は新たな pos の直前に訪れたマスの情報を示すPOS_T のデータを取得することができます。つまり、ゴールの２つ前に訪れたマスの情報が取得することができることになります。
同様の処理を繰り返し行えば、ゴールの前に訪れたマスの情報を次々と取得していくことができることになり、いずれはスタートから辿った全てのマスの情報を取得することができます。この取得した情報を配列の先頭から順に保存しておき（printRoute では配列 route に保存している）、最後にこの保存した配列の情報を逆順に全て表示してやれば、スタートからゴールの経路を表示することができるようになります（この配列にはゴールからスタートの順にマスの情報が保存されることになるため、逆順に表示する必要があります）。
この経路の表示に関してはもっと効率の良い方法もあると思うのですが、今回はソースコードや説明をシンプルにするために、上記のような方法で表示を行なっています。
スポンサーリンク
深さ優先探索のサンプルプログラム（グラフ）
深さ優先探索のサンプルプログラムの最後の紹介として、グラフに対する深さ優先探索の例を示しておきたいと思います。
今回探索の対象とするグラフは下の図のようなものになります。
このグラフは、下記のような initGraph 関数により実現することができます。
/* グラフのサイズ */
#define GRAPH_SIZE 11
/* エッジの最大数 */
#define MAX_EDGE 4
int graph[GRAPH_SIZE][MAX_EDGE];
/* グラフを作成する関数 */
void initGraph(void) {
graph[0][0] = 1; graph[0][1] = 2; graph[0][2] = -1; graph[0][3] = -1;
graph[1][0] = 3; graph[1][1] = 0; graph[1][2] = -1; graph[1][3] = -1;
graph[2][0] = 0; graph[2][1] = 4; graph[2][2] = -1; graph[2][3] = -1;
graph[3][0] = 1; graph[3][1] = 5; graph[3][2] = -1; graph[3][3] = -1;
graph[4][0] = 2; graph[4][1] = 6; graph[4][2] = -1; graph[4][3] = -1;
graph[5][0] = 3; graph[5][1] = -1; graph[5][2] = -1; graph[5][3] = -1;
graph[6][0] = 7; graph[6][1] = 4; graph[6][2] = 8; graph[6][3] = -1;
graph[7][0] = 9; graph[7][1] = 6; graph[7][2] = -1; graph[7][3] = -1;
graph[8][0] = 6; graph[8][1] = -1; graph[8][2] = -1; graph[8][3] = -1;
graph[9][0] = 7; graph[9][1] = 10; graph[9][2] = -1; graph[9][3] = -1;
graph[10][0] = 9; graph[10][1] = -1; graph[10][2] = -1; graph[10][3] = -1;
}graph がグラフを表現する２次元配列であり、graph[i][e] の値が、ノード i の第 e 番目のエッジの先にあるノードを表しています。
例えば、graph[0] における graph[0][0] の値は 1 であり、ノード 0 からノード 1 の間にエッジが存在する、すなわちノード 0 からノード 1 に辿れることが可能であることを示しています。言い換えれば、ノード 0 を探索した際に、ノード 1 が新たな探索候補として見つかることを示しています。
また同様に、graph[0][1] の値が 2 であることは、ノード 0 からノード 2 の間にエッジが存在することを示しています。
さらに、ノード 0 との間にエッジが存在するノード 1 と ノード 2 には当然ノード 0 との間にエッジが存在することになるため、graph[1] のいずれかの要素の値と graph[2] のいずれかの要素の値は 0 となります。上記の initGraph で生成した graph の場合は、graph[1][1] と graph[2][0] とが 0 となります。
このようなノード間のエッジを定義することでグラフを生成しているのが initGraph になります。
これらに対し、graph[0][2] や graph[0][3] の値は -1 であり、この値が -1 である場合はエッジが存在しないことを示しています。つまり、ノード 0 に存在するエッジはノード 1 との間およびノード 2 との間の２つのみであることになります。
迷路では、探索候補としてスタックに保存する際に、その探索候補のマスが迷路外・壁・探索済みの場合は探索候補から除外するようにしていました。それに対し、上記のグラフの場合は、ノード i を探索した際に、そのノードのエッジの先にあるノードの番号のみをスタックに保存することになります。すなわち、値が -1 でない graph[i][e] の情報を保存していくことになります（ただし、迷路の時同様に、既に探索済みのノードは探索候補から除外して OK です）。
また、今回も POS_T 構造体を用意しますが、今回は座標ではなくノード番号 i で探索候補や探索先を管理していくことになるため、迷路の場合と異なり j に関するメンバは不要になります（b_i メンバは、ノード i の探索を行う前に探索したノード番号となります）。
/* 各ノードの情報 */
typedef struct POS {
int i; /* ノードの番号 */
int b_i; /* １つ前に辿ったノードの番号 */
} POS_T;深さ優先探索 でも解説したように、迷路でゴールを探索するような探索問題はグラフの問題として置き換えることができます。上記の initGraph 関数で作成するグラフも迷路を意識したものであり、実際に initGraph 関数で作成するグラフは下の図の迷路に基づいて作成したものになります。
マスに記入している数字とノード番号が対応しており、例えば 0 が記入されたマスからは 1 が記入されたマスと 2 が記入されたマスに辿ることができるため、グラフ化した際にはノード 0 にノード 1 へのエッジとノード 2 へのエッジが存在することになります。他のノードに関しても、迷路の各マスに対応していることが確認できると思います。
また、迷路においては、あるマスから辿れるマス数の最大値は４つとなります（上・下・左・右方向の４つのマス）。そのため、今回のグラフでは各ノードに存在するエッジの最大数（MAX_EDGE）は 4 として実装していきたいと思います。
上記の解説に基づき、グラフから深さ優先探索で探索を行うプログラムのソースコードは下記のようになります。
#include <stdio.h>
#include <stdbool.h>
/* グラフのサイズ */
#define GRAPH_SIZE 11
/* エッジの最大数 */
#define MAX_EDGE 4
/* 管理するデータの上限個数 */
#define MAX_NUM GRAPH_SIZE
#define STACK_SIZE MAX_NUM
/* 各ノードの情報 */
typedef struct POS {
int i; /* ノードの番号 */
int b_i; /* １つ前に辿ったノードの番号 */
} POS_T;
/* スタック構造体 */
typedef struct STACK {
/* データの最後尾 */
int tail;
/* スタックされているデータ */
POS_T data[STACK_SIZE];
} STACK_T;
STACK_T stack;
POS_T trace[GRAPH_SIZE];
POS_T route[GRAPH_SIZE];
int graph[GRAPH_SIZE][MAX_EDGE];
int searched[GRAPH_SIZE];
/* グラフを作成する関数 */
void initGraph(void) {
graph[0][0] = 1; graph[0][1] = 2; graph[0][2] = -1; graph[0][3] = -1;
graph[1][0] = 3; graph[1][1] = 0; graph[1][2] = -1; graph[1][3] = -1;
graph[2][0] = 0; graph[2][1] = 4; graph[2][2] = -1; graph[2][3] = -1;
graph[3][0] = 1; graph[3][1] = 5; graph[3][2] = -1; graph[3][3] = -1;
graph[4][0] = 2; graph[4][1] = 6; graph[4][2] = -1; graph[4][3] = -1;
graph[5][0] = 3; graph[5][1] = -1; graph[5][2] = -1; graph[5][3] = -1;
graph[6][0] = 7; graph[6][1] = 4; graph[6][2] = 8; graph[6][3] = -1;
graph[7][0] = 9; graph[7][1] = 6; graph[7][2] = -1; graph[7][3] = -1;
graph[8][0] = 6; graph[8][1] = -1; graph[8][2] = -1; graph[8][3] = -1;
graph[9][0] = 7; graph[9][1] = 10; graph[9][2] = -1; graph[9][3] = -1;
graph[10][0] = 9; graph[10][1] = -1; graph[10][2] = -1; graph[10][3] = -1;
}
/* スタックを初期化する関数 */
void initStack(STACK_T *stack){
/* スタックを空に設定 */
stack->tail = -1;
}
/* PUSHする関数 */
void push(STACK_T *stack, POS_T *input){
/* スタックが満杯なら何もせず関数終了 */
if(stack->tail >= STACK_SIZE - 1){
printf("スタックが満杯でPUSHできません\n");
return;
}
/* データをデータの最後尾の１つ後ろに格納 */
stack->data[stack->tail + 1] = *input;
/* データの最後尾を１つ後ろに移動 */
stack->tail = stack->tail + 1;
}
/* POPする関数 */
POS_T *pop(STACK_T *stack){
POS_T *ret;
/* スタックが空なら何もせずに関数終了 */
if(stack->tail == -1){
printf("スタックが空です\n");
return NULL;
}
/* データの最後尾からデータを取得 */
ret = &(stack->data[stack->tail]);
/* データの最後尾を１つ前にずらす */
stack->tail = stack->tail - 1;
/* 取得したデータを返却 */
return ret;
}
/* ゴールまでの経路を出力する関数 */
void printRoute(int num_trace) {
int n;
int count = 0;
/* ゴールからスタートまでの経路をrouteに格納 */
/* 最後に通過したノードの情報のtrace上の位置 */
n = num_trace - 1;
while (true) {
POS_T pos = trace[n]; /* 通過したノードの情報を取得 */
route[count] = pos; /* 通過したノードを覚えておく */
count++;
if (pos.b_i == -1) {
/* 通過したノードスタートなら終了 */
break;
}
for (int m = n - 1; m >= 0; m--) {
/* posの前に通過したノードの情報が格納されているtrace上の位置を探索 */
if (trace[m].i == pos.b_i) {
/* posの前に通過した位置はtrace[m]に格納されている */
n = m;
break;
}
}
}
/* ゴールからスタートまでの経路を逆順に表示 */
for (int m = count - 1; m >= 0; m --) {
printf("%d,", route[m].i);
}
printf("\n\n");
}
/* スタートからゴールを探索する関数*/
bool search(int s_i, int g_i) {
POS_T pos;
int num_trace;
bool ret;
pos.i = s_i;
pos.b_i = -1;
push(&stack, &pos); /* スタックにノードの情報を格納*/
num_trace = 0;
while (true) {
int i;
/* スタックから次の探索候補のノードを取得*/
POS_T *next = pop(&stack);
if (next == NULL) {
/* 次の探索候補がない場合は探索失敗 */
ret = false;
break;
}
/* 探索するノードの座標を取得 */
i = next->i;
/* 探索するノードを探索済のノードとして覚えておく */
trace[num_trace] = *next;
num_trace++;
if (i == g_i) {
/* 探索対象が見つかったので探索成功 */
printf("ゴールに到着\n");
printRoute(num_trace);
ret = true;
break;
}
/* 探索済みのノードに印をつける */
searched[i] = 1;
for (int e = 0; e < MAX_EDGE; e++) {
if (graph[i][e] != -1) {
if (searched[graph[i][e]] != 1) {
pos.i = graph[i][e];
pos.b_i = i;
push(&stack, &pos);
}
}
}
}
return ret;
}
int main(void) {
initStack(&stack);
initGraph();
/* スタートのノード番号を0、ゴールのノード番号を10として開始 */
if (search(0, 10)) {
printf("ゴールが見つかりました！\n");
} else {
printf("ゴールが見つかりません！\n");
}
return 0;
}今まで示してきた search 関数とは引数の意味合いが異なっているので注意してください。
search 関数は第１引数で指定された番号のノードをスタートとして、第２引数で指定された番号のノードを探索する関数になっています。
ただ、search 関数で行っていることは基本的には迷路の時と同じで、新たに見つけた探索候補のスタックへの保存と、次の探索先のスタックからの取得とを繰り返すことで探索を行なっています。
前述の通り、あるノードで見つかる新たな探索候補は、そのノードのエッジの先にあるノードとなります。したがって、ノード i を探索した際には、値が -1 でない graph[i][e] の値を POS_T のデータにセットしてスタックに保存すれば良いことになります。
幅優先探索の実装
最後に、幅優先探索の実装方法および、サンプルプログラムについて紹介していきたいと思います。
幅優先探索の実装方法
幅優先探索 で説明したように、幅優先探索とは「スタートからの距離が近い候補を優先しながら探索対象を探索するアルゴリズム」です。
これは「先に見つけた探索候補を優先しながら探索対象を探索するアルゴリズム」と言い換えることができます。
このアルゴリズムを実現するために、深さ優先探索ではスタックを利用しましたが、幅優先探索ではキューを利用します。
キューについても、スタックと共に下記ページで解説していますので、キューについてご存知ない方や詳しく知りたい方は読んでみていただければと思います。
【C言語/データ構造】スタックとキューの配列での実装方法
スタック同様にキューもデータの保存や取得を行うための仕組みであり、取得を行う際、先に保存されたデータが先に取得されるという特徴を持っています。
つまり、保存するデータを探索候補（迷路の場合はマスの座標）とし、探索候補が見つかった際にキューに対して探索候補を保存するようにしてやり、次の探索候補はそのキューから取得するようにすることで、先に見つけた探索候補が優先して取得されるようになります（下の図では、探索候補を (3, 2)・(3, 4)・(2, 3)・(4, 3) の順でキューに保存を行なっています。深さ優先探索で示した例の時とは逆順なので注意してください）。
さらに、その探索先で新たに探索候補が見つかった場合は、同様にしてキューに対して見つかった探索候補を保存し、さらに次の探索先はキューからの取得によって決定します。これを繰り返していけば、自然と深さ優先探索での探索を実現することができます。
したがって、幅優先探索は次のような手順を踏むことで実現することができることになります。
- スタートと探索対象の位置を決める
- スタートの位置をキューに保存する
- キューから次の探索先を取得する
- 取得に失敗した場合は探索対象が存在しないため探索終了
- 現在の探索先が探索対象であれば探索対象が見つかったことになるので探索終了
- 現在の探索先を探索済みとする
- 現在の探索先から辿ることが可能な探索候補をキューに保存する
- 探索候補が同時に複数見つかった場合、見つかった全ての探索候補をキューに保存
- 3. に戻る
上記の手順に従って探索を行うように実装すれば、幅優先探索での探索を実現することができます。
また、深さ優先探索の実装 で示した手順と比較すれば分かるように、幅優先探索を実現するための手順と深さ優先探索を実現するための手順の違いは使用するデータ構造のみとなります。
つまり、深さ優先探索でスタックを利用していた箇所をキューを利用するように変更すれば、幅優先探索を実現することが可能です。
ただし、スタック同様に、キューに関してもC言語では標準で用意されていないため、自身で実装するなどして別途キューを用意する必要があります。
スポンサーリンク
幅優先探索のサンプルプログラム（迷路）
では、先ほど紹介した手順に従って探索を行うように実装したサンプルプログラムを紹介していきます。
幅優先探索で迷路を解くプログラム
前述の通り、幅優先探索と深さ優先探索とでは使用するデータ構造が異なるだけです。深さ優先探索ではスタックを利用するのに対し、幅優先探索ではキューを利用します。そのため、深さ優先探索で迷路を解くプログラム で紹介したソースコードに対し、スタックに関する変数の変更やスタックの利用部分をキューに関するものに変更してやれば、幅優先探索での探索を実現することができます。
そのサンプルプログラムのソースコードが下記となります。基本的には、深さ優先探索で迷路を解くプログラム で紹介したソースコードに対して使用するデータ構造を変更しているだけなので、ソースコードの解説は省略します（データを保存する関数を push から enqueue に、データを取得する関数を pop から dequeue に変更しています）。
#include <stdio.h>
#include <stdbool.h>
/* 迷路のサイズ */
#define MEIRO_WIDTH 13
#define MEIRO_HEIGHT 9
#define PATH 0 /* 通路 */
#define WALL 1 /* 壁 */
#define GOAL 2 /* ゴール */
#define PASSED 3 /* 通過したマス */
/* 管理するデータの上限個数 */
#define MAX_NUM (MEIRO_WIDTH * MEIRO_HEIGHT)
#define QUEUE_SIZE (MAX_NUM + 1)
/* マスの位置情報 */
typedef struct POS {
int i; /* マスのi座標 */
int j; /* マスのj座標 */
} POS_T;
/* キュー構造体 */
typedef struct QUEUE {
/* データの最後尾 */
int tail;
/* データの先頭 */
int head;
/* キューされているデータ */
POS_T data[QUEUE_SIZE];
} QUEUE_T;
QUEUE_T queue;
/* 迷路を表す配列(0:通路、1:壁) */
static int maze[MEIRO_HEIGHT][MEIRO_WIDTH] =
{
{1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,1,1,1},
{1,0,1,1,1,1,1,1,1,0,1,0,1},
{1,0,0,0,0,0,0,0,1,0,0,0,1},
{1,0,1,1,1,1,1,0,1,1,1,0,1},
{1,0,0,0,0,0,0,0,0,0,1,0,1},
{1,0,1,0,1,0,1,1,1,0,1,0,1},
{1,0,0,0,0,0,0,0,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1}
};
/* キューを初期化する関数 */
void initQueue(QUEUE_T *queue){
/* キューを空に設定 */
queue->head = 0;
queue->tail = -1;
}
/* ENQUEUEする関数 */
void enqueue(QUEUE_T *queue, POS_T *input){
/* キューが満杯なら何もせず関数終了 */
if((queue->tail + 2) % QUEUE_SIZE == queue->head){
printf("キューが満杯でENQUEUEできません\n");
return;
}
/* データをデータの最後尾の１つ後ろに格納 */
queue->data[(queue->tail + 1) % QUEUE_SIZE] = *input;
/* データの最後尾を１つ後ろに移動 */
queue->tail = (queue->tail + 1) % QUEUE_SIZE;
}
/* DEQUEUEする関数 */
POS_T *dequeue(QUEUE_T *queue){
POS_T *ret;
/* キューが空なら何もせずに関数終了 */
if((queue->tail + 1) % QUEUE_SIZE == queue->head){
printf("キューが空です\n");
return NULL;
}
/* データの先頭からデータを取得 */
ret = &(queue->data[queue->head]);
/* データの先頭を１つ後ろにずらす */
queue->head = (queue->head + 1) % QUEUE_SIZE;
/* 取得したデータを返却 */
return ret;
}
/* (i,j) が通過可能なマスかどうかを確認する関数 */
bool check(int i, int j) {
bool ret = true;
if (i < 0 || i >= MEIRO_WIDTH || j < 0 || j >= MEIRO_HEIGHT) {
/* (i,j) は迷路外なので通過不可 */
ret = false;
}
if (maze[j][i] == WALL) {
/* (i,j) は壁なので通過不可 */
ret = false;
}
if (maze[j][i] == PASSED) {
/* (i,j) は通過済みなので通過不可 */
ret = false;
}
return ret;
}
/* スタート(i,j)からゴールを探索する関数*/
bool search(int s_i, int s_j) {
POS_T pos;
bool ret;
/* 次の探索候補としてスタートのマスの情報をキューに格納 */
if (check(s_i, s_j)) {
pos.i = s_i; /* スタートのi座標*/
pos.j = s_j; /* スタートのj座標*/
enqueue(&queue, &pos); /* キューにマスの情報を格納*/
}
while (true) {
int i, j;
/* キューから次の探索候補のマスを取得*/
POS_T *next = dequeue(&queue);
if (next == NULL) {
/* 次の探索候補がない場合は探索失敗 */
ret = false;
break;
}
/* 探索するマスの座標を取得 */
i = next->i;
j = next->j;
if (maze[j][i] == GOAL) {
/* 探索対象が見つかったので探索成功 */
printf("ゴールに到着\n");
ret = true;
break;
}
/* 探索済みのマスに印をつける */
maze[j][i] = PASSED;
/* 現在探索中のマスから辿れる次の探索候補をキューに格納 */
if (check(i, j - 1)) {
/* 上方向に辿れる場合 */
pos.i = i; /* 上方向のマスのi座標 */
pos.j = j - 1; /* 上方向のマスのj座標 */
/* 上方向のマスを探索候補としてキューに格納*/
enqueue(&queue, &pos);
}
if (check(i, j + 1)) {
/* 下方向に辿れる場合 */
pos.i = i; /* 下方向のマスのi座標 */
pos.j = j + 1; /* 下方向のマスのj座標 */
/* 下方向のマスを探索候補としてキューに格納*/
enqueue(&queue, &pos);
}
if (check(i - 1, j)) {
/* 左方向に辿れる場合 */
pos.i = i - 1; /* 左方向のマスのi座標 */
pos.j = j; /* 左方向のマスのj座標 */
/* 左方向のマスを探索候補としてキューに格納*/
enqueue(&queue, &pos);
}
if (check(i + 1, j)) {
/* 右方向に辿れる場合 */
pos.i = i + 1; /* 右方向のマスのi座標 */
pos.j = j; /* 右方向のマスのj座標 */
/* 右方向のマスを探索候補としてキューに格納*/
enqueue(&queue, &pos);
}
}
return ret;
}
int main(void) {
initQueue(&queue);
/* ゴールの位置を設定 */
maze[5][3] = GOAL;
/* スタート位置を(1,3)として開始 */
if (search(1, 3)) {
printf("ゴールが見つかりました！\n");
} else {
printf("ゴールが見つかりません！\n");
}
return 0;
}１点だけ補足しておくと、本ソースコードにおいては、search 関数における下記部分をコメントアウトしてもゴールの探索に成功します（下記は探索済みのマスを記録する処理となります）。それに対し、深さ優先探索で迷路を解くプログラム のソースコードでは、search 関数における下記部分をコメントアウトすると探索に失敗します（無限に探索が続けられる）。
maze[j][i] = PASSED;上記をコメントアウトすれば、探索済みのマスが再度探索候補として扱われるようになり、探索候補が減らなくなることになります。つまり、探索候補が無限に存在することになります。
探索の失敗の有無 で解説したように、このような探索候補が無限に存在する場合でも、幅優先探索ではスタートからゴールに到達可能であれば探索に成功します。が、深さ優先探索の場合はスタートからゴールに到達可能であっても探索に失敗する可能性があります。
この違いを、上記のコメントアウトによって確認することが出来ます。
幅優先探索で迷路を解くプログラム（経路表示あり）
また、上記のソースコードを次のように変更すれば、ゴールを見つけた際にスタートからゴールへの経路を示すこともできます。幅優先探索探索の場合、必ず最短経路が表示されることになります。
これに関しても、深さ優先探索で迷路を解くプログラム（経路表示あり） に対して、スタックに関する部分をキューのものに変更しているだけで実現することができます。
#include <stdio.h>
#include <stdbool.h>
/* 迷路のサイズ */
#define MEIRO_WIDTH 13
#define MEIRO_HEIGHT 9
#define PATH 0 /* 通路 */
#define WALL 1 /* 壁 */
#define GOAL 2 /* ゴール */
#define PASSED 3 /* 通過したマス */
/* 管理するデータの上限個数 */
#define MAX_NUM (MEIRO_WIDTH * MEIRO_HEIGHT)
#define QUEUE_SIZE (MAX_NUM + 1)
/* マスの位置情報 */
typedef struct POS {
int i; /* マスのi座標 */
int j; /* マスのj座標 */
int b_i; /* １つ前に辿ったマスのi座標 */
int b_j; /* １つ前に辿ったマスのj座標 */
} POS_T;
/* キュー構造体 */
typedef struct QUEUE {
/* データの最後尾 */
int tail;
/* データの先頭 */
int head;
/* キューされているデータ */
POS_T data[QUEUE_SIZE];
} QUEUE_T;
QUEUE_T queue;
POS_T route[MEIRO_HEIGHT * MEIRO_WIDTH];
POS_T back_trace[MEIRO_HEIGHT * MEIRO_WIDTH];
/* 迷路を表す配列(0:通路、1:壁) */
static int maze[MEIRO_HEIGHT][MEIRO_WIDTH] =
{
{1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,1,1,1},
{1,0,1,1,1,1,1,1,1,0,1,0,1},
{1,0,0,0,0,0,0,0,1,0,0,0,1},
{1,0,1,1,1,1,1,0,1,1,1,0,1},
{1,0,0,0,0,0,0,0,0,0,1,0,1},
{1,0,1,0,1,0,1,1,1,0,1,0,1},
{1,0,0,0,0,0,0,0,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1}
};
/* キューを初期化する関数 */
void initQueue(QUEUE_T *queue){
/* キューを空に設定 */
queue->head = 0;
queue->tail = -1;
}
/* ENQUEUEする関数 */
void enqueue(QUEUE_T *queue, POS_T *input){
/* キューが満杯なら何もせず関数終了 */
if((queue->tail + 2) % QUEUE_SIZE == queue->head){
printf("キューが満杯でENQUEUEできません\n");
return;
}
/* データをデータの最後尾の１つ後ろに格納 */
queue->data[(queue->tail + 1) % QUEUE_SIZE] = *input;
/* データの最後尾を１つ後ろに移動 */
queue->tail = (queue->tail + 1) % QUEUE_SIZE;
}
/* DEQUEUEする関数 */
POS_T *dequeue(QUEUE_T *queue){
POS_T *ret;
/* キューが空なら何もせずに関数終了 */
if((queue->tail + 1) % QUEUE_SIZE == queue->head){
printf("キューが空です\n");
return NULL;
}
/* データの先頭からデータを取得 */
ret = &(queue->data[queue->head]);
/* データの先頭を１つ後ろにずらす */
queue->head = (queue->head + 1) % QUEUE_SIZE;
/* 取得したデータを返却 */
return ret;
}
/* (i,j) が通過可能なマスかどうかを確認する関数 */
bool check(int i, int j) {
bool ret = true;
if (i < 0 || i >= MEIRO_WIDTH || j < 0 || j >= MEIRO_HEIGHT) {
/* (i,j) は迷路外なので通過不可 */
ret = false;
}
if (maze[j][i] == WALL) {
/* (i,j) は壁なので通過不可 */
ret = false;
}
if (maze[j][i] == PASSED) {
/* (i,j) は通過済みなので通過不可 */
ret = false;
}
return ret;
}
/* ゴールまでの経路を出力する関数 */
void printRoute(int num_route) {
int n;
int count = 0;
/* ゴールからスタートまでの経路をback_traceに格納 */
/* 最後に通過したマスの情報のroute上の位置 */
n = num_route - 1;
while (true) {
POS_T pos = route[n]; /* 通過したマスの情報を取得 */
back_trace[count] = pos; /* 通過したマスを覚えておく */
count++;
if (pos.b_i == -1 && pos.b_j == -1) {
/* 通過したマススタートなら終了 */
break;
}
for (int m = n - 1; m >= 0; m--) {
/* posの前に通過したマスの情報が格納されているroute上の位置を探索 */
if (route[m].i == pos.b_i && route[m].j == pos.b_j) {
/* posの前に通過した位置はroute[m]に格納されている */
n = m;
break;
}
}
}
/* ゴールからスタートまでの経路を逆順に表示 */
for (int m = count - 1; m >= 0; m --) {
printf("(%d,%d) ", back_trace[m].i, back_trace[m].j);
}
printf("\n\n");
}
/* スタート(i,j)からゴールを探索する関数*/
bool search(int s_i, int s_j) {
POS_T pos;
int num_route;
bool ret;
/* 次の探索候補としてスタートのマスの情報をキューに格納 */
if (check(s_i, s_j)) {
pos.i = s_i; /* スタートのi座標*/
pos.j = s_j; /* スタートのj座標*/
pos.b_i = -1; /* スタートの前の位置は存在しないため-1にしておく */
pos.b_j = -1; /* スタートの前の位置は存在しないため-1にしておく */
enqueue(&queue, &pos); /* キューにマスの情報を格納*/
}
num_route = 0;
while (true) {
int i, j;
/* キューから次の探索候補のマスを取得*/
POS_T *next = dequeue(&queue);
if (next == NULL) {
/* 次の探索候補がない場合は探索失敗 */
ret = false;
break;
}
/* 探索するマスの座標を取得 */
i = next->i;
j = next->j;
/* 探索するマスを探索済のマスとして覚えておく */
route[num_route] = *next;
num_route++;
if (maze[j][i] == GOAL) {
/* 探索対象が見つかったので探索成功 */
printf("ゴールに到着\n");
printRoute(num_route);
ret = true;
break;
}
/* 探索済みのマスに印をつける */
maze[j][i] = PASSED;
/* 現在探索中のマスから辿れる次の探索候補をキューに格納 */
if (check(i, j - 1)) {
/* 上方向に辿れる場合 */
pos.i = i; /* 上方向のマスのi座標 */
pos.j = j - 1; /* 上方向のマスのj座標 */
pos.b_i = i; /* 上方向のマスの前に辿ったマスのi座標 */
pos.b_j = j; /* 上方向のマスの前に辿ったマスのj座標 */
/* 上方向のマスを探索候補としてキューに格納*/
enqueue(&queue, &pos);
}
if (check(i, j + 1)) {
/* 下方向に辿れる場合 */
pos.i = i; /* 下方向のマスのi座標 */
pos.j = j + 1; /* 下方向のマスのj座標 */
pos.b_i = i; /* 下方向のマスの前に辿ったマスのi座標 */
pos.b_j = j; /* 下方向のマスの前に辿ったマスのj座標 */
/* 下方向のマスを探索候補としてキューに格納*/
enqueue(&queue, &pos);
}
if (check(i - 1, j)) {
/* 左方向に辿れる場合 */
pos.i = i - 1; /* 左方向のマスのi座標 */
pos.j = j; /* 左方向のマスのj座標 */
pos.b_i = i; /* 左方向のマスの前に辿ったマスのi座標 */
pos.b_j = j; /* 左方向のマスの前に辿ったマスのj座標 */
/* 左方向のマスを探索候補としてキューに格納*/
enqueue(&queue, &pos);
}
if (check(i + 1, j)) {
/* 右方向に辿れる場合 */
pos.i = i + 1; /* 右方向のマスのi座標 */
pos.j = j; /* 右方向のマスのj座標 */
pos.b_i = i; /* 右方向のマスの前に辿ったマスのi座標 */
pos.b_j = j; /* 右方向のマスの前に辿ったマスのj座標 */
/* 右方向のマスを探索候補としてキューに格納*/
enqueue(&queue, &pos);
}
}
return ret;
}
int main(void) {
initQueue(&queue);
/* ゴールの位置を設定 */
maze[5][3] = GOAL;
/* スタート位置を(1,3)として開始 */
if (search(1, 3)) {
printf("ゴールが見つかりました！\n");
} else {
printf("ゴールが見つかりません！\n");
}
return 0;
}幅優先探索のサンプルプログラム（グラフ）
最後にグラフから幅優先探索で探索を行う場合のサンプルプログラムも紹介しておきます。
今まで示してきたサンプルプログラムと同様に、深さ優先探索のサンプルプログラム（グラフ） で紹介したソースコードのスタックに関する部分をキューのものに変更してやれば、グラフからの幅優先探索での探索を実現することが可能です。
#include <stdio.h>
#include <stdbool.h>
/* グラフのサイズ */
#define GRAPH_SIZE 11
/* エッジの最大数 */
#define MAX_EDGE 4
/* 管理するデータの上限個数 */
#define MAX_NUM GRAPH_SIZE
#define QUEUE_SIZE (GRAPH_SIZE + 1)
/* 各ノードの位置情報 */
typedef struct POS {
int i; /* ノードの位置 */
int b_i; /* １つ前に辿ったノードの位置 */
} POS_T;
/* キュー構造体 */
typedef struct QUEUE {
/* データの最後尾 */
int tail;
/* データの先頭 */
int head;
/* キューされているデータ */
POS_T data[QUEUE_SIZE];
} QUEUE_T;
QUEUE_T queue;
POS_T trace[GRAPH_SIZE];
POS_T route[GRAPH_SIZE];
int graph[GRAPH_SIZE][MAX_EDGE];
int searched[GRAPH_SIZE];
/* グラフを作成する関数 */
void initGraph(void) {
graph[0][0] = 1; graph[0][1] = 2; graph[0][2] = -1; graph[0][3] = -1;
graph[1][0] = 3; graph[1][1] = 0; graph[1][2] = -1; graph[1][3] = -1;
graph[2][0] = 0; graph[2][1] = 4; graph[2][2] = -1; graph[2][3] = -1;
graph[3][0] = 1; graph[3][1] = 5; graph[3][2] = -1; graph[3][3] = -1;
graph[4][0] = 2; graph[4][1] = 6; graph[4][2] = -1; graph[4][3] = -1;
graph[5][0] = 3; graph[5][1] = -1; graph[5][2] = -1; graph[5][3] = -1;
graph[6][0] = 7; graph[6][1] = 4; graph[6][2] = 8; graph[6][3] = -1;
graph[7][0] = 9; graph[7][1] = 6; graph[7][2] = -1; graph[7][3] = -1;
graph[8][0] = 6; graph[8][1] = -1; graph[8][2] = -1; graph[8][3] = -1;
graph[9][0] = 7; graph[9][1] = 10; graph[9][2] = -1; graph[9][3] = -1;
graph[10][0] = 9; graph[10][1] = -1; graph[10][2] = -1; graph[10][3] = -1;
}
/* キューを初期化する関数 */
void initQueue(QUEUE_T *queue){
/* キューを空に設定 */
queue->head = 0;
queue->tail = -1;
}
/* ENQUEUEする関数 */
void enqueue(QUEUE_T *queue, POS_T *input){
/* キューが満杯なら何もせず関数終了 */
if((queue->tail + 2) % QUEUE_SIZE == queue->head){
printf("キューが満杯でENQUEUEできません\n");
return;
}
/* データをデータの最後尾の１つ後ろに格納 */
queue->data[(queue->tail + 1) % QUEUE_SIZE] = *input;
/* データの最後尾を１つ後ろに移動 */
queue->tail = (queue->tail + 1) % QUEUE_SIZE;
}
/* DEQUEUEする関数 */
POS_T *dequeue(QUEUE_T *queue){
POS_T *ret;
/* キューが空なら何もせずに関数終了 */
if((queue->tail + 1) % QUEUE_SIZE == queue->head){
printf("キューが空です\n");
return NULL;
}
/* データの先頭からデータを取得 */
ret = &(queue->data[queue->head]);
/* データの先頭を１つ後ろにずらす */
queue->head = (queue->head + 1) % QUEUE_SIZE;
/* 取得したデータを返却 */
return ret;
}
/* ゴールまでの経路を出力する関数 */
void printRoute(int num_trace) {
int n;
int count = 0;
/* ゴールからスタートまでの経路をrouteに格納 */
/* 最後に通過したノードの情報のtrace上の位置 */
n = num_trace - 1;
while (true) {
POS_T pos = trace[n]; /* 通過したノードの情報を取得 */
route[count] = pos; /* 通過したノードを覚えておく */
count++;
if (pos.b_i == -1) {
/* 通過したノードスタートなら終了 */
break;
}
for (int m = n - 1; m >= 0; m--) {
/* posの前に通過したノードの情報が格納されているtrace上の位置を探索 */
if (trace[m].i == pos.b_i) {
/* posの前に通過した位置はtrace[m]に格納されている */
n = m;
break;
}
}
}
/* ゴールからスタートまでの経路を逆順に表示 */
for (int m = count - 1; m >= 0; m --) {
printf("%d,", route[m].i);
}
printf("\n\n");
}
/* スタートからゴールを探索する関数*/
bool search(int s_i, int g_i) {
POS_T pos;
int num_trace;
bool ret;
pos.i = s_i;
pos.b_i = -1;
enqueue(&queue, &pos); /* キューにノードの情報を格納*/
num_trace = 0;
while (true) {
int i;
/* キューから次の探索候補のノードを取得*/
POS_T *next = dequeue(&queue);
if (next == NULL) {
/* 次の探索候補がない場合は探索失敗 */
ret = false;
break;
}
/* 探索するノードの座標を取得 */
i = next->i;
/* 探索するノードを探索済のノードとして覚えておく */
trace[num_trace] = *next;
num_trace++;
if (i == g_i) {
/* 探索対象が見つかったので探索成功 */
printf("ゴールに到着\n");
printRoute(num_trace);
ret = true;
break;
}
/* 探索済みのノードに印をつける */
searched[i] = 1;
for (int e = 0; e < MAX_EDGE; e++) {
if (graph[i][e] != -1) {
if (searched[graph[i][e]] != 1) {
pos.i = graph[i][e];
pos.b_i = i;
enqueue(&queue, &pos);
}
}
}
}
return ret;
}
int main(void) {
initQueue(&queue);
initGraph();
/* スタートの位置を0、ゴールの位置を10として開始 */
if (search(0, 10)) {
printf("ゴールが見つかりました！\n");
} else {
printf("ゴールが見つかりません！\n");
}
return 0;
}まとめ
このページでは、基本的な探索アルゴリズムである「深さ優先探索」と「幅優先探索」について解説しました！
深さ優先探索は探索候補の中から「スタートからの距離が一番遠い候補を優先しながら探索を行うアルゴリズム」であり、幅優先探索は「スタートからの距離が一番近い候補を優先しながら探索を行うアルゴリズム」となります。
この違いがあるため、当然探索順は２つのアルゴリズムで大きく異なることになります。が、実は実現方法はほぼ同じで、利用するデータ構造を変えるだけで、深さ優先探索からの幅優先探索への変更や、幅優先探索からの深さ優先探索への変更を行うことができます。
具体的には、探索候補の保存＆次の探索先の取得を行うデータ構造としてスタックを利用すれば深さ優先探索になりますし、キューを利用すれば幅優先探索となります。
この「利用するデータ構造の違いだけ」で２つの探索アルゴリズムを実現できるという点が、深さ優先探索と幅優先探索の面白いところだと思います！
システムやアプリを開発する際に探索を行う機会は結構多いと思いますので、このページで紹介した深さ優先探索と幅優先探索の特徴については是非覚えておいてください！
