BFS（幅優先探索）とDFS（深さ優先探索）を実装する力を身につけるための記事です。
「概念は分かってんだよ」という人のためにそこの説明は軽くやっておしまいです。
枝切り（枝刈り）探索についてはここでは扱いません。
記事内のコードのバージョンはC#13.0、.NET 10.0。
概念を理解する
木構造の探索でよく使われるので二分木を使って解説します。
図の赤い丸の部分がノード（点）。このノード自体に対する処理、While文や再帰などのループに記述する部分です。例として、探索済みとしてマークする（visited[i][j] = true）など。
赤い線の部分がエッジ（線）。ここでやるのは次のノードに対する条件判定。未探索であるか、現在のノードは末端でないか、2次元のグリッドなどでは隣にノードが存在するか。それを判別して次のノード（オレンジの丸）をQueueに入れます。
最短経路探索の問題で使われる重み付きグラフなども、この時に考慮します。
やることは終わったのでループを抜けて、またQueueから要素を取り出すと、下図のようになります。
このように再帰的に処理が進んでいきます。
図の赤い部分で再帰的な構造になっているので、そこを処理するコードを書けばよいです。
実際には抽象的にグラフ構造っぽいものであれば木構造に限らず何にでも使えます。2次元配列などグリッドにおける連結成分の数え上げ、双方向グラフでの最短経路探索など競プロにおいて頻出する問題に対応できます。
使うもの
Queue、先入れ先出し法によるコレクションです。
Stack、後入れ先出し法によるコレクションです。
Queueは幅優先探索に、Stackは深さ優先探索に使います。
解く問題によってはどちらか一方の型が最適な選択になることもありますが、基本的にお好みで大丈夫です。解説はQueueを使います。
Queueにおける追加、取り出しはEnqueue()、Dequeue()。
Stackの追加、取り出しはそれぞれPush()、Pop()です。適宜読み換えてください。
解説
(更新:説明文を分かりやすく親切にしました)
先ほど解説した通り、While文や再帰などのループ部で主に処理する部分をDequeueとEnqueueで挟みます。下図とリストを参照。
- Dequeue()による取り出しおよび各ノードに対する処理。（問題によりけり）
- 次のノードを判別。（有効なノードである、現在のノードが末端でないなど）
- 次のノードをEnqueue()。
これが記述できれば、始点となるノードをEnqueue()してWhile文に入るだけです。
コードの全体をより単純化するとこうなります。
- データの前処理（あれば）
- 始点となるノードをQueueに入れる
- ループ部（BFS・DFSの核）
- Queueからノードを取り出す
- ノードに対する処理
- 次のノードを判別
- 次のノードをQueueに入れる
- ループを抜けたら集計して出力。あるいはループを抜けた時点で集計が終わっている状態にする。
以上の工程を経たのが大体下記の例になります。自分で書きたい人向けに畳んでます。
QueueをWhileでぶん回すBFSの例
var ans = new List<List<int>>(); // 複数解を格納する
var que = new Queue<List<int>>(); // 幅優先探索に使うキュー
que.Enqueue([0]); // 原点0より一番目の頂点
while (0 < que.Count)
{
var list = que.Dequeue();
if (/*もし探索すべき枝の末端なら*/)
{
if (/*答えとなるかを判別し*/) ans.Add(list); // 別で宣言したリストに追加。
}
else // もし探索中なら
{
for (int i = 0; i < n; i++)
{
que.Enqueue([.. list, i]); // その枝の先をEnqueue
//que.Enqueue(new List<int>(list){i}); とはほぼ同義
}
}
}ちなみに深さ優先探索をしたい場合は例に挙げたQueueをStackに置き換えます。
最低限QueueとWhileさえ覚えていればBFSは何とかなります。
余談
しかし初学者にとってみると「ノード（頂点）とはどんな変数型であるべきか」というのを決めることがなかなかに難しいところかもしれません。
大抵はintなどのプリミティブ型で考慮することはそう多くないのですが、ノードが配列・リスト型などの参照渡しの場合はコピーを作る必要があるなど注意点が増えます。List.Add()を使うとメソッドの引数に指定するとしても元の配列インスタンスに変更が反映されてバグの原因になるため、これを避けるためにインスタンスのコピーを作ります。
List.Add()の場合は代わりにnew List<T>(list){i}や[.. list, i]を使う、それ以外の変更はobject.Clone()やnew式を使う、など。この方法も制約上ノードとなりうる数に左右されますが、それはのちのち記事にできればと思います。
上記の通り、配列インスタンスへの変更を再帰的に行う場合には意図しない副作用を起こさないよう注意が必要です。
コメント