问题标签 [depth-first-search]

我想在有向图中找到所有循环。从一个节点开始深度优先搜索会找到一些循环（找到后边）。所以，我将 dfs 应用于图中的所有节点（即每次根是不同的节点）。我可以使用它来获得所有周期（通过消除重复的周期）。但是，我不确定这是否适用于所有图表以及这是否是正确的方法。谁能建议我这是否适用于所有情况。

谢谢

我最近（4 天）开始学习来自 C / Java 背景的 C++。为了学习一门新语言，我通常从重新实现不同的经典算法开始，尽可能地针对特定语言。

我来到了这段代码，它是一个 DFS - 无向图中的深度优先搜索。仍然从我读到的最好通过 C++ 中的引用传递参数。不幸的是，我不能完全掌握参考的概念。每次我需要参考时，我都会感到困惑，我会根据指针来思考。在我当前的代码中，我使用按值传递。

这是代码（可能不是应有的 Cppthonic）：

您能否通过引用此代码给我一些关于如何使用引用的提示？

我当前的编程风格是否与 C++ 的结构兼容？

对于 C++ 中的二维数组，vector 和 type** 是否有标准替代方案？

后期编辑：

好的，我已经分析了你的答案（谢谢大家），我已经以更 OOP 的方式重写了代码。我也明白什么是参考，并且要使用它。它有点类似于 const 指针，不同之处在于该类型的指针可以保存 NULL。

这是我最新的代码：

我了解 DFS 和 BFS 之间的区别，但我很想知道何时使用其中一种更实用？

谁能举例说明 DFS 如何胜过 BFS，反之亦然？

考虑下图：

我试图找到一种方法来枚举从源节点到目标节点的所有可能路径。例如，从 A 到 E，我们有以下可能的路径：

请注意，对于 ACDE，实际上有 2 条路径，因为其中一条使用边 F3，另一条使用边 F5。此外，由于 A 和 C 之间存在循环，因此您最终可能会得到无限数量的路径，但出于此目的，我只对在从源到目标的路径上没有重复节点的路径感兴趣。

我写了一个深度优先搜索（DFS）算法，但问题是当你在 2 个节点之间有多个边时（比如上面的边 F3 和 F5）我不知道如何处理它。我的算法只带回路径A C D E和A C E，而不带回其他路径。在 的情况下A B C E，我理解原因，因为它从 A 开始，然后到 C 并构建这些路径，但是当 DFS 回到节点 B 时，它然后尝试去 C，但是 C 已经被访问过所以它停止了。

无论如何，我只是想知道是否有办法做到这一点，或者这可能是 NP 完全的。

如果您想查看我的 DFS，代码如下（抱歉滥用宏，我在竞赛编程中使用这些，所以有点习惯）。

输出：

我正在尝试编写一个 DFS 来解决多个过河问题（Fox Goat Cabbage、Jealous Husbands、Mercenaries and Cannibals 等）。我已经编写了拼图类，但是在构建求解器时遇到了麻烦。我了解 DFS 的工作原理，但我不知道从哪里开始使其适应这种设计。

每个谜题都有一个 move() 方法，如果它是有效的移动，则返回 true，如果它违反规则集，则返回 false。乘客在代表河流每一侧的一对列表中被跟踪。求解器可以访问这些列表，但我不确定如何使用它来生成可能的移动集，因为每次乘客过河时可能的移动都会改变。

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

我解决了 N-Queen 问题，条件是每列只能有一个皇后。所以我把一个皇后放在第一列的一个方格中，然后移动到下一列，把一个皇后放在船上没有被皇后攻击的方格中。我可以使用这种方法找到所有解决方案，但是在 n=13 之后开始需要很长时间。此外，我发现该问题的大多数解决方案都可以通过旋转和反射极少数不同的解决方案来找到。例如，8 个皇后问题有 92 个总解决方案，其中只有 12 个是不同的。（http://en.wikipedia.org/wiki/Eight_queens_puzzle）

所以我的问题是我如何检查电路板的这些状态，并且只将这些状态推送到堆栈中，从而给出不同的解决方案？

这就是我现在正在做的事情。

我需要编写一个 Lisp 函数来查找两个节点之间的最长路径，而无需重新访问任何节点。但是，如果起始节点和结束节点相同，则可以重新访问该节点。该函数需要既是递归的又是深度优先搜索的。

我一直试图解决这个问题几个小时，但无法提出解决方案。我知道该功能的大致轮廓，但无法正确编程。在一些代码中，主要是伪代码：

网络看起来像 '((ab) (bc)) ，其中第一项是节点，其他一切都是它的邻居（例如节点 a 有邻居 b，节点 b 有邻居 c）。

是的，这是用于家庭作业的，所以如果您不愿意发布解决方案或其中的任何部分，请不要发布。我是 Lisp 的新手，想要一些技巧/帮助来获得一个体面的开始。

谢谢

编辑：嗯，我能得到的最多的是：

它会产生正确的解决方案，除非开始节点和结束节点相同。即使它们相同，我也不知道如何执行搜索。

我尝试编写一个脚本来计算图形的连接组件，但我无法获得正确的解决方案。我有一个包含 6 个节点（顶点）的简单图，节点 1 和 2 已连接，节点 3 和 4 已连接（6 个顶点；1-2,3-4,5,6）。所以该图包含 4 个连通分量。我使用以下脚本来计算连接的组件，但我得到错误的结果 (2)。

谁能帮我找出错误？

大家好，任何人都可以帮助我解决 DFS 算法：Path* agent_DFS (void* arg1,...); 这是用 C 程序编写的，是关于人工智能的，我必须找到一种方法让汽车达到他的目标..?? 它返回一个类型路径数组我对此完全不知道......请帮助我