擬似言語で見る幅優先探索と深さ優先探索の違い｜たどる順番を解説

幅優先と深さ優先、名前は覚えたのに、どっちがどっちの順番なのか毎回迷う。

問題文に探索という言葉が出てきた瞬間、手が止まっていませんか？

大丈夫です。この2つの違いは、たった1つのことに集約できます。

それは、次に調べる節点をどこから取り出すか、という点です。取り出し方が変わるだけで、同じ図でもたどる順番がまったく変わります。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。画面の階層メニューを表示したり、組織図のような親子関係のデータを処理したりと、実務でもこの2つのたどり方は何度も使ってきました。

この記事では、文法の説明ではなく、2つの探索がどう動くのかという仕組みを、擬似言語のコードとトレース表で一つずつ確かめていきます。

科目B全体でアルゴリズムがどう問われるのかを先に押さえたい人は、親記事から読むと位置づけがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

幅優先探索と深さ優先探索とは¶

まずは、2つの探索がそれぞれどんなイメージなのかをつかみましょう。ここでは、節点同士が線でつながった図をたどる場面を考えます。

幅優先探索は、出発点から近い節点を先に全部調べる方法です。出発点のすぐ隣を全部見てから、その隣の隣へ進みます。

池に石を投げたときの波紋を思い浮かべてみてください。波は中心から、同じ距離の場所へ同時に広がっていきます。

深さ優先探索は、行けるところまで一本道で進む方法です。行き止まりになったら一つ前の分かれ道まで戻り、まだ行っていない道を試します。

こちらは迷路を手探りで進む人のイメージです。壁に当たるまで進み、当たったら戻って別の道を選びます。

2つの違いを表にまとめると、次のようになります。

ここで一番大事なのは、使う仕組みの行です。幅優先はキュー、深さ優先はスタック。この対応さえ覚えておけば、コードを見たときにどちらか判断できます。

キューとスタックの出し入れの順番がまだあいまいな人は、こちらの記事で先に確かめておくと、この先がぐっと読みやすくなります。

【関連記事】擬似言語のスタックとキューの違いとは？科目Bで出る出し入れの順番を解説

例として使う図¶

ここからは、同じ図を使って2つの探索を比べます。節点は 1 から 6 までの6つで、次のようにつながっているとします。

5 と 6 がつながっているので、この図は1周して元に戻れる道を含んでいます。ここが、あとで2つの探索の違いをはっきり見せてくれるポイントです。

出発点は節点 1 とします。隣の節点が複数あるときは、番号の小さいほうから調べることにします。

訪問済みの印がないと同じ節点を何度も回る¶

もう一つ、コードを読む前に押さえておきたいことがあります。それは、一度調べた節点に印を付けておく仕組みです。

この図では、1 から 2、5、6、3 と進むと、また 1 に戻ってこられます。印を付けておかないと、同じ道を永遠に回り続けてしまいます。

そこでどちらの探索でも、訪問済みかどうかを記録する配列を用意します。コードの中では、この配列を確かめる if 文が必ず出てきます。

幅優先探索を擬似言語で読む¶

それでは、幅優先探索のコードから見ていきましょう。IPAの公開問題そのものではなく、試験でよく見かける形をもとに作った例です。

つながりは二次元配列 adj で表し、節点 i と j がつながっていれば adj[i, j] が 1、そうでなければ 0 とします。訪問済みの印は論理型の配列 visited で管理します。

大域: 整数型の二次元配列: adj
大域: 論理型の配列: visited

○bfs(整数型: start, 整数型: n)
  整数型の配列: queue ← {n個の 0}
  整数型: head, tail, v, w
  head ← 1
  tail ← 1
  queue[tail] ← start
  tail ← tail + 1
  visited[start] ← true
  while (head < tail)
    v ← queue[head]
    head ← head + 1
    v を出力する
    for (w を 1 から n まで 1 ずつ増やす)
      if ((adj[v, w] が 1 と等しい) and (visited[w] が false と等しい))
        visited[w] ← true
        queue[tail] ← w
        tail ← tail + 1
      endif
    endfor
  endwhile

queue は配列ですが、head から取り出して tail に入れているので、先に入れたものが先に出てきます。つまり、これはキューの動きです。

visited に true を入れるタイミングにも注目してください。キューに入れた時点で印を付けているので、同じ節点が二重にキューへ入ることはありません。

トレース表で訪問順を追う¶

では、出発点 1 で動かしてみます。取り出した節点と、そのときのキューの中身を1行ずつ表にしていきます。

出力される順番は、1、2、3、4、5、6 です。1 から見て、1歩で行ける 2 と 3、2歩で行ける 4、5、6 の順に並んでいるのが分かるでしょうか。

5 回目で 6 を入れなかった理由は、3 回目の時点ですでに印が付いていたからです。印を付けるのがキューに入れた時点なので、6 は二重に入りません。

幅優先が最短の手数を求められる理由¶

幅優先探索は、近い節点から順番に取り出していきます。そのため、ある節点に初めてたどり着いたときの手数が、そのまま最短の手数になります。

実際に、この図で 1 から 6 へ行く道は、1、3、6 と 1、2、5、6 の2通りあります。幅優先では 3 から先に 6 を見つけるので、短いほうの2歩の道が選ばれます。

乗り換え案内やゲームの最短経路のように、手数の少ない道を知りたい場面で幅優先が使われるのは、この性質があるからです。

深さ優先探索を擬似言語で読む¶

次は、深さ優先探索です。試験では、再帰呼び出しを使って書かれることがよくあります。

○dfs(整数型: v, 整数型: n)
  整数型: w
  visited[v] ← true
  v を出力する
  for (w を 1 から n まで 1 ずつ増やす)
    if ((adj[v, w] が 1 と等しい) and (visited[w] が false と等しい))
      dfs(w, n)
    endif
  endfor

