saibox

幅優先探索（BFS）

作成：更新：

イメージ

graph TD
  A((0)) --> B((1))
  A --> C((2))
  B --> D((3))
  B --> E((4))
  C --> F((5))
  C --> G((6))

実装

訪問すべきノードをキューで管理する

bfs.cpp
queue<int> q;
q.push(0);
 
while (not q.empty()) {
    int cv = q.front();
    q.pop();
    seen[cv] = true;
    
    each(nv, g[cv]) {
        if (seen[nv]) continue;
        q.push(nv);
    }
}

スタックで管理すればpushして直ちにpopするのでDFSになる

グリッド

迷路など、2次元のグリッドを探索するような場合

bfs.cpp
queue<pair<int, int>> q;
q.emplace(0, 0);
 
vector<int> dy = {0, 1, 0, -1};
vector<int> dx = {1, 0, -1, 0};
 
while (not q.empty()) {
    auto [y, x] = q.front();
    q.pop();
    seen[y][x] = true;
 
    rep(i, 4) {
        int ny = y + dy[i], nx = x + dx[i];
        if (ny < 0 or h <= ny or nx < 0 or w <= nx) continue;
        if (seen[ny][nx]) continue;
 
        q.emplace(ny, nx)
    }
}

参考

Graph