今回はグラフの探索の基本的なアルゴリズムである深さ優先探索と幅優先探索を学んでいきましょう！エンジニア就活等で出題されるコーディングテストでは頻出のお題なので、ぜひマスターしたいアルゴリズムです。
Contents
グラフ探索
今回紹介する「深さ優先探索」と「幅優先探索」はグラフと呼ばれるノード（頂点）とエッジ（辺）で構成されるデータ構造を探索する際に使用されるアルゴリズムです。一番わかりやすい例は迷路や家系図などです。
さて、私たち人間は頭の中で家系図や友好関係を辿って特定の人物を発見すると言ったことをなんとなく行っています。しかしコンピュータに同じことをさせる時、どのようにプログラミングすれば良いのでしょうか？
そんな時に役立つのが、今から学習していくグラフ探索アルゴリズムです。皆さんはこの学習を終えると簡単なグラフ探索をコンピュータにさせることができるようになります。楽しんで学習していきましょう！
深さ優先探索（DFS）
深さ優先探索とは？
まずは、深さ優先探索を学んでいきましょう。
下の図のようなシンプルな二分木（枝が二つに分かれている木のこと）構造のデータを考えます。皆さんはコンピュータにこの木の一番上の頂点（ルート）から全ての頂点（ノード）をチェックしに行ってもらうように手順（アルゴリズム）を考えなければなりません。さて、どのように探索しましょうか…？
そこで深さ優先探索が登場します。今回は混乱を避けるため深さ優先探索の中でも「行きがけ順」に限定して説明していきます。深さ優先探索には行きがけ順の他に「帰りがけ順」、「通りがけ順」があります。
深さ優先探索ではノードを下に下に降りていくように探索します。そして、一番深いところまで辿り着いたら、今度はひとつ前のノードに戻ってまた下に下に降りていきます。深さ優先探索はこの繰り返しです。行きがけ順の場合は次の図のように二分木を進んでいきます。
コードにこの手順を落とし込めるように言語化すると、次のフローチャートにしたがって探索していきます。
深さ優先探索のPython実装
ではPythonで深さ優先探索を実装してみましょう！
次のような二分木の全てのノードを深さ優先探索を使って探索していきます。
まずは、この二分木をデータとして表していきます。
木構造データの作成
今回は次のクラスを使ってノード間の繋がりを作っていきます。
このTreeNodeクラスは、あるノードに対してその左下と右下に繋がっているノードが何なのかを定義します。具体的にはTreeNodeがインスタンス化される際にvalに対象のノードの値を、leftに左下のノードを、そしてrightに右下のノードを入れて与えてあげることで左下と右下のノードを登録できます。上のエディタでTreeNodeに登録するノードの値を変えてみて、イメージを膨らませてみてください。
では実際にこのクラスを使って木構造を作ってみましょう。
まず、treeというリストの変数は今回使用する木構造を表しています。このtreeに含まれている全てのノードについて、右左のノードを登録していく必要があります。その全てのノードについてつながりを登録していく関数がmake_tree()です。再帰的に（node.leftを登録して、node.left.leftを登録して…）ノードの登録を行なっているので少し複雑に見えるかもしれませんが、あくまでノード間のつながりを全てのノードに関して登録している関数です。そして、最後の行でroot、つまりスタート地点を受け取っています。
探索部分の実装
さて、ここまでで木構造の実装が完成しました。ここからいよいよ深さ優先探索を実装していきます。
今回の問題では深さ優先探索でたどったノードを順番に集めていけば良いです。したがって、ansというリストにチェックした順にノードを追加していく方針で実装しています。
ここでアルゴリズムの実装に必要になるデータ構造があります。それはスタックというデータ構造です。
深さ優先探索の実装にはスタックを使うことが多いです。スタックは「後入れ・先出し」と表されます。つまり、最後に入れたデータが最初に取り出されるということです。今回はdequeというスタックにもキュー（←幅優先探索で説明します）にもなるライブラリが用意しているメソッドを使ってスタックのデータ構造を実装します。
まずは、このスタックを変数stackとし、スタート地点のノードを入れます。ここからが深さ優先探索の本番です。最初にスタート地点のみが入っているstackからrootノードを取り出します。このノードには、左下と右下のノードを登録していたので、ノードの有無を調べることができます。ここで重要なのは、次に右と左のどちらのノードをstackに追加するかです。今回は左側から優先して探索していく（行きがけ順）ので、次のループに入った時に左側が最初に取り出されなければなりません。スタックでは最後に入れたものが先に取り出されるので、最初に右側のノードを、その次に左側のノードを追加すれば良いです。
# 木を作成
root = make_tree(tree, None, 0, len(tree))
# 答えを入れるためのリスト
ans = []
# スタックというデータ構造にリストを変換
stack = deque([root])
# 深さ優先探索の開始
#stackが空にならない限りループを続ける
while stack:
#stackの右側から要素を一つ取り出す
node = stack.pop()
#ans（答え）に追加
ans.append(node.val)
#もし右側のノードが存在するならstackに追加
if node.right:
stack.append(node.right)
#もし左側のノードが存在するならstackに追加
if node.left:
stack.append(node.left)
print(ans)このループを未探索のノードがなくなるまで続けることで、全てのノードを深さ優先探索することができます。下に全体のコードを記載しておくのでtree変数の要素を変えてみたり、stackに追加するノードを右と左で順番を変えてみてイメージを掴んでみてください！
幅優先探索（BFS）
幅優先探索とは？
ここでも先ほどと同様に二分木の全てのノードを探索するアルゴリズムを考えます。
幅優先探索は深さ優先探索とは逆に横に横にノードを移っていきます。そして一番右に到達すると、今度はひとつ下の一番左のノードに移って、また右に右に移っていきます。幅優先探索はこの繰り返しです。
今回もアルゴリズムをコードに落とし込むために、フローチャートをみてイメージをより具体化してみましょう。
幅優先探索のPython実装
木構造データの作成
今回も深さ優先探索の時と同様の二分木を使用しましょう。
ですのでノードの登録までは深さ優先探索の時と全く同じです。もう一度確認したい人は深さ優先探索セクションの木構造データ作成部分を見返してみてください。
探索部分の実装
深さ優先探索と大きく異なるのは使用するデータ構造です。幅優先探索ではキューというデータ構造を使用します。
キューはスタックと逆で「先入れ・先出し」と表されます。つまり、最初に入れたデータが最初に取り出されるということです。
幅優先探索は先ほどの深さ優先探索で行ったループのデータ構造をキューにすることで実装できます。
まずはこのキューを変数queueとし、スタート地点のノードを入れます。
ここからが幅優先探索の本番です。
まずスタート地点のみが入っているqueueからノード（スタート地点のノード: root）を取り出します。深さ優先探索の時と同様、それぞれのノードには左下ノードと右下ノードを登録していたので、ノードの有無を調べることができます。深さ優先探索の時は左側を優先して下に下に探索するためにスタック（先入後出し構造）に右のノードを先に入れることで、左のノードを先に取り出していました。今回はキューを使用しているので先に入れたものが先に取り出されます。なので、左ノードを先に入れ、次に右ノードを次に入れてあげることで、次のループで左ノードが先に取り出され、次に右ノードが取り出されます。
# 木を作成
root = make_tree(tree, None, 0, len(tree))
# キューというデータ構造にリストを変換
queue = deque([root])
# 幅優先探索の開始
# queueが空にならない限りループを続ける
while queue:
#queueの左側から要素を一つ取り出す
node = queue.popleft()
#ans（答え）に追加
ans.append(node.val)
#もし左側のノードが存在するならqueueに追加
if node.left:
queue.append(node.left)
#もし右側のノードが存在するならqueueに追加
if node.right:
queue.append(node.right)
print(ans)このループを未探索のノードがなくなるまで続けることで、全てのノードを幅優先探索することができます。ここでも深さ優先探索の時と同様にtreeの要素を自分で変えてみて幅優先探索のイメージを掴んでください。
二つのアルゴリズムの使い分け
さて、皆さんは二つのグラフ探索アルゴリズムをマスターしました。しかし、これらのアルゴリズムをどのように使い分ければ良いのでしょうか？実際には次のような場合分けができます。
- 深さ優先探索
- 全ての経路を探索して、比較する時
- 幅優先探索
- スタート地点に近いところに正解（ゴールなど）がある時
幅優先探索では分岐数が非常に多い木の場合キューに入ってくるデータが非常に多くメモリ効率が悪くなってしまいます。一方で深さ優先探索では分岐が多い木であったとしても、一つの分岐について探索していくので多くの場合でメモリ効率が良いです。なので、全てを探索する時、多くの場合で深さ優先探索の方がメモリ効率がいいのです。
対して、スタート地点に近いところにゴールがある場合を考えてみます。もしこのような場合で深さ優先探索を使用してしまうと、ゴールがない深い分岐に囚われてしまい、ゴールを見つけるまでに時間がかかってしまいます。このような時は幅優先探索を使用する方が良いことがわかりますね。
使い分けの具体的なイメージを掴むための例題を解いてみましょう。
例題1
問題
上のような二分木があります。この木の一筆書き辿ることのできる経路のうち、もっともノードの値の和が大きくなる経路の和は何でしょう。
皆さんの力で少し考えて実装してみましょう。下のエディタの問題タブにコードを書いて動かしながら問題を解いてみてください。
問題の方針とヒント
さて、問題を読むとグラフ探索の問題であることは明らかです。つまり、皆さんが学習した深さ優先探索と幅優先探索を駆使して解くことができます。しかし、問題なのはどちらを使うほうがいいのかということです。
ポイントになるのは「全ての経路を探索する必要があるのか？」ということです。
今回の問題では「最もノードの値の和が大きい経路を見つけよ」ということなので、これは全ての経路を調べてから比較して、最も大きい和の経路を答えとするほうがよさそうです。つまり、深さ優先探索を使用した方が良いでしょう。
そして、これまで実装してきた時との大きな違いは「一筆書きの経路の和」を求めないといけない点です。つまり、経路の和を記録しておく変数が新たに必要ですね。
解答と解説
上のエディタの解答タブを開いて解答を確認してみましょう。
今回の問題ではヒントとして示したように、全ての経路を辿ってから、その和を比較して答えを求める必要があります。したがって、深さ優先探索を使って木を探索していきます。まず変数として用意したのはansとsum、rootとstackです。それぞれの役割は次のようになっています。
ans: それぞれの経路の和を記録しておくためのリストsum: 経路を辿る途中の和を記録しておくための変数root: 木構造データstack: ノードとそのノードにたどり着いた時点の経路の和がタプルとして入れられたスタック
# 各経路の和を保存しておくためのリスト
ans = []
# 各経路の和
sum = 0
# 木の作成
root = make_tree(tree, None, 0, len(tree))
# 深さ優先探索なのでスタックに変換
# 和も一緒に記録しておく必要がある
stack = deque([(root, sum)])先ほど行った深さ優先探索と大きく異なるのは、スタックにノードと一緒に和も入れられている点です。このように和も一緒に記録しておくことで、行き止まりにたどり着いて、一つ上のノード（親のノード）にたどり着いた時に、和の計算を再開することができます。
いよいよ本題の深さ優先探索のパートに入っていきます。
大枠は先ほど行った深さ優先探索と同じですが、和を計算・記録する部分が加わっているのがわかります。具体的には、次のコードのように実装していきます。
# 現在地と現在の和を取り出す
node, current_sum = stack.pop()
# 現在のノードの値を足す
current_sum += node.valstackには、ノード: nodeとひとつ前のノードまでの和: current_sumが入っているので取り出します。そして、ひとつ前のノードまでの和に現在のノードの値を加算して、現在の和を更新します。
さらに必要な部分が、行き止まりを検知してその一筆書きの経路の和を確定する部分です。この部分に該当するのが下のコードです。
# もし行き止まりなら経路の和を確定させてansに格納
if not node.left and not node.right:
ans.append(current_sum)ここでは、もし現在のノードが行き止まり、つまり左にも右にもノードがない（None）状態であれば、和を確定させ、ansに格納するということをしています。
あとは、stackに（右のノード、現在の和）→（左のノード、現在の和）の順で追加してあげることで深さ優先探索を先ほどと同様に進めることができます。
最後にansに格納された各経路の和の最大値を求めることで最終的な答えとしています。
# 各経路の和を保存しておくためのリスト
ans = []
# 各経路の和
sum = 0
# 木の作成
root = make_tree(tree, None, 0, len(tree))
# 深さ優先探索なのでスタックに変換
# 和も一緒に記録しておく必要がある
stack = deque([(root, sum)])
# 深さ優先探索の開始
while stack:
# 現在地と現在の和を取り出す
node, current_sum = stack.pop()
# 現在のノードの値を足す
current_sum += node.val
# もし行き止まりなら経路の和を確定させてansに格納
if not node.left and not node.right:
ans.append(current_sum)
# 左右のノードをstackに追加
if node.right:
stack.append((node.right, current_sum))
if node.left:
stack.append((node.left, current_sum))
# 最後に各経路の最大値を求める
print(max(ans))例題2
先ほど使用した木と似ていますが、今回は分岐の仕方が偏った木を使用してみます。
問題
この二分木の行き止まりのノードを一つ見つけて、その値を返しなさい。
この問題も、ぜひ一度皆さんの力で考えて下のエディタで実装してみてください。
問題の方針とヒント
今回は行き止まりのノードの値をどれか一つだけ答えればいいです。つまり、全ての経路を探索する必要がありません。さらに、比較的近い位置に行き止まりがあることもわかります。
したがって、幅優先探索で行き止まりに辿り着いた時点で探索を中断し、答えを返すのが良いでしょう。
解答と解説
エディタの解答タブから解答を確認してみましょう。
この問題ではヒントとして示したように
- 全ての経路を比較する必要がない
- 比較的近くに答えになる点がある
というポイントから幅優先探索を選択します。
先ほど行った最も基本的な幅優先探索と大きく異なるのは、行き止まりを検知してループを抜ける点です。該当するのは次のコードです。
# 左にも右にもノードがないなら行き止まり
# ループを抜ける
if node.left is None and node.right is None:
print(node.val, "がいきどまりです")
breakこれは現在のノードの右と左のどちらにもノードがない（None）場合に答えとなる現在の行き止まりのノードの値を返しbreakでwhileループを抜けるということをおこなっています。
あとは、最も基本的な幅優先探索と同様に左のノード→右のノードの順でキューqueueに追加することで深さ優先探索を進めていくことができます。
# 木の作成
root = make_tree(tree, None, 0, len(tree))
# 幅優先探索なのでキュー
queue = deque([root])
# 幅優先探索の開始
while queue:
# 現在のノードを取り出す
node = queue.popleft()
# 左にも右にもノードがないなら行き止まり
# ループを抜ける
if node.left is None and node.right is None:
print(node.val, "がいきどまりです")
break
# 左右のノードをqueueに追加
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)この問題を深さ優先探索で解いてしまうと、最初の深い分岐にはまってしまって、答えを返すまでに幅優先探索に対して長い時間がかかるのがわかると思います。実際にキューをスタックに変更して深さ優先探索で問題を解いてみて、使い分けの重要性を実感してみるのもいいかもしれません。
練習問題（より現実的な問題への応用）
例題では深さ優先探索と幅優先探索のそれぞれの使い分けのイメージを膨らませるために、シンプルな問題を解きました。今回はさらに現実的な問題として、迷路の脱出の可否を判定する問題を解いてみましょう。
問題
空白のセル: ‘.’と壁: ‘#’を持つm×nの行列（二重にネストしたリスト）が与えられます。ここで、start = [行番号, 列番号]（インデックスは0始まり） は、あなたが最初に立っているセルの行と列を表します。壁のあるマスは立ち入ることができず、通り抜けることもできません。また、斜めに移動することはできません。
もし出口: goal = [行番号, 列番号]に辿り着くことができれば1を、そのような経路が存在しない場合は-1を返しなさい。
ケース1
これは3×3の迷路で、start=[0, 0]、goal=[2, 1]の場合です。この場合、startからgoalまでは辿り着くことができるので1を返すべきです。
ケース2
これは3×3の迷路で、start=[0, 0]、goal=[2, 1]の場合です。この場合、startからgoalまでは辿り着くことができないので-1を返すべきです。
今回のケース
回答と解説
この問題では、与えられた迷路が解くことができるものなのか否かを判定するプログラムを作成しなければなりません。迷路なんてこれまで扱ってきた二分木とは全く違うじゃないか！と感じる方がいるかもしれませんが、実は迷路もグラフ構造として表すことができます。迷路のつながりがエッジ、立ち止まる点や壁がノードと考えると、まさにグラフ構造で迷路を表すことができるとわかります。
となると、いままで学習してきた深さ優先探索と幅優先探索を使うことができます。では、どちらのアルゴリズムを使用する方が見通しがいいでしょうか？ポイントは問題文の「goalまで辿り着くことができるかどうかを判定しなさい」という部分です。この問題では迷路の全ての経路を探索する必要はなく、どこか一つの出口を見つけられれば良いということになります。したがって、幅優先探索を使用して迷路を解いていきましょう。
まず下準備として例のごとく、スタート地点の座標をキューに入れます。さらに、迷路で進むことができる方向をdirectionにまとめておいて後で使えるようにしていきます。そして、探索した地点を壁: “#” として登録することで、探索済みであることをマークしておきます。
# 幅優先探索のためのキュー
queue = deque([start])
# 移動できる方向をまとめておく
directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
# スタートを探索済みに変える
maze[start[0]][start[1]] = "#" 幅優先探索の部分に当たるwhileループの中を見ていきましょう。まずは、キューから先ほど入れたスタート地点の座標を取り出しています。ここで取り出された座標が現在地の座標です。現在地がgoalの座標と一致するならば、それはgoalに辿り着いたということですので、1を表示してループを抜けます。もしgoalでないところならば、次に進む点を探します。その部分がfor文の中です。最初に下準備としてdirectionに進むことのできる[右、左、上、下]をまとめておいたので、このdirectionを使ってそれぞれの方向に進むことができるかどうかを判定しています。もし、進むことができる（壁ではない、迷路の外ではない）ならば、キューに追加して次のループでgoalかどうかを判定します。そして、最後にキューに追加した座標（次のループで探索する座標）を探索済みとして”#”でマークすることで一回分のループが完了します。これを繰り返していくことで深さ優先探索で迷路のゴールを探すことができるのです。
# 幅優先探索開始
while queue:
# 現在地の座標を取り出す
x, y = queue.popleft()
# もしgoalの座標と現在地の座標が一致するなら
if x == goal[0] and y == goal[1]:
# 1を表示してループを抜ける
print(1)
break
# 右、左、上、下に行けるかどうかを判定する
for dx, dy in directions:
# 現在地を次の地点に進める
nx, ny = x + dx, y + dy
if 0 <= nx < len(maze) and 0 <= ny < len(maze[0]) and maze[nx][ny] == ".":
# もし次の地点が壁でない、かつ、迷路の外でないならば
queue.append([nx, ny])
# キューに次に地点を追加して、探索済みにマーク
maze[nx][ny] = "#"
# 全地点を探索し終わったなら迷路は解けないということ
print(-1) 急に問題の毛色が変わって難しく感じた人もいるかもしれませんが、この解説を読んで、再度自分の手で実装してみることで理解が深まると思いますので、ぜひもう一度自分の手で解答を作ってエディタでコードを走らせてみてください。
まとめ
今回は深さ優先探索と深さ優先探索という、グラフ探索アルゴリズムの中でも最も基本的なものを学習しました。これらのアルゴリズムをマスターすることで、他の探索アルゴリズムの学習につながり、さまざまな問題を解くことができるようになります。ですので、ぜひ例題の解答を自分の力で実装できるように、自分で本記事のエディタでコーディングをしてみてください。
