【c++で楽しく実装！】深さ優先探索(DFS)&幅優先探索(BFS)

zuka

深さ優先探索（DFS）と幅優先探索（BFS）を実装するよ。

本記事では，深さ優先探索（DFS）と幅優先探索（BFS）の簡単な解説と実装例をお伝えしていきます。使用言語はc++です。その他の競技プログラミング関連の記事は，以下の目次をご覧ください。

本記事の概要

まずは，深さ優先探索（DFS）と幅優先探索（BFS）のお気持ちをお伝えしていきます。その次に，数列の列挙を題材として深さ優先探索と幅優先探索の振る舞いを確認します。最後に，それぞれの実装方法を確認していきます。

お気持ち

深さ優先探索（DFS：depth-first search）と幅優先探索（BFS：breadth-first search）は，その名の通り「探索」を実現するためのアルゴリズムです。探索というのは，鉱山から金銀財宝を発掘する作業のように，与えられた問題の答えを探し出す作業のことを指します。

与えられる問題は，しばしば「グラフ」という形式をとります。グラフというのは，中学生の頃に習った樹形図のようなもので，基本的にはノード（丸いやつ）とエッジ（丸いやつを繋ぐやつ）からなります。

グラフの特別な形として，木構造があります。木構造というのは，グラフはグラフでも内部にループを持たず，離れているグループがないようなグラフのことを指します。DFSとBFSは，木構造を意識すると理解しやすいアルゴリズムになっています。

DFSのお気持ちは，問題の答えを探すときにとりあえず猪突猛進していきたいというものです。木構造で言えば，一番上の根から一番下の葉まで一旦突き進みます。そして，答えが見つかれば終了します。答えが見つからなければ，1つ手前まで戻って方向転換します。「一番深いところから順番にみていく」というような思想を反映して，「深さ」優先探索と呼ばれています。

一方で，BFSのお気持ちは，問題の答えを探すときに近いところからしらみつぶしに調べていきたいというものです。木構造で言えば，一番上の根に近いところからじわじわ調べていきます。「一番近いところから順番にみていく」というような思想を反映して，「幅」優先探索と呼ばれています。

DFSは猪突猛進するので，解にたどり着くまでの時間が早いです。一方で，BFSはしらみつぶしに調べていくので解にたどり着くまでの時間が遅いです。しかし，最短経路問題と呼ばれるような「一番〇〇なものを求めなさい」という問題になると話は別です。DFSではスタートから初めてとりあえずゴールにたどり着きますが，その答えが最短である保証はどこにもありません。一方で，BFSは最初からしらみつぶしに調べていくので，解が見つかればその答えは最短です。

他にも，DFSでは現在の自分の位置を覚えておけば良いのでメモリの使用量が少なくすみます。一方で，BFSでは分岐していった分の結果を覚えていかなければならないのでメモリの使用量が多くなってしまいます。一般には，最短経路問題であればBFS，それ以外であればDFSが使われることが多いようです。

zuka

DFSとBFSは名前が似ていて覚えにくいね。DFSはDepth（深さ）のDでBFSはBreadth（幅）のBと理解するようにしよう。

振る舞い

さて，以下では数列の列挙を題材としてDFSとBFSの振る舞いを観察していきましょう。まずは，例題からです。

$i=1\cdots3$に対し$1 \leq A_i \leq 3$であるとき，広義単調増加数列${A_1, A_2, A_3}$を全て出力しなさい。ただし，広義単調増加数列とは$i \leq j$に対し$A_i \leq A_j$であるような数列を指す。

問題の意味はつかめそうでしょうか。例えば，答えの1つに{1,2,3}があります。この問題は，単純にはボールと仕切り棒のアイディアとbit全探索を用いて求めることができます。詳しくは，以下の記事をご覧ください。

あわせて読みたい

【競プロ精進ログ】ABC165-C 本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。 これから競技プログラミ...

今回は，DFSとBFSと用いて解答していこうと思います。まずは，DFSを用いた場合の数列列挙の流れをみていこうと思います。

実装

DFSとBFSの実装を対応づけるにはデータ構造をおさらいしておく必要があります。まずは結論からお伝えします。

・スタックが空になるまで回し続ける：DFS
・キューが空になるまで回し続ける：BFS

DFSは，スタックというデータ構造（データの入れ物）を用いて実現することができます。スタックというのは，データを入れる箱のことで，一番最後に入れられたデータが優先的に処理されるような構造をしています。本などを「積み上げて」上からとっていくイメージからStack（積み上げる）と呼ばれています。

一方，キューもデータを入れる箱のことで，一番最初に入れられたデータが優先的に処理されるような構造をしています。人が行列を作るイメージからQueue（行列）と呼ばれています。

それでは，スタックやキューには何を入れていけば良いのでしょうか。それはスバリ，完成途中の数列です。完成途中の数列に数字を付け加えていくことで，広義単調増加数列を作っていくという発想です。

要素の付け加え方と木構造における探索の対応ですが，探索対象のノードが次のノードをわたるごとに数列の要素を付け加えていきます。完成させる数列の要素数は4なので，木の深さも4になります。もし，探索対象のノードが葉になれば，その時点での数列を出力します。

