问题标签 [depth-first-search]

我有一个任务，我需要拍摄一些现有的照片[显示一些自动机（DFA、NFA、图灵机）]，并以某种方式将它们转换为一种格式，这使我能够使用数据将其表示为自动机以及将其编译成一些图形表示。你们中有人做过类似的事情吗？是否有任何 Python 库/框架可以让我以图形方式呈现一些自动机数据？

嘿，我参加了当地的编程比赛，他们问了我这个我做不到的问题，请帮助我解决这个问题。

编写一个程序，从一个迷宫大小的文件加载，然后是迷宫本身。为了模拟迷宫，我们使用字符“S”来指定起始单元格“.”。指定空闲单元格，“#”是墙，“F”是最后一个单元格。编写一个程序，找出从起始单元到最终单元的路径。你可以认为迷宫中有一个服从命令的机器人，那么对于下面的迷宫，机器人应该收到以下命令：上、上、右、右、下、下。

迷宫 1 文本文件

迷宫 2 文本文件

一般写你的程序（迷宫最大输入可以是200x200）。

帮助将不胜感激。我只是一个正在升起的大二学生，所以如果你能给我提供代码，那么我就能理解它，他们会自己再做一次。

我的问题并不是关于这两种搜索类型的机制。我觉得它比这更平凡 - 我不了解两者的输入和输出。更具体地说，在 CLRS 中，BFS 将图和源节点作为输入，而 DFS 仅将图作为输入。DFS 不关心你从哪里搜索吗？

这就是输入混乱。输出混乱是，在 DFS 中，当你完成后，你有一个类似表的结构记录每个节点的发现和完成时间，对吗？您如何从中提取解决方案，即从源节点到目标节点的路径？

我希望我说得通。谢谢！

编辑：这就是我所说的 DFS 不采用源节点的意思。这是来自 CLRS 的 DFS 伪代码。我看不到它在任何地方都有源节点。我看到它所做的只是遍历图中的所有节点。

此代码在python 官方图论论文中给出。这是代码：

我不擅长python，因为我还没有足够的练习和阅读它。您能否通过将其与 DFS 图中的子兄弟概念相关联来解释代码？谢谢。

我正在尝试为有向图编写方法 DFS 方法。现在我遇到了分段错误，我真的不确定它在哪里。根据我对有向图的理解，我相信我的逻辑是正确的……但是一双新的眼睛会是一个很好的帮助。

这是我的功能：

类定义：

谢谢！

我有一个YAML 组文件，我想将它放入一个名为 groups 的 MongoDB 集合中，其中包含类似文档{"name" => "golf", "parent" => "sports"}（顶级组，如运动，只是{"name" => "sports"}没有parent.）

我们正在尝试遍历嵌套的 hash，但我不确定它是否工作正常。我更喜欢使用递归方法而不是 lambda proc。我们应该改变什么才能让它发挥作用？

谢谢！

马特

我在某处读到 DFS 不适合找到解决方案，而 BFS 是..为什么？我真的不明白这是怎么回事..有人可以为我证明一个案例来证明这一点吗？

我需要使用 DFS 在有向图中找到最长的循环。

我曾经看到这篇 Wikipedia 文章描述了这样做的方式，我认为它解决了类似用以下三种状态之一标记节点的问题：节点尚未访问，已完成搜索节点，节点已访问，但尚未完成访问.

如果有人可以与我分享链接，我将不胜感激。顺便说一句，这不是 Tarjan 算法。

如果您想知道，下面的问题是我要解决的问题。

第一行给出的两位数是N和M，分别代表节点数和有向边数。

从第二行开始给出 M 组两个数字 A 和 B，这意味着节点 A 和 B 是连接的，但您只能从 A 遍历节点到 B。

输入.txt：

在这种情况下，答案是 6，因为 2>3>4>5>6>7>2。

我试图在包含 26 个节点的最小生成树上执行 DFS。节点被命名为“A”到“Z”并且树是无向的。

我在这里尝试编写一个名为 DFS 的空函数，它（我假设）在树（一个 2D 数组）中接收一个 startNode（随机选择的节点“M”）和 endNode（随机选择的节点“Z”） .

连接节点的权重在 2D 数组参数中标识，但我如何真正开始访问节点？

所需要的只是按照 DFS 遍历的顺序打印每个 nodeName。

我需要为二维数组中的每个节点创建一个 Node_class 吗？

我正在尝试通过使用 boost 图形库找到一种从特定顶点执行深度优先算法的方法。

Boost 库提供的深度优先算法评估从起始顶点到最后一个顶点的图。但是，如果必须从特定顶点搜索图形怎么办？

有什么建议么？