幅優先検索を実行するときにキューの代わりにスタックを使用するとします。それはまだ最短経路を計算していますか？

Question

は、幅優先検索を実行しているときに、キューの代わりにスタックを使用できますか。それはまだ最短経路を計算していますか？

Answer 1

何でもできます。

はい、幅優先検索の補助データ構造としてキューの代わりにスタックを必ず使用することができます。

つまり、は、2つのスタックを使用してキューを実装しています。。短い説明はthis答えを参照してください。

すべてのエンキューおよびデキュー操作では、単純なBFSの複雑なコードにつながる可能性のある余分なプッシュとポップを実行する必要があります。

を1つのスタックに制限している場合は、深さ優先検索を試みることもできます。