algorithm - 具有恒定内存量的 BFS

Question

是否可以仅使用（图形大小）+ 恒定内存量进行呼吸优先搜索 - 换句话说，不记录已访问过哪些节点？

Answer 1

不，您始终需要记住您去过的地方。因此，在最坏的情况下，您需要记录所有节点的访问状态。但是，图的分支因子和深度是主要因素。如果图表的分支不多，则不需要这样的东西。如果它是高度分支的，你倾向于最坏的情况。