🐔
「DFSが苦手」がなくなる！BFSと合わせて体系的に再解釈する話

2025/05/15に公開
 はじめにこんにちは、とりからです。
今回はBFS(幅優先探索)とDFS(深さ優先探索)について、これらの類似点と相違点を明らかにしつつ、統合的なフレームワークのもとで再解釈することで、アルゴリズムの理解を深めて行きたいと考えています。
これらのアルゴリズムがわからない人はもちろん、「どちらを使うか迷う」「BFSは書けるけど DFSは苦手」「ダイクストラはすぐには書けない」といった人の理解の手助けにもなればと思います。

 BFSと DFSの考え方BFSとDFSはいずれも基本的に全探索を行うアルゴリズムです。全探索では、漏れなく、ダブりなく(MECEって言うんでしたっけ？)行うことが重要で、そのための探索順序の工夫がBFSとDFSです。
BFSは始点から同心円状に探索領域を広げていき、DFSは始点から放射状に探索領域を広げていくイメージで、私は部屋の床を雑巾掛けするときのやりかたの違いといった形で視覚的に捉えています。BFSは真ん中から段々広がるように拭き進めていく、DFSは真ん中から一直線に端まで拭いて、元の位置に戻ってきて違う方向を拭くといった様子です(絵心がないのでAIに作ってもらいました)。


 BFSと DFSの実装はほぼ同じさて、イメージとして上記のような違いをもつBFSとDFSですが、実装はどう違うのでしょうか。結論から言うと、queueを使うかstackを使うかの違いだけで、ほとんど一緒のコードで書き分けることができます(コード例はC++です)。

 BFSの基本形bfs.cpp
int N; //探索するグラフのノード数
vector<vector<int>> G; //探索するグラフ
int start; //探索の始点
vector<bool> visited(N,false); 
queue<int> q; //queueを使用！！
visited[stert]=true;
q.push(start);
while(!q.empty()){
  int cur=q.front(); //現在の探索ノード
  q.pop();
  //何かの処理をする
  for(int nxt:G[cur]){
    if(visited[nxt])continue;
    visited[nxt]=true;
    q.push(nxt); //次の探索ノードの挿入
  }
}

 DFSの基本形さきほどのBFSの基本形においてqueueであった部分をstackに置き換えるだけです。
dfs.cpp
int N; //探索するグラフのノード数
vector<vector<int>> G; //探索するグラフ
int start; //探索の始点
vector<bool> visited(N,false); 
stack<int> st; //stackを使用！！
visited[stert]=true;
st.push(start);
while(!st.empty()){
  int cur=st.top(); //現在の探索ノード
  st.pop();
  //何かの処理をする
  for(int nxt:G[cur]){
    if(visited[nxt])continue;
    visited[nxt]=true;
    st.push(nxt); //次の探索ノードの挿入
  }
}
これは、ざっくりと言えば、queueがFIFOであり、ある探索ノードの隣接点を全て確認してから次に進んでいくのに対し、stackは LIFOであり、ある探索ノードの隣接点を後回しにして、新しくいれたノードから見ていくため、前者はBFS順に、後者はDFS順に探索が進むことになります

 DFSを再帰で書く関数の呼び出しはスタック的に行われるので、DFSの基本形で用いたスタックを関数に置き換えることができます。これがDFSを再帰で書くと言うことで、やっていることは同じです。コード例で確認します。

再帰で書くと何が嬉しいのかについては後述します。
関数呼び出しがスタック的とはf(x)=g(x)+2,g(x)=h(x)+1,h(x)=xという関数を考えて、x=2のときのf(x)の値を求めようとすると、まずg(x)が呼ばれて、その後にh(x)が呼ばれることになります。
このときに、g(x)が解決しない限り、h(x)を参照できないというのでは困ります。なので、後に入れたh(x)=2が先に決まり、先に入れたg(x)はその後にg(x)=h(x)+1=3と決まり、最後にf(x)=g(x)+2=5とわかるという、LIFOの順で解決することになるということです
dfs_recur.cpp
int N; //探索するグラフのノード数
vector<vector<int>> G; //探索するグラフ
int start; //探索の始点
vector<bool> visited(N,false); 
auto dfs=[&](auto dfs,int cur){
  visited[cur]=true; //現在の探索ノード
  //何か処理をする
  for(int nxt:G[cur]){
    if(visited[nxt])continue;
    dfs(dfs,nxt); //次の探索ノードの挿入
  }
  return;
};
dfs(dfs,start); //始点からDFSを開始
こう見ると、再帰のDFSもスタックのDFSと似た形をしているのがわかります。

 BFSと DFSの使い分けここまでBFSとDFSは似たような実装で書けるという話をしてきましたし、全探索の探索順の違いでしかないという話をしてきました。
とすると、BFSとDFSはどっちかだけでよくないか？好きな方だけ書こうと思うかもしれません。
全探索が回るような計算量であればどちらでもよいケースも多いですが、探索順の違いから来る特性によって、剪定(不要な探索を途中で打ち切ること)できる枝の性質が異なっていたり、保持しやすい情報が異なっていたりするので、以降でそれぞれの特徴を見ていきたいと思います。
イメージ例のために、先ほどの例で言う、床の雑巾掛けの最中に複数の落ちてる画鋲を拾うという操作を追加して考えていきます。

 BFSって何が嬉しいの？BFSは先にも述べた通り、始点を中心とした同心円で層状に探索を進めることから、始点との関係性を軸にした探索に強みがあります。
