检测有向图中所有周期的最有效算法是什么？
我有一个有向图表示需要执行的作业的计划，作为节点的作业和作为边缘的依赖 . 我需要检测此图中循环的错误情况，从而导致循环依赖 .
最简单的方法是对图形进行深度优先遍历（DFT） .
如果图形具有 n 个顶点，则这是一个 O(n) 时间复杂度算法 . 由于您可能必须从每个顶点开始执行DFT，因此总复杂度变为 O(n^2) .
n
O(n)
O(n^2)
您必须维护一个包含当前深度首次遍历中所有顶点的堆栈，其第一个元素是根节点 . 如果你在DFT期间遇到一个已经在堆栈中的元素，那么你就有一个循环 .
Tarjan's strongly connected components algorithm具有 O(|E| + |V|) 时间复杂度 .
O(|E| + |V|)
有关其他算法，请参阅维基百科上的Strongly connected components .
鉴于这是一份工作计划，我怀疑在某些时候你会将它们分类为一个建议的执行顺序 .
如果是这种情况，那么topological sort实现可以在任何情况下检测周期 . UNIX tsort 当然可以 . 因此，我认为在tsorting的同时检测循环可能更有效，而不是在单独的步骤中 .
tsort
因此，问题可能变成“我如何最有效地进行切割”，而不是“我如何最有效地检测循环” . 答案可能是“使用库”，但未通过以下维基百科文章：
http://en.wikipedia.org/wiki/Topological_sorting
具有一个算法的伪代码，以及来自Tarjan的另一个算法的简要描述 . 两者都有 O(|V| + |E|) 时间复杂度 .
O(|V| + |E|)
从DFS开始：当且仅当在DFS期间发现后沿时，才存在循环 . 这被证明是白路理论的结果 .
在我看来，用于检测有向图中的周期的最易理解的算法是图着色算法 .
基本上，图形着色算法以DFS方式遍历图形（深度优先搜索，这意味着它在探索另一条路径之前完全探索路径） . 当它找到后边缘时，它将图形标记为包含循环 .
有关图形着色算法的深入解释，请阅读本文：http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
另外，我在JavaScript中提供了图着色的实现https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js
如果无法向节点添加“已访问”属性，请使用集合（或映射），并将所有已访问的节点添加到集合中，除非它们已在集合中 . 使用唯一键或对象的地址作为“键” .
这也为您提供了有关循环依赖关系的“根”节点的信息，当用户必须解决问题时，它将派上用场 .
另一种解决方案是尝试查找要执行的下一个依赖项 . 为此，您必须有一些堆栈，您可以记住您现在的位置以及下一步需要做的事情 . 在执行之前检查该堆栈上是否已存在依赖项 . 如果是，你找到了一个循环 .
虽然这似乎有O（N * M）的复杂性，但您必须记住堆栈的深度非常有限（因此N很小）并且M变小，每个依赖关系都可以检查为"executed"加上你可以当你找到一片叶子时停止搜索（所以你必须检查每个节点 - > M也会很小） .
在MetaMake中，我将图形创建为列表列表，然后在执行时删除每个节点，这自然会减少搜索量 . 我从来没有必要进行独立检查，这一切都在正常执行期间自动发生 .
如果您需要“仅测试”模式，只需添加一个“干运行”标志，该标志禁用实际作业的执行 .
没有算法可以在多项式时间内找到有向图中的所有周期 . 假设有向图有n个节点，每对节点都有相互连接，这意味着你有一个完整的图 . 因此，这n个节点的任何非空子集指示一个周期，并且存在2 ^ n-1个这样的子集 . 因此不存在多项式时间算法 . 因此，假设您有一个有效的（非愚蠢的）算法，它可以告诉您图中的定向循环数，您可以先找到强连接组件，然后在这些连接的组件上应用算法 . 由于循环仅存在于组件内而不存在于组件之间 .
我在sml（命令式编程）中实现了这个问题 . 这是大纲 . 找到具有0的indegree或outdegree的所有节点 . 这样的节点不能是循环的一部分（因此删除它们） . 接下来，从这些节点中删除所有传入或传出边缘 . 递归地将此过程应用于结果图 . 如果最后你没有任何节点或边缘，图表没有任何周期，否则它有 .
如果DFS找到了指向已经访问过的顶点的边，你有一个循环 .
https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length我喜欢这个解决方案最好特别为4长:)
另外，物理向导说你必须做O（V ^ 2） . 我相信我们只需要O（V）/ O（V E） . 如果图形已连接，则DFS将访问所有节点 . 如果图形已经连接了子图形，那么每次我们在该子图形的顶点上运行DFS时，我们将找到连接的顶点，并且不必在下一次运行DFS时考虑这些 . 因此，为每个顶点运行的可能性是不正确的 .
我这样做的方法是进行拓扑排序，计算所访问的顶点数 . 如果该数字小于DAG中的顶点总数，则表示您有一个循环 .
正如你所说，你有一组工作，需要按一定的顺序执行 . Topological sort 为您提供了调度作业所需的订单（如果是 direct acyclic graph ，则为依赖性问题） . 运行 dfs 并维护一个列表，并开始在列表的开头添加节点，如果遇到已访问过的节点 . 然后你在给定的图表中找到了一个循环 .
Topological sort
direct acyclic graph
dfs
如果图表满足此属性
|e| > |v| - 1
然后图表至少包含循环 .
13 回答
最简单的方法是对图形进行深度优先遍历（DFT） .
如果图形具有
n个顶点，则这是一个O(n)时间复杂度算法 . 由于您可能必须从每个顶点开始执行DFT，因此总复杂度变为O(n^2).您必须维护一个包含当前深度首次遍历中所有顶点的堆栈，其第一个元素是根节点 . 如果你在DFT期间遇到一个已经在堆栈中的元素，那么你就有一个循环 .
Tarjan's strongly connected components algorithm具有
O(|E| + |V|)时间复杂度 .有关其他算法，请参阅维基百科上的Strongly connected components .
鉴于这是一份工作计划，我怀疑在某些时候你会将它们分类为一个建议的执行顺序 .
如果是这种情况，那么topological sort实现可以在任何情况下检测周期 . UNIX
tsort当然可以 . 因此，我认为在tsorting的同时检测循环可能更有效，而不是在单独的步骤中 .因此，问题可能变成“我如何最有效地进行切割”，而不是“我如何最有效地检测循环” . 答案可能是“使用库”，但未通过以下维基百科文章：
具有一个算法的伪代码，以及来自Tarjan的另一个算法的简要描述 . 两者都有
O(|V| + |E|)时间复杂度 .从DFS开始：当且仅当在DFS期间发现后沿时，才存在循环 . 这被证明是白路理论的结果 .
在我看来，用于检测有向图中的周期的最易理解的算法是图着色算法 .
基本上，图形着色算法以DFS方式遍历图形（深度优先搜索，这意味着它在探索另一条路径之前完全探索路径） . 当它找到后边缘时，它将图形标记为包含循环 .
有关图形着色算法的深入解释，请阅读本文：http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
另外，我在JavaScript中提供了图着色的实现https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js
如果无法向节点添加“已访问”属性，请使用集合（或映射），并将所有已访问的节点添加到集合中，除非它们已在集合中 . 使用唯一键或对象的地址作为“键” .
这也为您提供了有关循环依赖关系的“根”节点的信息，当用户必须解决问题时，它将派上用场 .
另一种解决方案是尝试查找要执行的下一个依赖项 . 为此，您必须有一些堆栈，您可以记住您现在的位置以及下一步需要做的事情 . 在执行之前检查该堆栈上是否已存在依赖项 . 如果是，你找到了一个循环 .
虽然这似乎有O（N * M）的复杂性，但您必须记住堆栈的深度非常有限（因此N很小）并且M变小，每个依赖关系都可以检查为"executed"加上你可以当你找到一片叶子时停止搜索（所以你必须检查每个节点 - > M也会很小） .
在MetaMake中，我将图形创建为列表列表，然后在执行时删除每个节点，这自然会减少搜索量 . 我从来没有必要进行独立检查，这一切都在正常执行期间自动发生 .
如果您需要“仅测试”模式，只需添加一个“干运行”标志，该标志禁用实际作业的执行 .
没有算法可以在多项式时间内找到有向图中的所有周期 . 假设有向图有n个节点，每对节点都有相互连接，这意味着你有一个完整的图 . 因此，这n个节点的任何非空子集指示一个周期，并且存在2 ^ n-1个这样的子集 . 因此不存在多项式时间算法 . 因此，假设您有一个有效的（非愚蠢的）算法，它可以告诉您图中的定向循环数，您可以先找到强连接组件，然后在这些连接的组件上应用算法 . 由于循环仅存在于组件内而不存在于组件之间 .
我在sml（命令式编程）中实现了这个问题 . 这是大纲 . 找到具有0的indegree或outdegree的所有节点 . 这样的节点不能是循环的一部分（因此删除它们） . 接下来，从这些节点中删除所有传入或传出边缘 . 递归地将此过程应用于结果图 . 如果最后你没有任何节点或边缘，图表没有任何周期，否则它有 .
如果DFS找到了指向已经访问过的顶点的边，你有一个循环 .
https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length我喜欢这个解决方案最好特别为4长:)
另外，物理向导说你必须做O（V ^ 2） . 我相信我们只需要O（V）/ O（V E） . 如果图形已连接，则DFS将访问所有节点 . 如果图形已经连接了子图形，那么每次我们在该子图形的顶点上运行DFS时，我们将找到连接的顶点，并且不必在下一次运行DFS时考虑这些 . 因此，为每个顶点运行的可能性是不正确的 .
我这样做的方法是进行拓扑排序，计算所访问的顶点数 . 如果该数字小于DAG中的顶点总数，则表示您有一个循环 .
正如你所说，你有一组工作，需要按一定的顺序执行 .
Topological sort为您提供了调度作业所需的订单（如果是direct acyclic graph，则为依赖性问题） . 运行dfs并维护一个列表，并开始在列表的开头添加节点，如果遇到已访问过的节点 . 然后你在给定的图表中找到了一个循环 .如果图表满足此属性
然后图表至少包含循环 .