问题标签 [breadth-first-search]

我记得并检查过，遍历树或首先爬取网络广度 (BFS) 的常用方法是使用队列。实际上有没有一种方法可以不使用队列来实现它？

我有一个二叉树，其中每个节点都可以有一个值。

我想在树中找到值为 null 并且最接近根的节点。如果有两个节点与根的距离相同，则任何一个都可以。我需要最小化对二叉树的读取访问次数。假设工作记忆仅限于 k 个节点。

DFS 到深度 k 是详尽的，但除非我先遍历整个树，否则不会找到最近的节点。BFS 会找到最接近的，但它可能会失败，因为 DFS 可以使用相同的内存找到更深的空值。

我希望对树的读取访问次数最少，并找到最近的空节点。

（我最终也需要在 n 路树中实现这一点，所以一个通用的解决方案会很好。没有对树的写访问权限，只是读取。）

这是一道面试题

我想一个解决办法。它使用队列。

有什么比这更好的解决方案，不使用队列吗？

我想使用 java 实现 DFS（深度优先搜索）和 BFS。

java是否有一个内置的树数据结构，我可以随时使用？或者我可以使用的其他任何东西？

假设我找到了符合我的条件的节点，我需要停止搜索。

我的书中有以下伪代码用于广度优先搜索：

我自己按照这些伪代码指令实现了一个类似的算法。我的问题是，修改它以保持解决方案路径的最简单方法是什么？

仅仅知道我可以找到解决方案并没有获得解决方案的转换列表那么有用。

我正在尝试构建一种方法，该方法在未加权图中返回从一个节点到另一个节点的最短路径。我考虑过使用 Dijkstra 的，但这似乎有点矫枉过正，因为我只想要一对。相反，我实现了广度优先搜索，但问题是我的返回列表包含一些我不想要的节点 - 我如何修改我的代码以实现我的目标？

我了解如何在树结构中使用广度优先搜索和 A*，但鉴于下图，它将如何实现？换句话说，搜索将如何遍历图形？S 是开始状态

图表在这里

我正在编写一个使用 inotify 来监视文件访问的守护程序，并且在递归搜索中不会遗漏任何内容至关重要。我发现了这个有趣的想法并开始实施它。

ftw() 和 ftw64() 不使用广度优先算法，它更多的是“预购”。nftw() 给了我深度优先的选项，但我担心上层叶子的比赛。

我希望我错过了一些东西，也许是 GNU 扩展？还是我只是想用类型安全的回调来实现我自己的（我真的不想这样做）？

或者，对于这种类型的应用程序，我对广度优先优于深度优先的优势的理解是否错误？

通常当我不得不走一个图时，我总是使用深度优先搜索，因为空间复杂度较低。老实说，我从未见过需要广度优先搜索的情况，尽管我的经验非常有限。

什么时候使用广度优先搜索有意义？

更新：我想我在这里的回答显示了我使用 BFS 的情况（因为我认为是 DFS）。不过，我仍然很想知道，为什么它在这种情况下很有用。