问题标签 [depth-first-search]

我正在尝试针对 8 Queens 问题改进我当前的算法，这是我第一次真正处理算法设计/算法。我想结合此处描述的不同 Y 值的排列来实现深度优先搜索： http ://en.wikipedia.org/wiki/Eight_queens_puzzle#The_eight_queens_puzzle_as_an_exercise_in_algorithm_design

我已经实现了置换部分来解决问题，但是我在考虑深度优先搜索时遇到了一些麻烦。它被描述为一种遍历树/图的方式，但它会生成树图吗？只有当深度优先搜索生成要遍历的树结构时，这种方法才会更有效，这似乎是唯一的方法，通过实现一些逻辑来只生成树的某些部分。

所以本质上，我必须创建一个算法来生成一个修剪过的字典排列树。我知道如何实现修剪逻辑，但我只是不确定如何将它与排列生成器联系起来，因为我一直在使用 next_permutation。

是否有任何资源可以帮助我了解深度优先搜索的基础知识或以树形式创建字典排列？

关于深度优先搜索的维基百科：

深度优先搜索 (DFS) 是一种用于遍历或搜索树、树结构或图的算法。一个从根开始（在图中选择某个节点作为根），并在回溯之前沿着每个分支尽可能地探索 。

那么什么是广度优先搜索？

“一种算法，选择一个起始节点，检查所有节点回溯，选择最短路径，选择邻居节点回溯，选择最短路径，由于连续回溯遍历每条路径，最终找到最佳路径。

Regexfind的修剪——回溯？

回溯一词因其用途广泛而令人困惑。UNIXfind对 SO 用户的修剪通过回溯进行了解释。如果您不限制 Regex 的范围，Regex Buddy 使用术语“灾难性回溯”。这似乎是一个使用过于广泛的总称。所以：

1. 您如何专门为图论定义“回溯”？
2. 广度优先搜索和深度优先搜索中的“回溯”是什么？

[添加]

关于回溯和示例的良好定义

1. 蛮力法
2. Stallman（？）发明的术语“依赖导向回溯”
3. 回溯和正则表达式示例
4. 深度优先搜索定义。

我知道这个算法是如何工作的，但无法决定何时使用哪种算法？

是否有一些指导方针，其中一个比其他或任何考虑更好？

非常感谢。

我知道这个问题有很多答案。但是，我发现他们都没有真正做到这一点。
有人争辩说，循环（几乎）与强连接组件相同（s.在有向图中查找所有循环），因此可以使用为该目标设计的算法。
一些人认为，可以通过 DFS 并检查后边来找到循环（s. boost graph documentation on file dependencies）。

我现在想对是否可以通过 DFS 检测到图中的所有循环并检查后边提出一些建议？
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf（在 SO 上找到）说明了一种基于循环基础的方法。就我个人而言，我觉得它不是很直观，所以我正在寻找不同的解决方案。

编辑：我最初的看法显然是错误的。S.下一个答案是“白痴”。
初步意见：我的意见是，当 DFS-VISIT（S. DFS 的伪代码）新进入每个尚未访问的节点时，它确实可以这样工作。从这个意义上说，每个顶点都展示了一个循环的潜在开始。此外，由于 DFS 访问每条边一次，因此也覆盖了通向循环起点的每条边。因此，通过使用 DFS 和后端检查，确实应该可以检测到所有图中的循环。请注意，如果存在具有不同数量的参与者节点的循环（例如三角形、矩形等），则必须进行额外的工作来区分每个循环的实际“形状”。

DFS 主要用于在图中找到循环，而不是 BFS。有什么理由吗？两者都可以在遍历树/图时查找节点是否已被访问。

为方便起见，该表包含英语词典中的所有单词。

我想做的是能够将数据存储为 trie。这样我可以遍历 trie 的不同分支并返回最相关的结果。

首先，如何将表中的数据存储为 trie？

其次，如何遍历树？

如果它有帮助，那么上一个问题中的建议就是引发这个问题的地方。

请确保它是我们正在谈论的 SQL。由于指针，我理解了Mike Dunlavey 的 C 实现，但看不到这部分（特里树本身）在 SQL 中是如何工作的。

谢谢，
马特

我使用 Java 创建一个由指定的“行”和“列”组成的迷宫，看起来像一个网格。我计划使用深度优先递归方法在房间（由行和列创建的框）之间“打开门”。

我需要帮助编写一个 openDoor 方法来断开房间之间的链接。

我正在尝试在 C 中编写深度优先搜索。在搜索中，我不必维护一组所有可访问节点，而是必须将 Vertex 中的 isVisited 字段标记为 1 以表示已访问。这是我的数据结构和我的算法尝试。

这是我对 DFS 实施的尝试：

这个搜索的问题是它永远不会返回一个节点是可达的，即使它是可达的。有人知道我该如何纠正吗？

我了解 BFS 和 DFS，但是对于我的生活来说，我无法弄清楚迭代深化和 BFS 之间的区别。显然，迭代深化与 DFS 具有相同的内存使用量，但我无法看到这是怎么可能的，因为它只是像 BFS 一样不断扩展。如果有人能澄清那将是很棒的。

如果需要，可以处理的树：

我在 3D 计算机图形学方面做过一些工作，但对图论有点陌生。特别是，我一直在研究并尝试使用深度优先搜索 (DFS) 来解决我的问题，如 Mastering Algors w/Perl (Jarkko Hietaniemi) 中所述。到目前为止，我还没有得到它:-(但我很确定 DFS 是我想要的。

它不必是 Perl（只是想学习该语言），但 Java 或 C++ 会很好。

我有 53 个位置向量，即 (x,y,z)，我将其表示为

然后我运行一个我编写的 Perl 程序来生成节点之间的随机链接，并分配一些最大编号。跳数，比如说 6。所以拓扑可能看起来像这样

我想确定“运行”的路径，直到我遇到接收器，即 0。例如，节点 1 到节点 18 到节点 3，......这条路径已经完成。. . .

我想我想要 DFS；这似乎是一个递归练习。

如果有人理解并可以给我代码，那就太好了。我不是学生，但我已经 51 岁了！也许这与我没有得到这个有关:-)

我看着我的 q 并且出于某种原因（可能是我 :-( 它是“乱码”

拓扑应该看起来像 5 <-- 节点 1 有 5 个链接；18 4 23 6 48 <--节点18，节点4，节点23，节点6，节点48 2 <--节点2有2条链路；14 5, <-- 节点 14, 节点 5 0 <-- 节点 3 是叶子，因为它没有链接。. . 2 <-- 节点 18 有 2 个链接；3 17 <-- 节点 3，节点 17 。. . 4 <-- 节点 53 有 4 个链接；10 46 49 22 <-- 节点 10，节点 46，节点 49，节点 22

只是想清楚以防有人可以提供代码（Perl、Java、c++/C ...）

谢谢。