BFS（幅優先探索）とDFS（深さ優先探索）を実装する力を身につけるための記事です。
「概念は分かってんだよ」という人のためにそこの説明は軽くやっておしまいです。
枝切り（枝刈り）探索についてはここでは扱いません。
記事内のコードのバージョンはC#13.0、.NET 10.0。
使うもの
Queue、誤解を恐れずに言えば先入れ先出し法によるコレクションです。
Stack、こちらも同様に後入れ先出し法によるコレクションです。
Queueは幅優先探索に、Stackは深さ優先探索に使います。
だいたい木構造っぽい問題を解くために使います。
解く問題によってはどちらか一方の型が最適な選択になることもありますが、基本的にお好みで大丈夫です。解説はQueueを使います。
Queueにおける追加、取り出しはEnqueue()、Dequeue()。
Stackの追加、取り出しはそれぞれPush()、Pop()です。適宜読み換えてください。
解説
- Queueに最初の頂点となる要素をEnqueue()します。この要素の型は大抵、配列やListなどのコレクションになることが多いです。頂点となる要素が複数存在する場合もあります。
- While文を「Queueに要素がなくなるまで」の条件でぶん回します。
- While内でDequeue()した要素から伸びる頂点をEnqueue()します。
- for文でEnqueue()しまくることが多いです。
- 配列やListは参照型なので
new List<int>(list){hoge}したり[.. list, hoge]したりします。C++とは違って別のインスタンスを用意する必要があります。
- 末端となるケースを判別して答えを出力します。
以上の工程を経たのが大体下記の例になります。自分で書きたい人向けに畳んでます。
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でぶん回すもの。
StackもWhileでぶん回すもの。
命は投げ捨てるもの
最低限QueueとWhileさえ覚えていればBFSは何とかなります。枝木っぽい解き方かも＝じゃあQueueとWhileだな。
あとはQueueのCount部分以外の終了条件と、各頂点への探索を適切に追加すること。
しかし初学者にとってみると「頂点とはどんな変数型であるべきか」というのを決めることがなかなかに難しいところかもしれません。解く問題によってまあまあ異なるので「大体これです」とも言えない……。
まあどうにか慣れてください。（投げやり）
コメント