问题标签 [depth-first-search]

I have this code which iterates over a tree, doing a depth-first search. Every element is tackled exactly once. Very good.

BUT: How can I keep track of the current depth in the graph? I need to know the level of depth. So for example I have these nodes:

A has childs B, J. B has child C. C has child D. D has childs E, F, I.

When A is at depth level 1, then B is 2 and C is 3.

With recursion it was very easy to keep track of the current depth level. Just inrement a variable before calling itself and decrement it after calling itself.

But here with this fancy while loop that is not possible. There is no box in the box in the box happening like with recursion.

I don't really want to have to add properties (or instance variables) to the TreeNode object as this should be re-usable in a generic way for any kind of object graph.

Does anyone have an idea how to do this? Must I introduce another array to keep track of visited nodes?

作为一个母语不是英语的人（俄罗斯），我在维基百科上阅读了这篇文章：http ://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Heuristic_search/Depth-first_search

我尝试遵循这个用硬核英语编写的伪代码示例，几乎没有解释或评论。

特别是，我不明白他们试图用这句话说什么：

对于与你相邻的所有节点 v

我对这句话的问题是“相邻”部分。我的字典说这意味着“邻居”。所以我必须遍历你的超级节点的子节点？注意 u 是图中的一个节点。

或者他们是想说我必须遍历你的所有子节点？因为这将产生巨大的影响。

除了那些英语问题，他们忘了提d和p的意思，这让我把我所有的头发都扯掉了（是的，即使是我胡子上的那些）。

文章中的链接只是重复了这个没什么意义的神秘东西。也许有人能够以一种更易于阅读的方式重新编写它，有更多的评论和有意义的变量？我没有找到任何真正好的解释，这不仅仅是为了炫耀与 DFS 相关的作者的主导智慧。

因此，如果有人可以以更好的方式即时重写它，并具有更大的学习价值，这将节省我的一天，节省我的胡子。保存一切。谢谢你。

我在随机访问从一个节点到它的邻居时遇到了麻烦，很少访问整个图（一个 MxN 数组，在这个测试 4x4 中），我不明白我在这里做错了什么。

这段代码给了我这样的输出：

即使我正在验证下一步的位置（通过布尔值 southValid、eastValid 等）

对于 Java 中的 DFS 迷宫生成，我想随机化 DFS 的递归调用的顺序：

我怎样才能做到这一点？

我正在使用深度优先搜索来生成迷宫。

使用 DFS 以随机顺序遍历 M*N 个顶点的邻接矩阵，我只对生成随机路由感兴趣。

这个东西在减少顶点数量的情况下工作得很好，但是在使用它时我得到了一个 StackOverflow 异常

问题： a）如何使用堆栈将此递归调用更改为迭代调用？

b）有没有办法为方法调用堆栈分配更多内存？

我正在通过堆栈通过矩阵实现 DFS 迭代搜索，以便稍后生成迷宫。事情是在没有弹出它的情况下推动第一个元素：

完整代码：

我已经尝试过；搜索和搜索，但无法真正找到解决我问题的算法。我想枚举一棵树中的所有路径，（不仅仅是简单的路径）那些以叶节点开始和结束的路径（虽然这是一个简单的约束）。

例如，对于一棵树；

我希望能够生成以下路径：

我想就是这样。

我尝试了以下解决方案使用深度优先搜索查找所有简单路径的复杂性？. 但是，这只能找到简单的路径，因此无法找到诸如 4-2-5-2-1-3-6 之类的路径。

有什么方法可以指导我，或者任何算法？

我正在用 java 做一个 8 块益智游戏，我做 DFS 以找到解决方案的分配命令，从随机状态开始。

我有一个 Node 类，每个 Node 对象都知道它使用 int[][] 处于什么状态以及它的父节点是什么。它还知道它可以向哪个方向移动（左、右、上、下）

从单个节点开始，开始节点，我的程序为其所有可能的子节点创建一个节点。它检查空白方块可以移动的可用方向，它检查它是否不会回到已经属于另一个节点的状态。所以在上面的例子中，起始节点会展开如下：

我处理这个问题的方法是我探索第一个节点并将它的所有子节点推入堆栈，这发生在递归方法中，循环扩展每个节点直到达到目标状态或达到截止（我提供给避免永远循环）

只要我的截止值不太高，代码就可以正常工作，如果它比我得到错误：java.lang.StackOverflowError

我究竟做错了什么？

我能找到的所有延续教程都是关于固定长度延续的（即数据结构在遍历时具有已知数量的项目

我正在实现 DepthFirstSearch Negamax(http://en.wikipedia.org/wiki/Negamax)，虽然代码有效，但我想使用延续重写代码

我的代码如下

其中 update 使用给定的移动更新游戏状态， eval 评估游戏状态并返回一个增量器（当前未使用）用于增量评估， isTerminal 评估该位置是否为结束位置。

问题是我必须注册一个未知数量的动作（每个剩余的 list.map 迭代）才能继续，我实际上无法想象一种有效的方法来做到这一点。

由于这是一个指数算法，我显然希望尽可能地保持它的效率（虽然我的大脑在试图弄清楚这个是我们的，所以我确实想要答案而不是一个有效的答案）

谢谢

这里为什么Unmark vertex v需要？为什么添加这样的行是安全的，因此 v 再次无法访问，会导致重新访问吗？