具有恒定内存量的 BFS
是否可以仅使用（图的大小）+恒定量的内存来进行呼吸优先搜索——换句话说，不记录哪些节点已经被访问过？
Is it possible to do a breath first search using only (size of graph) + a constant amount of memory -- in other words, without recording which nodes have already been visited?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
不，您始终需要记住您去过的地方。因此，在最坏的情况下，您需要记录所有节点的访问状态。然而，图的分支因子和深度是主要因素。如果图表没有太多分支，则不需要类似的东西。如果它是高度分支的，你就会倾向于最坏的情况。
No. You always need to remember where you have visited. In the worst case, therefore, you need to record the visited state of all nodes. However, the branching factor and depth of the graph are the main factors. If the graph doesn't branch a lot, you won't need anything like that. If it is highly branching, you tend to the worst case.