背景

ABC270でDFS・BFS（じゃなくても解けますが）の問題が出ました。 atcoder.jp

他の人のコードとか見ながら、結構みんな書き方まちまちなんだなーと思いつつ、個人的にバグらせないように気にしていることをまとめておこうと思い記事にしました。

この記事で触れないこと

DFS・BFS自体にはこの記事では触れません。これら自体については以下の記事などが良いと思います。

qiita.com

BFS (幅優先探索) 超入門！〜キューを鮮やかに使いこなす〜 - Qiita

TL;DR

共通

書き方をテンプレート化しておいて、考えることを減らす

DFS

コード書く量が減る（はず）なので、再帰で実装
再帰関数はほとんどの場合でローカル変数を参照したいので、lambda式で書く
行きがけ順の処理と帰りがけ順の処理を書く場所を決めておいて、やりたい処理をそこに書く

BFS

そもそもあんまり書かない（再帰のほうが楽）
訪問済みのマーク・判定はループの最初に入れる（これは諸説あり）

定義済みマクロとか

#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repe(a, v) for(auto& a : (v)) // v の全要素（変更可能）
template <class T> inline ostream& operator<<(ostream& os, vector<T>& v) {
    rep(i, sz(v)) {
        os << v.at(i);
        if (i != sz(v) - 1) os << " ";
    }
    return os;
}

その他、Graph型を定義しています。ライブラリ自体は以下に置いてますが、とりあえず隣接リストっぽくg[i]で隣接するノードを繰り返せると思っておけばよいです。

github.com

DFS

DFSを書くと決めた時点で、とりあえず脳死で以下まで書いてしまいます。（変数名とかは適宜変えます）

DFS（テンプレート）

Graph g;  // 適当に初期化
int s = 0;  // 最初の点
vb seen(n, false);
auto dfs = [&] (auto self, int x) {
    if (seen[x]) return;
    seen[x] = true;
    /* 行きがけ順にしたい処理を書く */
    repe(e, g[x]) {
        self(self, e.to);
    }
    /* 帰りがけ順にしたい処理を書く */
};
dfs(dfs, s);

lambda式にするのは、Global領域に変数をセットしに行くのがめんどくさいからです。

あとは、行きがけ順に処理したい内容と帰りがけ順に処理したい内容を考えて、それぞれコメントした箇所に書きます。逆にここ以外をいじることはほとんどしないです。（ついでにここ以外をいじる場合は、大抵自分はどこかをバグらせます）

書き方がかなりテンプレート化されているのでマクロや関数テンプレートで書けるかなーと思いつつ、地味にやりたいことが多岐にわたることと、上くらいであれば毎回書いてもそこまで時間かからないので、自分はテンプレートにはしていないです。エディタのスニペットとかには入れてもいいかなーとは思っています。

この書き方で、ABC270-Cを解くと以下のような感じです。

DFS（ABC270-C）

vi ans;
vb seen(n, false);
auto dfs = [&] (auto self, int xi) {
    if (seen[xi]) return;
    seen[xi] = true;
    /* 行きがけ順処理ここから */
    ans.push_back(xi + 1);
    if (xi == y) {
        cout << ans << endl;
        return;
    }
    /* 行きがけ順処理ここまで */
    repe(e, g[xi]) {
        self(self, e.to);
    }
    /* 帰りがけ順処理ここから */
    ans.pop_back();
    /* 帰りがけ順処理ここまで */
};
dfs(dfs, x);

atcoder.jp

ちなみに自分のDFSの書き方は以下の記事に多分に影響を受けています。 blog.knshnb.com

BFS

これもDFSと同じ感じで、とりあえずBFSと決めたら以下まで書いてしまいます。

BFS（テンプレート）

Graph g;  // 適当に初期化
int s = 0;  // 最初の点
deque<int> q;
q.push_back(x);
vb seen(n, false);
while(!q.empty()) {
    int x = q.front();
    q.pop_front();
    if (seen[x]) continue;
    seen[x] = true;
    /* やりたい処理 */
    repe(e, g[x]) {
        q.push_back(e.to);
    }
}

あとはやりたい処理を考えて埋めるだけです。

なお、自分は訪問済みの判定は、Queueの追加のタイミングではなく、必ず繰り返しの最初に置くことにしています。これは、昔以下のように書いてよくバグらせていたからです。

BFS（バグ例）

while(!q.empty()) {
    int x = q.front();
    q.pop_front();
    seen[x] = true;
    /* やりたい処理① */
    repe(e, g[x]) {
        if (!seen[e.to]) q.push_back(e.to);  // Queueの追加時に判定し、訪問済みのマークは処理時にすると、無駄な遷移が増えTLEする
    }
}

訪問済みチェックのタイミングとマークのタイミングが同じであればいいので、Queueの追加のときにマークする、でもいいのですが、とりあえず考えることを減らすために、自分は「ループの最初で訪問済みチェックとマークを両方する」をルール化しています。

これをベースにBFSでABC270-Cを解くと以下のような感じです。直前のノードを残しておくために、Queueの中身をpair<int, int>に改造しています。

BFS（ABC270-C）

vi prev(n, -1);
deque<pair<int, int>> q;
q.emplace_back(x, -1);
vb seen(n, false);
while(!q.empty()) {
    auto [x, par] = q.front();
    q.pop_front();
    if (seen[x]) continue;
    seen[x] = true;
    prev[x] = par;
    repe(e, g[x]) {
        q.emplace_back(e.to, x);
    }
}

vi ans; int current = y;
while (current != x) {
    ans.push_back(current + 1);
    current = prev[current];
}
ans.push_back(x + 1);
reverse(all(ans));
cout << ans << endl;

atcoder.jp

BFSはなんやかんやで、書いているとコードが長くなってくることが多い印象なので、どっちでもいいならDFSの方をよく書きます。

まとめ

書き方は人によりけりだとは思いますが、自分なりに「こう書けばバグらせない」みたいなテンプレートを持っておくことで、変なバグに悩まされることはなくなると思います。コンテスト中にえぐえぐ泣きながらデバッグして時間を溶かすのはしんどいので、バグらせないように書きましょう。。。

seekworserの日記

個人的DFS、BFS書くときにに気をつけてることまとめ

背景