掃除の例で言えば、始点からの距離が近い順に掃除を進めていきます。なので、最も近い画鋲はどこでしたか？という問いに対して、初めて拾ったときのやつか！とすぐにわかるというのがメリットです(最短距離問題)。
始点との関係性というところが肝で、それを念頭におくと、以下のようなアルゴリズムは自然と受け入れられるのではないでしょうか
多始点BFS

複数の始点を同一の層にあると見立てたもの。イメージとしては複数の山からなる地形の各山頂から等高線の順に探索するようなもの

あるいは始点の一つ手前に超頂点があると考えて、その一つ先の層が各始点であると考えることもできる
0,1-BFS

コスト0の辺の先のノードは、今探索しているノードと同じ層であるとみなせるため、先頭にいれることで、同じ層を網羅的に見てから次の層にいける
ダイクストラ法

BFSは各点への移動コストが一様(例えば全部1)な遷移であると考えると、ダイクストラはBFSにおける移動コストをバラバラに拡張したものと思える。始点から近い順に遷移していくように優先度付queueで次の探索先を管理する
プリム法

コストの低い順に、始点との連結成分が大きくなるように遷移していく
剪定についてもここまでと同じことが言えて、探索の限界を、始点との関係性によって全体的に、すなわちこの層より先はいかないといった形で決めるようなものが向いています。

 DFSって何が嬉しいの？DFSの剪定は先のBFSとは異なり局所的に決めるものが向いています。すなわち他との関係ではなく、今自分がいる点より先に行く意味があるかどうかという形で探索の限界を決めるということになります。
またBFSが始点との関係性を軸に探索していたのに対し、DFSは直接の親との関係性を軸に探索するという特徴があります。
この特徴は再帰と相性がよく、いわゆる行きがけ、戻りがけといった順(合わせて考えるとDFSは一筆がきのような形で探索していく)での遷移を考えるのに向いています。コード例で行きがけと戻りがけを示すと以下のようになります。
int N; //探索するグラフのノード数
vector<vector<int>> G; //探索するグラフ
int start; //探索の始点
vector<bool> visited(N,false); 
auto dfs=[&](auto dfs,int cur){
  visited[cur]=true; //現在の探索ノード
  //何か処理をする(行きがけ順)
  for(int nxt:G[cur]){
    if(visited[nxt])continue;
    dfs(dfs,nxt); //次の探索ノードの挿入
  }
  //ここが帰りがけ順での処理
  return;
};
dfs(dfs,start); //始点からDFSを開始
先ほどの掃除の例で言うと、BFSでは雑巾をかけながら画鋲を拾って、最後まで持ちっぱなしにするしかありませんが、DFSであれば端っこまで雑巾掛けをした後に、「元の位置まで戻ってきて」また違う方に行くというフェーズがあるので、①戻ってくるという暇なタイミングで画鋲を拾わせることができる、②画鋲を探索の途中で始点に集めておくことができるという2つの旨みがあるということになります。
このように親子間の関係を軸に遷移していくため、親から子だけではなく、子から親へと情報を伝播させる用途にも向いています。これを活用してトポロジカルソートや部分木サイズを求めたりすることができます。

 BFSもDFSもDPの一種ということここまで読んでいただいた方は既にお察しかもしれませんが、BFSでもDFSでも「ある点から次の点に遷移し、情報を伝播していく」ということは、すなわちDPをやっているということになるわけです。
逆に言えば、BFSやDFSはDPにおける遷移をどう設計するのかという一つの選択肢であるということです。
こう捉えることで、木DPも迷路探索も最短経路問題も、遷移を考えて情報を伝播するというDPの文脈で考えることができますし、DP自体の遷移の構造に関する理解も深まるのではないかと思います。

 まとめBFSとDFSは全く別のことを考えているわけではない
全探索が可能な状態数の下では、単なる探索順の違いにすぎず、基本的に好きな方を使えばいい
ただ、状態数が膨大になり枝刈りやメモ化が必要になったとき、遷移をどう設計するのかというDPの顔を見せることになる
BFSは始点との関係性に着目した遷移であり、伝播する情報も始点との関係性といったものになる。そのため、始点からの最短距離を求める場合等にはこの遷移が強い
DFSは親子間の関係性に着目した遷移であり、伝播する情報は親から子に連鎖的に伝えたり、子から親に集約的に伝えていくことになる。そのため最終状態を葉として持ち、開始状態を根として情報集約するような場合(後ろから考えるDPみたいな場合)にはこの遷移が強い

 おわりに今回はBFSとDFSについて、その性質を整理してきました。ここまで読んでくださった方に何か得るものがあれば幸いです。今後もまたアルゴリズムか何かの記事を投稿しますので、その際も読んでいただけるとありがたいです。みなさまが良きDFSライフを送れますように
はじめに

BFSと DFSの考え方

BFSと DFSの実装はほぼ同じ

BFSの基本形

DFSの基本形

DFSを再帰で書く

BFSと DFSの使い分け

BFSって何が嬉しいの？

DFSって何が嬉しいの？

BFSもDFSもDPの一種ということ

まとめ

おわりに

Discussion
