幅優先探索を実装してみた

幅優先探索の勉強メモです。アルゴリズムの解説と、問題を解くことまでをやっていきたいと思います。

幅優先探索

幅優先探索（Breadth First Search, BFS）はグラフを用いた基本的な探索アルゴリズム。近いものから順にアクセスしていく感じ。例えば次のような順番で各頂点を訪問します。

経路の探索によく用いられます。近い頂点から順に訪問していくので、最短距離も簡単に求めることができます。

アルゴリズム

深さ優先探索と同じノリで実装できます。違うのは、深さ優先探索がスタックを使うのに対し、幅優先探索はキューを用いること。

1. 始点となる頂点をキューに入れる。
2. キューが空になるまで以下を繰り返す：
   • キューから頂点を取り出し、処理する（訪問する）。
   • 訪問中のneighbors（隣接している頂点たち）のうち、未訪問のものをキューに入れる。

深さ優先探索： 深さ優先探索を実装してみた - プログラミング原人の進化論

実装

次の問題を解いてみます。

幅優先探索 | アルゴリズムとデータ構造 | Aizu Online Judge

各頂点を訪問したかどうか調べるために、状態を色で管理します。

• white：未訪問
• gray ：キューに入っている
• black：処理が終了

解答例：

#include<iostream>
#include<queue>
using namespace std;

#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int M[N+1][N+1];  // 隣接行列

void bfs(int n, int d[], int color[]) {
  int vertex;
  queue<int> Q;
  
  // 初期状態
  for (int i = 1; i <= n; i++) {
    d[i] = -1;
    color[i] = WHITE;
  }
  vertex = 1;  // 始点
  d[vertex] = 0;
  Q.push(vertex);
  //bfs
  while (!Q.empty()) {
    vertex = Q.front();
    Q.pop();
    color[vertex] = GRAY;
    // 見訪問の隣接する頂点を探してキューに入れる
    for (int i = 1; i <= n; i++) {
      if (M[vertex][i] && color[i] == WHITE) {
        color[i] = GRAY;
        Q.push(i);
        d[i] = d[vertex] + 1;  // 距離
      }
    }
    color[vertex] = BLACK;  // 処理終了
  }
}

int main() {
  int i, j, n, u, k, v, d[N+1], color[N+1];

  cin >> n;
  // 与えられた隣接リストを隣接行列表現に直す
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      M[i][j] = 0;
    }
  }
  for (i = 0; i < n; i++) {
    cin >> u >> k;
    for (j = 0; j < k; j++) {
      cin >> v;
      M[u][v] = 1;
    }
  }
      
  // bfs
  bfs(n, d, color);

  // 出力
  for (i = 1; i <= n; i++) cout << i << " " << d[i] << endl;

  return 0;
}

参考

渡部有隆. プログラミングコンテスト攻略のためのアルゴリズムとデータ構造. Ozy, 秋葉拓哉協力. 株式会社マイナビ. 2015.