我当前的项目包含一组带输入和输出的节点 . 每个节点都可以获取其输入值并生成一些输出值 . 这些输出可以用作其他节点的输入 . 为了最小化所需的计算量，在应用程序启动时检查节点依赖性 . 更新节点时，它们以相互依赖的相反顺序更新 .
也就是说，节点类似于 directed graph . 我正在使用迭代DFS（没有递归来避免巨大的图形中的堆栈溢出）来计算依赖关系并创建更新节点的顺序 .
我还想避免图中的循环，因为循环依赖会破坏更新程序算法并导致永远运行的循环 .
通过跟踪递归堆栈上的节点，有递归方法来查找带有DFS的循环，但 is there a way to do it iteratively ？然后我可以在主依赖解析器中嵌入循环搜索以加快速度 .
2 回答
试试时间戳 . 添加元时间戳并在节点上将其设置为零 .
先前的答案（不适用）：
好的，这就是我假设您正在执行DFS搜索的方式：
将根节点添加到堆栈（用于搜索）和向量（用于更新） .
弹出堆栈并将当前节点的子节点添加到堆栈和向量中
循环直到堆栈为空
反向迭代向量并更新值（通过引用子节点）
问题：Cycles会导致将相同的节点集添加到堆栈中 .
解决方案1：在添加到DFS搜索堆栈之前，使用布尔/时间戳来查看是否已访问该节点 . 这将消除周期，但不会解决它们 . 您可以吐出错误并退出 .
解决方案2：使用时间戳，但每次弹出堆栈时都会增加时间戳 . 如果子节点设置了时间戳，并且它小于当前戳记，则表示您已找到一个周期 . 这是踢球者 . 向后迭代值时，可以检查子节点的时间戳，以查看它们是否大于当前节点 . 如果更少，那么您已找到一个循环，但您可以使用默认值 .
事实上，我认为解决方案1可以通过在更新值并在启动时将所有节点设置为默认值时从不跟随多个子节点来以相同方式解析 . 解决方案2将在评估图形时给出警告，而解决方案1仅在创建矢量时向您发出警告 .
有很多循环检测算法可供在线使用 . 最简单的是Dijkstra算法的增强版本 . 您维护一个受访节点列表和成本 . 在您的设计中，将"cost"替换为到达那里的路径 .
在算法的每次迭代中，您将获取"active"列表中的下一个节点，并查看图中其后的每个节点（即每个依赖项） . 如果该节点在"visited"列表中，那么您有一个循环 . 你在这里保持的
path显示了循环路径 .这足以让你感动吗？