幅優先のコードと比べると、キューがどこにもありません。代わりに、未訪問の隣を見つけたら、その場で dfs を呼び出しています。

呼び出された側の処理が全部終わるまで、呼び出した側の for は次へ進みません。この待ち方が、一本道で奥まで進んでから戻る動きを生み出しています。

再帰呼び出しの流れそのものに不安がある人は、呼び出しと戻りの追い方を解説したこちらの記事で基本を固めておくと安心です。

【関連記事】基本情報科目Bの再帰呼び出しがわからない人への対策方法を解説｜擬似言語で処理を追うコツ

呼び出しの深さを表で追う¶

深さ優先のトレースは、今どこまで呼び出しが重なっているかを書いておくのがコツです。呼び出しの段数を深さとして、表にしてみます。

出力される順番は、1、2、4、5、6、3 です。幅優先とは、3 の位置がまったく違いますね。

3 は出発点 1 のすぐ隣なのに、最後に出てきました。深さ優先では、2 の先の道を奥まで進むうちに、5 と 6 を経由して反対側から 3 にたどり着いたからです。

再帰を使わずにスタックで書くこともできる¶

深さ優先探索は、再帰の代わりにスタックを使って書くこともできます。未訪問の隣をスタックに積み、後から積んだものを先に取り出すと、同じように奥へ奥へと進みます。

ただし、スタックで書くと、隣を積む順番によって訪問順が変わることがあります。番号の小さい順に積むと、大きいほうが先に取り出されるからです。

試験でスタック版が出たときは、隣を積む順番と取り出す順番を、必ず表に書いて確かめましょう。思い込みで答えると、ここで失点しやすくなります。

2つの探索を見分けるポイント¶

ここまでで、同じ図でも訪問順が変わることを確かめました。では、試験のコードを見たとき、どこでどちらの探索か判断すればよいのでしょうか。

見るべき場所は、次に調べる節点の取り出し方です。判断の手がかりを表にまとめると、次のようになります。

head と tail のように2つの位置を別々に動かしていたら、キューを疑ってください。1つの位置だけを増やしたり減らしたりしていたら、スタックの可能性が高いです。

二分木のたどり方との関係¶

実は、二分木の走査で学ぶ行きがけ順は、深さ優先探索の一種です。左の子へもぐれるだけもぐり、戻ってから右へ進むという動きは、ここまで見た dfs とまったく同じ形をしています。

一方、木を上の段から1段ずつ左から右へ読んでいくたどり方は、幅優先探索にあたります。木の問題とグラフの問題は、同じ考え方でつながっているのです。

二分木の走査順をもう一度整理しておきたい人は、節点をたどる順番を設問の形で解説したこちらの記事が役に立ちます。

【関連記事】科目Bの二分木問題の解き方｜節点をたどる順番を解説

よくある間違いと確認のしかた¶

最後に、訪問順を答えるときによくある間違いを確認しておきます。どれも、表を書けば防げるものばかりです。

特に多いのが、2つ目の visited の見落としです。印を付けるのがキューに入れた時点なのか、取り出した時点なのかで、同じ節点がキューに入る回数が変わります。

私も実務で、親子関係をたどる処理で同じデータを二重に処理してしまう不具合に出会ったことがあります。原因は、訪問済みの印を付ける位置が1行ずれていたことでした。

試験のコードでも、印を付ける行の位置は空欄補充の定番です。どの行で true にしているかは、必ず自分の目で確かめてください。

シミュレーターで動かして確かめる¶

ここまで紙の上で追ってきましたが、最後は実際に動かしてみるのが一番確実です。自分で書いた訪問順と、実際の出力が一致するかを確かめられるからです。

Giji Academyの擬似言語シミュレーターでは、擬似言語のコードを1行ずつ動かし、変数や配列の値が変わる様子を見ることができます。head と tail が進んでいく様子や、再帰で呼び出しが重なっていく様子を目で見ると、2つの探索の違いがはっきりします。

おすすめは、同じ図で出発点だけを変えて試すことです。出発点を 6 にすると、幅優先と深さ優先の訪問順がどう変わるかを予想してから動かしてみてください。

予想と結果がずれたら、それが理解のすき間です。どの行で考えがずれたのかを探すと、次の問題で同じ間違いをしなくなります。

自分で手を動かして確かめたい人は、Giji Academyの擬似言語シミュレーターから配列や再帰の講座を選んでみてください。読むだけの勉強より、ずっと記憶に残ります。

科目Bで出るほかのアルゴリズムも合わせて整理したい人は、型ごとに一覧にしたこちらの記事から学ぶ順番を決めるのもおすすめです。

【関連記事】擬似言語で押さえるアルゴリズム一覧｜科目Bで出る型を整理して解説

まとめ¶

幅優先探索と深さ優先探索の違いは、次に調べる節点をどこから取り出すかにあります。幅優先はキューで近い節点から広がり、深さ優先はスタックや再帰で一本道を奥まで進みます。

同じ図でも、幅優先では 1、2、3、4、5、6、深さ優先では 1、2、4、5、6、3 と、訪問順がはっきり変わりました。この違いを生んでいたのは、取り出し方の違いだけです。

どちらの探索でも、訪問済みの印を付ける配列が欠かせません。印を付ける行の位置は、コードを読むときに必ず確かめましょう。

試験でコードを見たら、まず取り出し方に注目してください。head と tail が別々に動いていれば幅優先、自分自身を呼び出していれば深さ優先と判断できます。

最初は表を書きながらゆっくり追えば大丈夫です。何度か手を動かすうちに、名前を聞いただけで動きが頭に浮かぶようになりますよ。