假設您在運行廣度優先搜索時使用堆棧而不是隊列。它是否仍然計算最短路徑？

Question

我可以使用堆疊而不是運行廣度優先搜索隊列時 。它是否仍然計算最短路徑？

Answer 1

一切皆有可能。

是的，您肯定可以使用堆棧而不是隊列作爲廣度優先搜索的輔助數據結構。

這就是說，我說的是實現一個隊列使用2堆棧。請參閱this答案以獲得簡要說明。

對於每一個入隊和出隊操作，則可能需要進行一些額外的推動和彈出這可能會導致一個簡單的BFS一個複雜的代碼。

如果您僅限於使用只有1堆棧，那麼您也可以嘗試進行深度優先搜索。