幅優先探索のアルゴリズムについて

Question

深さ優先探索は再帰関数を利用して行うことができます。
幅優先探索においては再帰関数を利用することはできるのでしょうか？？
（javaもしくはC、C++）

Answer 1

再帰関数で全く作れないというわけではないようです。

なぜ Haskell ではキューが軽んじられているか？ - あどけない話

上記記事では幅優先探索を再帰関数で実装しています(そもそもHaskellにはループ構文がないので再帰で書くしかないのですが)。キューの代わりに木を使ってそれを探索するようにしているようです。(細かい所は追ってないので私も詳しくは説明できないです)

ただ、この実装は余再帰というものを使っています。遅延評価であるHaskellでは問題ないようですが、正格評価であるC/C++ではスタックオーバーフローを起こす場合があるため、使えないと思われます(末尾再帰最適化すらできないJavaは論外)。

Answer 2

こんにちは。

幅優先探索はキューを使います。キューをスタックに変えると深さ優先探索になります。
そして、再帰処理はスタックを使って処理しますが、再帰処理をキューで実装するのは無理です。

Comments

[Gatmaster]

早い回答ありがとうございます。わかりやすかったのでベストアンサーにさせていただきます。
実はスタックとキューを理解しておらず、深さ優先探索を再帰関数を用いて行っていました。そのため、幅優先探索も再帰関数を用いてなんとかできないかという考えに至ったわけでして、、、。
とりあえずキューとスタックを勉強してみます。