日本語で説明していてもイメージが湧きにくいと思いますので，以下ではBFSとDFSにおいて数列が完成していく過程をみていきます。どちらも，初期値として{1}を与えます。DFSでは右にある要素に対して優先的に要素を付け加えていきます。一方，BFSでは左にある要素に対して優先的に要素を付け加えていきます。

DFSの場合

タブになっているので「スタック」と「出力」のそれぞれを眺めてみてください。太字になっている部分は，処理が行われる対象の要素を表しています。

zuka

スタックだから一番新しい右側の要素が優先的に処理されているよね。「出力」タブをみると広義単調増加数列が作られていく過程が分かるよ。

BFSの場合

タブになっているので「キュー」と「出力」のそれぞれを眺めてみてください。

zuka

キューだから一番古い左側の要素が優先的に処理されているよね。「出力」タブをみると広義単調増加数列が作られていく過程が分かるよ。

実装

さて，最後に実装してみましょう。

DFS

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rrep(i, n) for (int i = n; i > (int)(0); i--)
#define rrepi(i, a, b) for (int i = (int)(a); i > (int)(b); i--)
using namespace std;

int main() {
  // 作りかけの数列を格納するstackを作る
  stack<vector<int>> st;
  // 1~4の順番で出力させるために逆順で格納しておく
  rrep(i, 4){
    vector<int> initial = {i};
    st.push(initial);
  }

  // スタックが空になるまで繰り返す
  while (!st.empty()){
    // スタックの頭にあるものを取り出す
    vector<int> elem = st.top();

    // 処理した先頭の要素は削除しておく
    st.pop();

    // もし数列の長さが3であれば解答出力
    if (elem.size()==3){
        for (auto x : elem) cout << x;
        cout << endl;
      }

    // まだ数列の長さが3でなければ「前の要素以上の4以下の」要素を付け加える
    else {
      // ここでも1~4の順番で出力させるために逆順で格納しておく
      rrepi(i, 3, elem[elem.size()-1]-1){
          // 要素を付け加える新しい数列
          vector<int> elem_new = elem;
          // 要素を付け加える
          elem_new.push_back(i);
          // スタックに入れる
          st.push(elem_new);
      }
    }
  }
}

BFS

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rrep(i, n) for (int i = n; i > (int)(0); i--)
#define rrepi(i, a, b) for (int i = (int)(a); i > (int)(b); i--)
using namespace std;

int main() {
  // 作りかけの数列を格納するqueueを作る
  queue<vector<int>> que;
  // 1~4を格納しておく
  rep(i, 4){
    vector<int> initial = {i+1};
    que.push(initial);
  }

  // スタックが空になるまで繰り返す
  while (!que.empty()){
    // スタックの頭にあるものを取り出す
    vector<int> elem = que.front();

    // 処理した先頭の要素は削除しておく
    que.pop();

    // もし数列の長さが3であれば解答出力
    if (elem.size()==3){
        for (auto x : elem) cout << x;
        cout << endl;
      }

    // まだ数列の長さが3でなければ「前の要素以上の4以下の」要素を付け加える
    else {
      // ここでも1~4を格納しておく
      repi(i, elem[elem.size()-1], 4){
          // 要素を付け加える新しい数列
          vector<int> elem_new = elem;
          // 要素を付け加える
          elem_new.push_back(i);
          // キューに入れる
          que.push(elem_new);
      }
    }
  }
}

zuka

数列の生成を通してDFSとBFSの振る舞いと実装を確認したよ。

別実装

DFSはスタックを用いることから，再帰的な実装とも相性が非常に良いです。ですので，再帰を用いたDFSの実装も主流になっています。一方で，BFSはキューを用いることから，再帰とはあまり相性がよくありません。ですので，再帰を用いたBFSの実装はあまり見かけません。

そこで，今回はDFSを再帰で実装して終了ということにしたいと思います。再帰を用いたDFSでも，スタックを利用します。ただし，必ずしもスタックである必要はなく，c++ではvectorを用いればback()でスタックの一番上を取得し，push_back()でスタックの一番上に要素を追加し，pop_back()で一番上の要素を削除することができます。最後は，今までお伝えしてこなかったvectorを用いて再帰DFSを実装してみたいと思います。

再帰DFSでは，vector自身が出力したい単調増加数列を表すように設計することもできます。以下で詳しくコメントしていきます。

再帰を用いたDFS

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;

// 再帰関数
void dfs(vector<int> A) {
    // もし要素が3つあれば出力する
    if (A.size() == 3) {
      for (auto a : A) cout << a;
      cout << endl;
      return;
    }

    // 再帰の初期値の最小値は1から始める
    int last = 1;
    // Aが空になるまで続ける
    // スタックの一番上を処理の対象とする
    if (!A.empty()) last = A.back();
    // その数以上で3以下の数を数列に付け加えていく
    repi(i, last, 4){
        // 付け加えられた数列をvectorに追加する
        A.push_back(i);
        // dfsの再帰呼び出し
        dfs(A);
        // 一度対象とした要素は削除する
        A.pop_back();
    }
  // voidなので返り値はなし
  return;
}

int main() {
    vector<int> A;
    // 空のvectorを突っ込む
    dfs(A);
}