问题标签 [breadth-first-search]

我需要计算其值由以下无效的伪 python 代码给出的东西：

换句话说，给定所有节点对，foo = a * (E = 边数) + b * (EE = 不是邻居但有共同邻居的对的数量) + c * ( N(N-1 )/2 - EE - E)。

我试图考虑某种广度优先搜索，但我做不到。

编辑：更多信息

• 该图不是静态的。我不断添加和删除边缘，所以我不能只计算一次。我必须不断更新“下一个邻居列表”。
• 我将图形存储为邻接矩阵。

为什么 BFS 和 DFS 的运行时间是 O(V+E)，尤其是当有一个节点有一个有向边到一个可以从顶点到达的节点时，就像下面这个网站的例子一样

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

这是我第一次编程 C++，我被要求在给定这个类的地方编写广度优先搜索

sport是由string name和组成的结构int players。有人可以向我解释我将如何制作 BFS 吗？

提前致谢！

编辑：

我了解 BFS 的算法，但是由于我只编写过 C 语言，因此了解 OO 编程对我来说很困惑，鉴于该接口，我从哪里开始使用此 BFS，我是否创建了一个新函数来使 BFS 进行比较，start string与_target string

我已经从 wordnet 中检索同义词集并将其作为数组返回。这是我的代码的一部分

直到这一行，我已经成功检索了同义词集。我要做的是在搜索 WordNet 同义词集时实现广度优先搜索。我正在调用 RiWordnet 库中的 getAllSynsets 方法，该库将所有同义词存储在 wordnet 中。我尝试使用循环（if..else），但我不确定在哪里停止搜索。使用 BFS 应该知道搜索的范围，其中搜索同义词被标记为被访问的节点。这是我想在搜索同义词时使用 BFS 实现的概念。

例如：

有些人还建议我应用 HashSet 而不是 BFS。谁能帮我？先感谢您..

我目前正在阅读这篇论文，在第五页，它讨论了它认为是常识的二进制堆的属性。然而，他们提出的观点之一是我以前从未见过并且无法理解的东西。作者声称，如果给定一个平衡的二叉堆，则可以使用标准的广度优先搜索在每个元素 O(log n) 时间内按排序顺序列出该堆的元素。这是他们的原话：

在平衡堆中，任何新元素都可以在对数时间内插入。我们可以按权重顺序列出堆中的元素，只需使用广度优先搜索，就可以用对数时间来生成每个元素。

我不确定作者的意思是什么。当他们说“广度优先搜索”时，首先想到的是从根开始对树元素进行广度优先搜索，但这不能保证按排序顺序列出元素，也不需要对数时间每个元素。例如，在这个最小堆上运行 BFS 会产生乱序的元素，无论你如何打破关系：

这总是在 11 或 12 之前列出 100，这显然是错误的。

我错过了什么吗？是否有一个简单的广度优先搜索，您可以在堆上执行以使用对数时间按排序顺序取出元素？显然，您可以通过每次删除最小元素来破坏性地修改堆来做到这一点，但作者的意图似乎是这可以非破坏性地完成。

我正在尝试实现 CLRS 中描述的 BFS 算法。并具有以下内容：

但是，当我运行它时，我只会得到以下输出，然后是segfault队列初始化时的 a：

我正在使用以下命令进行编译：

我读过很多次关于DFS和BFS的文章，但我一直有这个疑问在我脑海中挥之不去。在很多文章中都提到 DFS 可能会陷入无限循环。

据我所知，通过跟踪访问的节点可以轻松消除此限制。事实上，在我读过的所有书籍中，这个小检查都是 DFS 的一部分。

那么为什么提到“无限循环”是 DFS 的一个缺点呢？是不是因为原来的 DFS 算法没有对访问节点进行这个检查？请解释。

我正在构建一个程序来搜索、识别和标记简单二维数组中整数值图的位置。

我手动追踪了第一个示例，它似乎运行准确。话虽如此，我要么编写了没有按照我认为的那样做的代码，要么我的手部追踪不准确。

我认为我的代码很接近，我正在寻找一些调试帮助以及对一般风格等的任何想法。

最终，该算法将被修改以找到用于 OCR 的字符像素图。我只是想在使用处理图像的代码使事情复杂化之前证明我的算法实现是准确的。

输入数组可能如下所示：

预期的结果是：

另一种类似的可能性是：在：

出去：

基本规则：

1. 输入文件的数组大小必须与 .cpp 文件中定义的 GS 匹配（H 等于 W 等于 GS）。
2. 图形定义为一个或多个彼此相邻的“1”值。
3. 使用简单队列的基本 BFS 技术执行搜索。
4. 当一个图表被定位时，它的值将从“1”更新为“2”。
5. 当确定图表中的最终值时，将在图表周围绘制一个由“3”个值组成的边界框。盒子的最小 X 等于图形的最小 X 减 2，盒子的最小 Y 等于图形的最小 Y 减 2。框的最大 X 等于图的最大 X 加二，框的最大 Y 等于图的最大 Y 加二。假设所有图表都有一个至少有两行/列的缓冲区，以允许绘制一个框。

处理这个数组的最新尝试：

产生这个输出：

而单个数字图效果很好：

产生输出：

这是我的代码：

我无法打印出所有可能的路径。目前我只能打印出一个路径，如果 (path-demo "J" "I")，程序会显示这个错误 mcdr: expects argument of type <mutable-pair>; 给定#f

我有来自 Cormen 的以下 BFS 功能。

从 s 到 v 的最短路径距离 path(s,v) 定义为从顶点 s 到顶点 v 的任何路径中的最小边数，或者如果没有从 s 到 v 的路径。 (s,v) 从 s 到 v 被称为从 s 到 v 的最短路径。

以下是给定的引理

令 G = (V,E) 为有向或无向图，令 s 属于 V 为任意顶点。然后，对于任何边 (u, v) E，

路径(s,v) <= 路径(s,u) + 1 。

我的问题是为什么我们必须在上面的公式中有 <= ，我教过 "=" 是可以的，谁能告诉我一个场景为什么我们需要 <= ？

下面是BFS算法

利马 2：

令 G = (V,E) 是有向或无向图，并假设 BFS 从给定源顶点 s 属于 V 的 G 上运行。然后在终止时，对于每个顶点 v 属于 V，值 d[v ] 由 BFS 计算满足 d[v] >= path (s, v)。

证明：

我们对顶点在队列 Q 中放置的次数使用归纳法。我们的归纳假设是所有 v 都属于 V 的 d[v] >= path(s,v)。

归纳的基础是在 BFS 的第 8 行将 s 放入 Q 之后的情况。

归纳假设在这里成立，因为 d[s] = 0 = path(s, s) 并且 d[v] = path (s, v) 对于所有 v 属于 V - {s}。

我的问题是作者所说的“我们对顶点放置在队列 Q 中的次数使用归纳法”是什么意思？以及它与归纳假设有何关系？

谢谢！