问题标签 [depth-first-search]

我正在尝试以递归深度优先方式找到最近的邻居。在达到这一点之前涉及许多元素，为了简单起见，我只包括了我目前遇到问题的部分。

我的想法是根据某个阈值距离找到给定点的最近邻居，我决定将过程 int 分为两种方法。一个真正找到最近邻居是否存在的方法，以及其他方法来一遍又一遍地递归调用该函数。

我有带有双值的 ArrayList，我将其视为点...如果返回 0.0，则意味着我没有找到最近的邻居（想知道我是否真的使用 Object，一旦我清理逻辑可能会这样做）。

这是我的方法，我计划以递归 dfs 方式调用上述方法。

我正在努力的是递归深度优先搜索。除此之外，我的访问者实现看起来不正确。

这就是我试图处理访客的方式

然后我会创建一个 VisitedPoint 对象，private VisitedPoint[] isVisited;但是当我在 isBelongTo() 方法中使用它时，我得到一个空指针异常。

提前感谢您的帮助。

感谢大家回复想法和替代解决方案。更有效的解决问题的方法总是受欢迎的，并且提醒我质疑我的假设。也就是说，我希望你暂时忽略我试图用算法解决的问题，并帮助我分析我的算法的复杂性，因为我已经编写了它——所有简单的路径在使用深度限制搜索的图表中，如此处所述，并在此处实现。谢谢！

编辑：这是家庭作业，但我已经提交了这个作业，我只想知道我的答案是否正确。当涉及到递归时，我对 Big-O 复杂性感到有些困惑。

下面的原始问题：

我试图找到该算法给出的所有路径搜索的复杂性。给定两个顶点，我使用深度优先搜索找到它们之间的所有简单路径。

我知道DFS的时间复杂度是O(V+E)，它的空间复杂度是O(V)，我的直觉是全路径搜索的复杂度会更多，但是我做不到确定它将是什么。

相关的 SO 问题在这里和这里。

更新（回应下面的评论）：

我正在尝试解决凯文培根的六度问题。这通常需要找到一对演员之间的最低分离度，但我必须找到所有的分离度（目前，小于 6，但这可以改变）。

上面的代码在存储为邻接矩阵的图上实现了 dfs，我请求一个建议，我应该做些什么改变才能知道生成的图是否连接。

我回来了另一个类似的问题。我目前正在开发一个 Java 程序，该程序将检查图形是否是 2 色的，即它是否不包含奇数循环（奇数长度的循环）。整个算法应该在 O(V+E) 时间内运行（V 是所有顶点，E 是图中的所有边）。我当前的算法进行深度优先搜索，记录路径中的所有顶点，然后查找后边缘，然后记录边缘位于哪些顶点之间。接下来，它从后边缘的一端跟踪一条路径，直到它碰到边缘另一端的另一个顶点，从而追溯后边缘完成的循环。

我的印象是，对于我图中存在的所有循环，这种遍历可以在 O(V+E) 时间内完成，但我一定遗漏了一些东西，因为我的算法运行了非常长的时间。图（10k 个节点，不知道有多少边）。

我的算法完全错误吗？如果是这样，任何人都可以为我指出正确的方向，以便更好地记录这些循环，或者判断它们是否有奇数个顶点？感谢你们提供的任何和所有帮助。如果您需要，代码如下。

补充：对不起，我忘了，如果图表不是 2-colorable，我需要提供一个奇数循环来证明它不是。

顶点类

我通过以下方式在加权有向图上实现 DFS：

我需要修改上述内容以允许在搜索源节点和目标节点之间的所有路径期间循环。为避免无限循环，可以设置条件以根据“停止”的数量或从源行进的最大允许距离来终止搜索。

例如，这样我可以找到从 A 开始到 D 结束的行程数，恰好有 5 个停靠点：一种解决方案可以是 ABCDCD。或者，我可以找到从 D 到 D 的距离小于 40 的不同路线的数量：一些解决方案是 DECD、DEBCD、DCDCD。

我的问题是我不确定如何创建保持主算法搜索的逻辑，同时逃避保证不会到达目标节点的无限搜索循环。

假设我想从 A 到 D。一个可能的死循环可能是 ABCEBCEBCEB....（到无穷大）。我基于停靠点数或总行驶距离的条件可以终止此循环，但也将结束整个搜索，否则可能会找到正确的路径 ABCDCDCDCD，当满足任一预设条件时，它将正确终止。

感谢您的任何想法。

我正在使用深度优先搜索来识别有向加权图中的路径，同时重新访问属于循环的节点，并根据行进的总距离或从源节点停止的距离设置截止条件。

