问题标签 [breadth-first-search]

我总是混淆是否使用堆栈或队列进行 DFS 或 BFS。有人可以提供一些关于如何记住哪种算法使用哪种数据结构的直觉吗？

嘿，我参加了当地的编程比赛，他们问了我这个我做不到的问题，请帮助我解决这个问题。

编写一个程序，从一个迷宫大小的文件加载，然后是迷宫本身。为了模拟迷宫，我们使用字符“S”来指定起始单元格“.”。指定空闲单元格，“#”是墙，“F”是最后一个单元格。编写一个程序，找出从起始单元到最终单元的路径。你可以认为迷宫中有一个服从命令的机器人，那么对于下面的迷宫，机器人应该收到以下命令：上、上、右、右、下、下。

迷宫 1 文本文件

迷宫 2 文本文件

一般写你的程序（迷宫最大输入可以是200x200）。

帮助将不胜感激。我只是一个正在升起的大二学生，所以如果你能给我提供代码，那么我就能理解它，他们会自己再做一次。

我的问题并不是关于这两种搜索类型的机制。我觉得它比这更平凡 - 我不了解两者的输入和输出。更具体地说，在 CLRS 中，BFS 将图和源节点作为输入，而 DFS 仅将图作为输入。DFS 不关心你从哪里搜索吗？

这就是输入混乱。输出混乱是，在 DFS 中，当你完成后，你有一个类似表的结构记录每个节点的发现和完成时间，对吗？您如何从中提取解决方案，即从源节点到目标节点的路径？

我希望我说得通。谢谢！

编辑：这就是我所说的 DFS 不采用源节点的意思。这是来自 CLRS 的 DFS 伪代码。我看不到它在任何地方都有源节点。我看到它所做的只是遍历图中的所有节点。

问题如下：一个流浪者从网格坐标 (x,y) 开始，想要到达坐标 (0,0)。从每个网格点，流浪者可以向北走 8 步或向南走 3 步或向东走 5 步或向西走 6 步（8N/3S/5E/6W）。

如何使用广度优先搜索找到从 (X,Y) 到 (0,0) 的最短路径？

说明：

• 无限网格
• 允许负坐标
• 必须使用队列（链表或数组）
• 不存在障碍

根据我所做的大部分阅读，据说双向搜索算法在“前向”和“后向”边界首次相交时终止。然而，在《人工智能：现代方法》第 3.4.6 节中，Russel 和 Norvig 指出：

双向搜索是通过将目标测试替换为检查两个搜索的边界是否相交来实现的；如果他们这样做了，那么已经找到了解决方案。重要的是要认识到找到的第一个解决方案可能不是最优的，即使两个搜索都是广度优先的；需要进行一些额外的搜索，以确保没有捷径跨越间隙。

我已经考虑了这个声明很长一段时间，但我找不到这种行为的例子。谁能提供一个示例图，其中双向 BFS 或 A* 搜索的前向和后向边界之间的第一个交点不是最短路径？

编辑：显然 BFS 不会在加权图中找到最短路径。听起来这段摘录是指无向图上的双向 BFS。或者，我有兴趣在加权图上查看使用双向 A* 的反例。

问题：我们如何逐级显示树节点？你能给我时间和空间有效的解决方案吗？

例子 ：

输出： 您必须逐级打印树节点

所以，我可以遍历列表，但我不能打印出每个级别。不知道怎么做。

我有这样的事情：

而不是像这样打印

我喜欢这样打印

我尝试了一些不同的东西，但我似乎无法得到它。任何帮助将不胜感激。

在我的以下代码中，我通过breadth first search. 代码在遍历时构建图形。这是一个非常大的图，有 12 个扇形。因此，每当深度breadth first search增加时，我都想破坏它上面的层，以尽量减少内存使用。我怎么能设计一个算法来做到这一点？

我在某处读到 DFS 不适合找到解决方案，而 BFS 是..为什么？我真的不明白这是怎么回事..有人可以为我证明一个案例来证明这一点吗？

我一直在阅读很多关于如何使用广度优先搜索、dfs、A* 等的 stackoverflow 问题，问题是最佳用法是什么以及如何在现实中实现它与模拟图。例如

假设您有 Twitter/Facebook/某个社交网站的社交图，对我来说，搜索算法的工作原理如下：

如果用户 A 有 10 个朋友，那么其中一个有 2 个朋友，另一个有 3 个朋友。搜索首先会找出用户 A 的朋友是谁，然后必须向十个用户中的每一个查找谁的朋友在哪里。对我来说，这似乎是 bfs？

但是，我不确定这是否是实现算法的方法。

谢谢，