幅優先探索を使用する問題向けのライブラリです。例えば以下のような問題に対して使用すると有用です。
AtCoder Beginner Contest 007 C - 幅優先探索
AtCoder Beginner Contest 204 C - Tour
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
final class BfsExecutor {
private static final char UNREACHABLE_GRID = '#';
private static final int INF = 1 << 30;
/**
* 幅優先探索により、スタート位置からの最短距離を記録した二次元配列を取得する
* @param grid 横幅と高さが定まった二次元グリッド
* @param sx スタート位置のx座標
* @param sy スタート位置のy座標
* @return スタート位置からの最短距離を記録した二次元配列
*/
public static int[][] getGridDistanceMemory(char[][] grid, int sx, int sy) {
int h = grid.length;
int w = grid[0].length;
int[][] distances = new int[h][w];
for (int[] row : distances) {
Arrays.fill(row, INF);
}
Deque<Integer> qx = new ArrayDeque<Integer>();
Deque<Integer> qy = new ArrayDeque<Integer>();
int[] dx = { 1, 0, -1, 0 };
int[] dy = { 0, 1, 0, -1 };
distances[sy][sx] = 0;
qx.addLast(sx);
qy.addLast(sy);
while (!qx.isEmpty()) {
int px = qx.pollFirst();
int py = qy.pollFirst();
for (int i = 0; i < 4; ++i) {
int nx = px + dx[i];
int ny = py + dy[i];
// 範囲外ならば無視
if (!(0 <= nx && nx <= w - 1) || !(0 <= ny && ny <= h - 1)) {
continue;
}
// 行けないマスならば無視
if (grid[ny][nx] == UNREACHABLE_GRID) {
continue;
}
// 訪問済みのマスならば無視
if (distances[ny][nx] < INF) {
continue;
}
distances[ny][nx] = distances[py][px] + 1;
qx.addLast(nx);
qy.addLast(ny);
}
}
return distances;
}
/**
* 幅優先探索を行い、頂点に隣接するノードを記録したリストを返す
* @param adjNodesToEach 各ノードに隣接しているノードを記録した2次元リスト
* @param top 頂点
* @param visited 訪問済みの頂点か否か判定用配列(要素数はノードの数に等しい)
* @return 頂点に隣接しているノード番号のリスト
*/
public static List<Integer> getAdjacentNodesToTop(ArrayList<Integer>[] adjNodesToEach, int top, boolean[] visited) {
List<Integer> res = new ArrayList<Integer>();
Deque<Integer> q = new ArrayDeque<Integer>();
res.add(top);
visited[top] = true;
q.addLast(top);
while (!q.isEmpty()) {
int prevNode = q.pollFirst();
for (int i = 0, f = adjNodesToEach[prevNode].size(); i < f; ++i) {
int adjNode = adjNodesToEach[prevNode].get(i);
if (visited[adjNode]) {
continue;
}
res.add(adjNode);
visited[adjNode] = true;
q.addLast(adjNode);
}
}
return res;
}
}
※幅優先探索は以下のような疑似コードで一般的に表現できます
function bfs(top) {
// 空のキューQを定義
// topに訪問済みの印をつける
// topをQに追加
while (Qが空でない) {
// prevNode ← Qの先頭から取り出す
for each (prevNodeに接続しているノードadj) {
if (adjが訪問済み) {
continue;
}
// adjに訪問済みの印をつける
// adjをQに追加
// adjに所望の処理を行う
}
}
}