据我了解，使用递归，深度优先搜索不需要显式堆栈结构，所以我想知道是否可以通过某种方式不使用显式堆栈来进一步简化下面的代码：

然而，其他没有显式堆栈结构的递归实现通常会考虑已经访问过的节点，将它们着色为白色、灰色或黑色。那么，在我允许重新访问并且需要记录路径的情况下，绝对需要显式堆栈吗？感谢您对更简单的替代方案的任何建议。

我正在尝试在 Python 中进行深度优先搜索，但它不起作用。

基本上我们有一个钉子纸牌板：

1 代表挂钩，0 代表空位。您必须一次将一个钉子向后或向前移动两个槽位到一个空位。如果您在此过程中跳过另一个挂钩，它将成为一个空槽。你这样做直到剩下一个钉子。所以基本上，一个游戏是这样的：

这是我所拥有的：

所以，现在我的问题：

1. 这是进行深度优先搜索的正确方法吗？
2. 我的算法不行！！！它卡住了。在问这里之前，我已经为此苦苦挣扎了几天，所以请帮忙。
3. 看起来我没有关注 DRY，有什么建议吗？
4. 天哪，帮帮我？

我在 Java 上制作了一个流程图编辑器。它会淹没流程图并将它们相互连接并为我创建两个数组。其中一个显示连接节点和线，另一个显示相互连接的元素。我必须找到从开始两个和开始的所有方法。例如，如果我有一些钻石用于决策，我有两种不同的方式..我想获得所有这些方式..我必须使用哪些算法？

编辑3： 再次解决嗨，我自己解决了我的问题..这是我的代码..））

编辑1：当我解决我的问题时，我解决了一个部分，没有也有错误......这里我的问题更深入的描述：我有一个描述元素之间连接的数组

这是我的连接数组..我试图找到从 A 到 E 的所有方法

有2种方式

A->B->C->E

A->B->D->E

我可以找到从左到右搜索数组的第一种方式。如果我看到 1，我取 J 的 walu e 并转到 i 中的第 J 行，使该元素 2 并从 [i,j+1] 开始搜索，如果到达 E，则发送结果。

但在这里我的问题是在第一行的第二次搜索中它不会看到 1 并且会进入第二行并且有第一个元素 1 但它指的是第一行并且它将是循环的。

我也尝试将 DFS 与回溯一起使用，但它并不是指显示所有路径，而是仅显示一条路径。

如果我找到 1 并开始搜索 [i,j]，我已经尝试将列下方的所有内容设为 0，但在第二次搜索中它不会看到任何内容，并且我的 arry 表出现了一个空白表））。

我知道我错过了一件事，但我想不通..

编辑2：

现在我关闭了解决方案，但又出现了问题。我使用此代码从矩阵计算路径

}

结束它的输出是

成立 成立 成立

[ 0 0, 0 1, 1 2, 2 4, 1 3, 3 4]

2 表示已访问和更改.. 问题是您在已访问列表中添加的

00 , 01 , 12, 24 这是第一个路径，但只有 13,34 。这是因为我将数组的其余部分更改为 0 以不搜索。我该如何解决这个问题？它必须是 00,01,12,24 和 00,01 或 10,13,34.. 有什么想法吗？而且我不认为这是 DFS 或 BFS ？或者是其他东西？？

在为我的 Graph 实现实现了大部分常用和需要的功能之后，我意识到有几个功能（删除顶点、搜索顶点和获取顶点）没有“最佳”实现。

我正在为我的 Graph 实现使用带有链接列表的邻接列表，并且我正在一个接一个地搜索一个顶点，直到找到我想要的那个。就像我说的，我意识到我没有使用“最好的”实现。我可以有 10000 个顶点并且需要搜索最后一个顶点，但是那个顶点可以有一个到第一个顶点的链接，这会大大加快速度。但这只是一个假设的情况，它可能会发生也可能不会发生。

那么，您推荐什么算法用于搜索查找？我们的老师主要谈论广度优先和深度优先（还有 Dikjstra 的算法，但那是完全不同的主题）。在这两者之间，你推荐哪一个？

如果我能同时实现这两者就完美了，但我没有时间，我需要拿起一个并在第一阶段截止日期临近时实现它......

我的猜测是，使用深度优先，似乎更容易实现，并且查看它们的工作方式，这似乎是最好的选择。但这实际上取决于输入。

但是你们有什么建议呢？

何时修剪在深度优先搜索中不再有效？我一直在研究一种解决 N-Queens 问题的有效方法，并且我第一次考虑修剪。我已经为前两行实现了它，但是它什么时候不再有效？我应该修剪到多远？