如何在迭代深度优先搜索中检测有向图中的循环？

Question

我目前的项目包括一组具有输入和输出的节点。每个节点可以取其输入值并生成一些输出值。这些输出可以作为其他节点的输入使用。为了最小化所需计算量，节点依赖性在应用启动时进行检查。更新节点时，它们按相互依赖的相反顺序进行更新。

也就是说，节点类似于有向图。我正在使用迭代DFS（不递归以避免在巨大图形中出现堆栈溢出）来计算依赖关系并创建一个更新节点的顺序。

我进一步想要避免图中的循环，因为循环依赖会破坏更新程序算法，并导致永久运行的循环。

通过跟踪递归堆栈上的节点，可以使用DFS递归方法找到循环，但是否有一种迭代方法可以做到这一点？然后，我可以将循环搜索嵌入主依赖项解析器中以加快速度。

- RenWal

Answer 1

有很多在线的循环检测算法。最简单的算法是Dijkstra算法的增强版本。您需要维护一个已访问节点列表和到达该节点的路径成本。在您的设计中，将“成本”替换为到达该节点的路径。

在算法的每个迭代中，您会获取“活动”列表上的下一个节点，并查看其后跟图中的每个节点（即它的依赖项）。如果该节点在“已访问”列表中，则存在循环。您在此处维护的路径显示了循环路径。

这样是否足以让您开始工作？

- Prune

Answer 2

尝试使用时间戳。在节点上添加元时间戳并将其设置为零。

以前的答案（不适用）：

当您开始搜索时，增加或获取time()时间戳。然后，当您访问节点时，将其与当前搜索时间戳进行比较。如果相同，则找到了一个循环。如果不是，则将时间戳设置为当前时间。

下一次搜索，再次增加。

好的，我假设您正在执行DFS搜索的方式如下：

- 将根节点添加到堆栈（用于搜索）和向量（用于更新）中。 - 弹出堆栈并将当前节点的子节点添加到堆栈和向量中 - 循环直到堆栈为空 - 反向迭代向量并通过引用子节点更新值

问题：循环会导致将相同的节点集添加到堆栈中。

解决方案1：在将节点添加到DFS搜索堆栈之前使用布尔值/时间戳查看是否已访问该节点。这将消除循环，但不会解决它们。您可以输出错误并退出。

解决方案2：使用时间戳，但每次弹出堆栈时递增。如果子节点设置了时间戳，并且它小于当前时间戳，则找到一个循环。重点在于，当反向迭代值时，可以检查子节点的时间戳是否大于当前节点。如果小于，则找到一个循环，但可以使用默认值。

事实上，我认为解决方案1可以通过在更新值时从不跟随多个子节点，并在启动时将所有节点设置为默认值来以同样的方式解决。解决方案2将在评估图形时向您发出警告，而解决方案1仅在创建向量时向您发出警告。

- James Poag

---

这种方法也可以称之为圆形：A是起始节点。A依赖于B和C。B和C都依赖于D。或者我漏掉了什么？我理解你的方法是“已访问”标志的替代方案。 - RenWal

一个很好的点。我假设你正在对依赖节点进行排队，并通过弹出队列的前面（DFS）来处理它们。然而，看起来你还想反向更新它们。需要更新答案... - James Poag

我想更新它们，以便如果A依赖于B，则先更新B再更新A。因此，基本上将它们放在堆栈上（是的，可以称之为“反向队列”）。该堆栈被保存，然后提供给更新程序线程。我不会在树遍历期间运行更新。一个循环是这样的：A是起始节点。A依赖于B。B依赖于C。C依赖于A。这种依赖关系显然无法解决，因此我需要识别这种情况。 - RenWal