幅優先探索(Breadth First Search)

探索幅優先探索, グラフ, キュー

幅優先探索とは、全探索アルゴリズムの一種です。最短経路を求める際に使用される基本的なアルゴリズムです。

木などのグラフやグラフと同一視できるものを探索する際に良く使われます。深さ優先探索と似ていますが、幅優先探索は始めの状態に近いものから順番に探索していきます。

英語では Breadth First Search なので、BFSと略されることも多いです。

以下のような順番で探索していきます。

状態遷移の順番
BFSの状態遷移の順番

アルゴリズム

幅優先探索ではキューを用いることで以下のように探索することができます。

  1. 始めの状態から遷移可能な状態を、全てキューに入れる
  2. キューに要素がなければ終了する
  3. 現在の状態から遷移可能な状態を、全てキューに入れる
  4. キューから1つ要素を取り出し、そこに状態を遷移させる
  5. 2.に戻る

(キューではなくスタックで実装すると、深さ優先探索になります。)

途中まで探索した時は以下のような状態になります。

2にいる時の状態
2にいる時の状態

状態を変更するたびに、キューに遷移可能な場所の情報を入れておきます。

※既に行ったことのある場所(上の図では0など)をキューに入れるようにすると無限ループになってしまうので気をつけましょう。

具体例で試してみる

例えば、以下のようなグラフについて考えます。

有向グラフ
有向グラフ

0からスタートして、3にたどり着ければ 「OK」、たどり着けなければ「NO」を返すプログラムを幅優先探索で実装します。

Pythonの例

隣接行列(グラフを参照のこと)を用いると以下のようになります。

from collections import deque 
n = 4 # グラフの頂点数
# グラフの隣接行列
G = [[0,1,1,0],
     [0,0,0,1],
     [0,1,0,1],
     [0,0,0,0]]
destination = 3; # 3にたどり着くかを探索
queue = deque() 
used = [0]*n    # 探索済みかどうかを記録
queue.append(0) # 0からスタート
used[0] = 1
while len(used) > 0:
  state = queue.popleft()
  print("now state:",state) # 現在の状態を表示
  for next in range(n):
    if G[state][next] == 1 and used[next]!= 1: # next が移動可能な状態ならstackに加える
      used[next] = 1
      queue.append(next)
  if state==destination: # 最終状態にたどり着いたら終了
    break;
if used[destination]==1:
  print("OK")
else:
  print("NO")

出力は以下のようになります。

now state: 0
now state: 1
now state: 2
now state: 3
OK

C++の例

隣接リスト表現(グラフを参照のこと)を用いると以下のようになります。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N = 4;                // グラフの頂点数
    vector<vector<int>> G(N); // 隣接リスト表現によるグラフ
    G[0].emplace_back(1);
    G[0].emplace_back(2);
    G[1].emplace_back(3);
    G[2].emplace_back(1);
    G[2].emplace_back(3);
    int destination = 3; // 3にたどり着くかを探す
    queue<int> que;
    vector<int> used(N, 0); // 探索済みかどうかを記録
    que.emplace(0);         // 0から探索する
    used[0] = 1;
    while (que.size() != 0) { // キューの要素がなくなったら終了
        int state = que.front();                // 現在の状態
        cout << "now state: " << state << endl; // 現在の状態を表示
        if (state == destination) { // 目的地にたどり着いたので終了
            cout << "OK\n";
            return 0;
        }
        que.pop();
        for (auto next : G[state]) {
            if (used[next] != 1) { // 未探索の時のみ行う
                used[next] = 1;
                que.push(next); //次の状態をqueueへ格納
            }
        }
    }
    cout << "NO\n";
    return 0;
}

出力はPythonの例と同じです。

実際に問題を解いてみる

AtCoder ABC007 C – 幅優先探索 を解いてみましょう。

問題概要

R行C列の迷路が与えられる。スタートの ( sy, sx ) からゴールの ( gy, gx ) までの最短距離を求めよ。

考え方

スタート地点から、幅優先探索によりゴールまでの最短距離を求めれば完了です。通った点について、スタート地点からの最短距離を記録していきましょう。

迷路上での探索なので、先程のグラフの例と少し実装が異なりますが、基本となるアルゴリズムは変わりません。

プログラム例

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n); i >= 0; i--)
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
const int INF = 2100100100;
int R, C;
char maze[55][55]; // 迷路の内容を保存する配列
int dist[55][55];  // スタート位置からの距離を記録
int s_x, s_y, g_x, g_y;
int main() {
    cin >> R >> C;
    cin >> s_y >> s_x;
    cin >> g_y >> g_x;
    // 0始まりに直す
    s_y--;
    s_x--;
    g_y--;
    g_x--;
    REP(i, R) {
        REP(j, C) { cin >> maze[i][j]; }
    }
    // 距離の初期化
    REP(i, R) {
        REP(j, C) { dist[i][j] = INF; }
    }
    int ans = 0;
    queue<pair<int, int>> que;
    que.emplace(make_pair(s_y, s_x)); // sから探索する
    dist[s_y][s_x] = 0;
    while (que.size() != 0) {               // キューの要素がなくなったら終了
        pair<int, int> state = que.front(); // 現在の状態
        que.pop();
        if (state.first == g_y && state.second == g_x) { // 目的地にたどり着いたので終了
            break;
        }
        int dy[4] = {0, 0, 1, -1};
        int dx[4] = {1, -1, 0, 0};
        REP(i, 4) {
            int ny = state.first + dy[i];  // 次の探索場所の行番号
            int nx = state.second + dx[i]; // 次の探索場所の列番号
            if (0 <= ny && ny < R && 0 <= nx && nx < C && maze[ny][nx] != '#' && dist[ny][nx] == INF) {
                que.push(make_pair(ny, nx));
                dist[ny][nx] = dist[state.first][state.second] + 1;
            }
        }
    }
    cout << dist[g_y][g_x] << endl;
    return 0;
}

関連問題