问题标签 [breadth-first-search]

我对图的基本广度优先搜索遍历的理解是：

但是，如果我们必须从给定节点遍历有向图，并且并非所有节点都可以从给定节点访问（直接或间接），那么我们如何使用 BFS 来遍历这种情况的图呢？

您能否在此图中也解释一下：

在这里，如果起始节点是b，我们从不打印aand c。

我在算法中遗漏了什么吗？

我曾经 HashMap<String, ArrayList> adj = new HashMap();创建邻接列表来存储图形。

我正在解决一个问题，我需要在给定的有向未加权图中找到两个节点之间的所有最短路径。我已经使用 BFS 算法来完成这项工作，但不幸的是我只能打印一条最短路径而不是全部，例如，如果它们是 4 条长度为 3 的路径，我的算法只打印第一个但我希望它打印所有四个最短路径。我想知道在下面的代码中，我应该如何更改它以便可以打印出两个节点之间的所有最短路径？

我非常感谢您的大力帮助谢谢，安德拉

关于深度优先搜索的维基百科：

深度优先搜索 (DFS) 是一种用于遍历或搜索树、树结构或图的算法。一个从根开始（在图中选择某个节点作为根），并在回溯之前沿着每个分支尽可能地探索 。

那么什么是广度优先搜索？

“一种算法，选择一个起始节点，检查所有节点回溯，选择最短路径，选择邻居节点回溯，选择最短路径，由于连续回溯遍历每条路径，最终找到最佳路径。

Regexfind的修剪——回溯？

回溯一词因其用途广泛而令人困惑。UNIXfind对 SO 用户的修剪通过回溯进行了解释。如果您不限制 Regex 的范围，Regex Buddy 使用术语“灾难性回溯”。这似乎是一个使用过于广泛的总称。所以：

1. 您如何专门为图论定义“回溯”？
2. 广度优先搜索和深度优先搜索中的“回溯”是什么？

[添加]

关于回溯和示例的良好定义

1. 蛮力法
2. Stallman（？）发明的术语“依赖导向回溯”
3. 回溯和正则表达式示例
4. 深度优先搜索定义。

我知道这个算法是如何工作的，但无法决定何时使用哪种算法？

是否有一些指导方针，其中一个比其他或任何考虑更好？

非常感谢。

假设我有以下 Haskell 树类型，其中“State”是一个简单的包装器：

我还有一个函数“expand :: Tree a -> Tree a”，它接受一个叶节点，并将其展开为一个分支，或者采用一个分支并原样返回。这种树类型表示 N 元搜索树。

搜索深度优先是一种浪费，因为搜索空间显然是无限的，因为我可以通过在所有树的叶节点上使用 expand 轻松地继续扩展搜索空间，并且有可能意外错过目标状态是巨大的......因此唯一的解决方案是广度优先搜索，在这里实现得相当不错，如果它在那里，它将找到解决方案。

不过，我想要生成的是遍历查找解决方案的树。这是一个问题，因为我只知道如何进行深度优先，这可以通过简单地在第一个子节点上一次又一次地调用“扩展”函数来完成......直到找到目标状态。（除了一个非常不舒服的列表之外，这真的不会产生任何东西。）

谁能给我任何关于如何做到这一点（或整个算法）的提示，或者判断它是否可能具有相当的复杂性？（或者这方面的任何资料，因为我发现很少。）

DFS 主要用于在图中找到循环，而不是 BFS。有什么理由吗？两者都可以在遍历树/图时查找节点是否已被访问。

这是广度优先旅行的Java代码：

是否可以编写一个递归函数来做同样的事情？

起初，我认为这很容易，所以我想出了这个：

然后我发现它不起作用。它实际上与此相同：

有没有人考虑过这个？

我一个人在这个项目上工作，可以用另一双眼睛来看看这个，看看我做错了什么。第一个循环无限运行。

我了解 BFS 和 DFS，但是对于我的生活来说，我无法弄清楚迭代深化和 BFS 之间的区别。显然，迭代深化与 DFS 具有相同的内存使用量，但我无法看到这是怎么可能的，因为它只是像 BFS 一样不断扩展。如果有人能澄清那将是很棒的。

如果需要，可以处理的树：

我正在寻找一种方法来实时找到巨大图中节点之间的最短路径。它有数十万个顶点和数百万条边。我知道以前有人问过这个问题，我想答案是使用广度优先搜索，但我更感兴趣的是知道你可以用什么软件来实现它。例如，如果它已经存在用于在无向图中执行 bfs 的库（带有 python 绑定！），那将是完全完美的。