问题标签 [depth-first-search]

我正在尝试在我的游戏中实现深度优先搜索算法。我一直在研究这个网页： http: //www.mazeworks.com/mazegen/mazetut/index.htm，却发现我无法将它与块而不是墙一起使用。我所说的块是指覆盖整个单元格的正方形，而不仅仅是边缘。我认为这样做会更容易，但现在我不太确定。有人做过吗？如果是这样，怎么做？（伪代码很好）。或者，如果它更容易，我应该只使用墙壁方法吗？

有一群人 [比如说 1874 人]，他们都代表世界上不同的公司 [比如说 236 人]。我的任务是最好地确定每个人工作的公司。诀窍是我不能简单地问一个人“你在哪里工作”并得到答案，但我所拥有的是一份包含许多问题的问卷 [比如说 290 个问题] 以及我应该期望员工的确切回答每个公司的。有些公司可能有相同的答案，所以最后，即使我不能确切地确定一个人在哪家公司工作，我应该能够缩小范围并说他/她必须为其中一家公司工作。

使用多值映射和其他一些数据结构，我已经确定了我可以用 1 个问题 [query] 识别的所有公司。使用这些查询来表示树数据结构的根，我需要使用其他查询/问题作为分支来构建树的其余部分以识别其余部分。

有什么建议/帮助/建议吗？

情况如下：

• 应用程序世界由数十万个状态组成。
• 给定一个状态，我可以计算出一组 3 或 4 个其他可达状态。一个简单的递归可以构建一个状态树，它会很快变得非常大。
• 我需要从根状态到此树中的特定深度执行 DFS，以搜索包含“最小”状态的子树（计算节点的值与问题无关）。

使用单线程执行 DFS 可以，但速度很慢。向下覆盖 15 个级别可能需要几分钟，我需要改进这种糟糕的表现。尝试为每个子树分配一个线程会创建太多线程并导致OutOfMemoryError. 使用 aThreadPoolExecutor也好不到哪里去。

我的问题：遍历这棵大树的最有效方法是什么？

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

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

虽然我知道我们可以通过检测后端http://cs.wellesley.edu/~cs231/fall01/dfs.pdf来使用 DFS 算法检测周期。在遵循上述方法时，我无法弄清楚如何以有效和“干净”的方式输出循环中的节点。

将不胜感激一些帮助

谢谢

每次迭代重新扫描 n-1 级节点不是多余的吗？

此刻我有一个看起来有点像这样的对象。

我正在尝试将它转换为另一个看起来非常相似的对象，除了它不允许循环之外。

它应该通过不扩展已经出现在更高深度的节点的子节点来处理循环。迭代深化解决了这个问题（深度优先搜索实现但广度优先搜索顺序），但我正在努力使用以下结构的实现。

我发现的所有实现都依赖于找到某种目标节点，而我需要扩展整个树。

任何帮助，将不胜感激。:D

我有一棵树（在图形意义上）表示一棵树（在物理意义上）。树表示为一个 BGL 邻接表，其中每个顶点包含半径和位置属性，即我的图以以下形式定义

我想在树上执行 DFS 以创建分支列表。附加要求是，每当一个顶点有多个未探索的相邻顶点时，它都会选择具有最大半径的顶点。该规则确保图的遍历顺序代表物理树枝。

似乎 DFS 访问者不支持优先级队列，所以我想知道是否存在通过 A* 获取此信息的替代搜索公式？

或者，我可以通过对顶点进行排序来实现我自己的 DFS 算法，但如果可能的话，我宁愿利用 BGL 框架。

谢谢

-约翰

我有三角形集合，它定义了我的 3D 形状的网格表面，我想修复每个三角形的法线以指向异形。

我正在尝试以下（伪）：

1. 定义第一个三角形法线方向是正确的方向
2. 使用这样的 DFS 遍历网格：
3. 三角形 = 第一个三角形
4. foreach neigbour in triangle.getNeighbours
5. 如果邻居和三角形之间的角度大于 180 做邻居.flip()
6. 三角形 = 邻居
7. 如果邻居已经选择然后继续下一个邻居
8. 继续递归到 4.

但是算法中的第 5 步不起作用，因为无法知道角度是否大于 180，因为我需要知道女巫方向（顺时针或逆时针）。

你能帮我理解如何修复算法吗？

根据书（Intro to Algorithm），在dfs中，边缘分为4种：

1. 树边，如果在边(u,v)中，首先发现v，那么(u,v)就是树边。
2. Back Edge，如果......，v已经被发现并且v是一个祖先，那么它就是一个后边缘。
3. 前缘，如果……，v 已经被发现并且v 是u 的后代，它就是前缘。
4. Cross Edge，除上述三个外的所有边。

我的问题是当我试图确定 (u, v) 是后边还是前边时，如何确定 v 是你的祖先还是后代？