12月19日 作業日誌 DFSとBFS
こんばんは。
「チョットデキル」や「なんもわからん」は概ね「めちゃくちゃできる」「開発者本人です」と同義です。
本当になんもわからん時なんて言うかいつも困ります。
今日はアルゴリズムの勉強をしていました。
アルゴリズム頭の体操ですね。
頭の整理も兼ねてDFSとBFSについて書いておきます。
DFS
深さ優先探索です。
このような構造（グラフ）があった時に、1→2→4→5→3→6の順に見ていくアルゴリズムです。
すでに通った道を記録することで、すべての頂点を一回ずつ見ることができます。
迷路とかを解けます。
実装は再帰関数でするのが良いと思います。
void dfs(vvi &g, vi &seen, int now){
for(auto next : g.at(now - 1)){
if(seen.at(next - 1) != -1){
continue;
}
dfs(g,seen,next);
}
}int main() {
int n;
cin >> n;
vvi g(n);
rep(i,n){
int tmp;
cin >> tmp;
int m;
cin >> m;
rep(j,m){
int v;
cin >> v;
g.at(i).push_back(v);
}
}
vi seen(n,-1);rep(i,n){
if(seen.at(i) == -1){
dfs(g,seen,i + 1);
}
}rep(i,n){
cout << i + 1 << " " << seen.at(i) << endl;
}
}
こんな感じです。
gが全ての頂点のつながり、seenがすでに通った頂点の記録です。
頂点を通った時間を記録するにはもう一つ変数を渡してdfs内のforの前後で記録します。
main関数の中でdfsをforで囲んでいるのは頂点が全て連結していない可能性を考慮しています。
参考（すごくわかりやすい）：
再帰関数を使わないDFSもあるそうで、そっちの方が速いらしいのでいつかつよつよになったら見てみます。
BFS
幅優先探索です。
このグラフだと1→2→3→4→5→6の順に見ていきます。
1に近い方から見ていくことになるので、各頂点への最短経路がわかります。
実装はwhile文が良いのだと思います。
キューを使うことで、
1.①をキューに入れる（①からの距離を記録する）
2.①をキューから出す
3.②と③をキューに入れる（①からの距離を記録する）
4.②をキューから出す
5.④と⑤をキューに入れる（①からの距離を記録する）
6.③をキューから出す
・
・
・
というように1に近い順で処理できます。
int main() {
int n;
cin >> n;
vvi g(n);
rep(i,n){
int num;
cin >> num;
int m;
cin >> m;
rep(j,m){
int tmp;
cin >> tmp;
g.at(i).push_back(tmp);
}
}
vi dist(n,-1);
queue<int> q;
dist.at(0) = 0;
q.push(1);
while(!q.empty()){
int v = q.front();
q.pop();
for(auto next : g.at(v - 1)){
if(dist.at(next - 1) != -1){
continue;
}
dist.at(next - 1) = dist.at(v - 1) + 1;
q.push(next);
}
}
rep(i,n){
cout << i + 1 << " " << dist.at(i) << endl;
}
}
こんな感じです。
distが①からの距離の記録です。
qがキューです。
参考（すごくわかりやすい）：
けんちょんさんには大変お世話になっております。
競技プログラミングのCとDを安定して解けるよう、過去問を解いたり解説を見たりして頑張ります。
あと、解説記事を書いてる方々すごすぎますね……。
もっとわかりやすく解説できるようになったら、きっと心から理解できたと言えるのでしょう。
以上です。
