在有向图中检测周期的最佳algorithm
在有向图中检测所有周期的最有效的algorithm是什么？
我有一个有向图，表示需要执行的作业的时间表，作业是一个节点，依赖关系是一个边。 我需要检测这个图中循环的错误情况，导致循环依赖。
Tarjan强连通分量algorithm的时间复杂度为O(|E| + |V|) 。
对于其他algorithm，请参阅Wikipedia上的强连接组件 。
考虑到这是一个工作时间表，我怀疑在某个时候你会把它们分类为一个build议的执行顺序。
如果是这样的话，那么拓扑sorting实现可以在任何情况下检测周期。 UNIX tsort当然可以。 我认为这样做可能更有效，因为在同时检测周期而不是在单独的步骤中。
所以这个问题可能会变成“我怎么最有效地呃逆”，而不是“我如何最有效地检测循环”。 答案可能是“使用图书馆”，但没有达到以下维基百科文章：
有一个algorithm的伪代码，还有一个来自Tarjan的简单描述。 两者都有O(|V| + |E|)时间复杂度。
从DFS开始：当且仅当在DFS期间发现后端时才存在循环。 这被certificate是白道理论的结果。
最简单的方法是对图进行深度优先遍历（DFT） 。
如果图有n个顶点，则这是一个O(n)时间复杂度algorithm。 由于您可能需要从每个顶点开始进行DFT，因此总复杂度变为O(n^2) 。
您必须维护一个包含当前深度第一次遍历的所有顶点的栈 ，其第一个元素是根节点。 如果在DFT期间遇到已经在堆栈中的元素，则有一个循环。
在我看来，在有向图中检测周期最容易理解的algorithm是图着色algorithm。
基本上，图着色algorithm以DFS方式（深度优先search，这意味着它在探索另一条path之前完全探索path）走图。 当它find一个后沿时，它将graphics标记为包含一个循环。
有关图着色algorithm的深入说明，请阅读以下文章： http : //www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
另外，我在JavaScript中提供了图着色的实现https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js
如果你不能添加一个“被访问”的属性到节点，使用一个集合（或映射），只是将所有访问节点添加到集合，除非它们已经在集合中。 使用唯一的键或对象的地址作为“键”。
这也给你提供了有关循环依赖的“根”节点的信息，当用户必须解决这个问题时，它将派上用场。
另一个解决scheme是尝试find下一个依赖项来执行。 为此，您必须有一些堆栈，您可以记住现在的位置以及下一步要做的事情。 在执行之前检查一个依赖项是否已经在这个栈上。 如果是的话，你find了一个循环。
虽然这可能看起来有O（N * M）的复杂性，但您必须记住堆栈的深度非常有限（所以N很小），并且每个依赖关系的M都会变小，您可以检查为“已执行”你可以停止search，当你发现一个叶子（所以你永远不必检查每个节点 – > M也会很小）。
在MetaMake中，我创build了图表作为列表的列表，然后删除每个节点，因为我执行它们时自然减less了search量。 我从来没有必要运行一个独立的检查，这一切都在正常执行过程中自动发生。
如果您需要“仅testing”模式，只需添加一个禁止执行实际作业的“空运行”标志。
没有一种algorithm可以在多项式时间内find有向图中的所有周期。 假设有向图有n个节点，每一对节点之间都有连接，这意味着你有一个完整的图。 因此，这n个节点的任何非空子集都表示一个周期，并且有2 ^ n-1个这样的子集。 所以不存在多项式时间algorithm。 所以假设你有一个有效的（非愚蠢的）algorithm，它可以告诉你一个图中有向循环的数量，你可以先find强连通的组件，然后在这些连接的组件上应用你的algorithm。 因为循环只存在于组件内而不在它们之间。
我已经在sml（命令式编程）中实现了这个问题。 这是纲要。 find所有有不完整或超出0的节点。 这样的节点不能成为一个循环的一部分（所以删除它们）。 接下来从这些节点中删除所有传入或传出边缘。 recursion地将此过程应用于生成的图。 如果最后没有留下任何节点或边，则图没有任何循环，否则就是。
如果DFSfind指向已经访问过的顶点的边，那么在那里有一个循环。
我这样做的方式是做一个拓扑sorting，计算访问的顶点数量。 如果该数小于DAG中的顶点总数，则有一个循环。
https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length我喜欢这个解决scheme最好特别是4长度;:)
同时医巫师说，你必须做O（V ^ 2）。 我相信我们只需要O（V）/ O（V + E）。 如果graphics连接，则DFS将访问所有节点。 如果graphics已经连接了子图，那么每当我们在这个子图的一个顶点上运行一个DFS时，我们就会发现连接的顶点，而不必考虑这些用于DFS的下一次运行。 因此，为每个顶点运行的可能性是不正确的。
正如你所说，你有一套工作，它需要按一定的顺序执行。 给定您需要sorting的工作（如果是direct acyclic graph则为依赖关系问题）的Topological sort 。 运行dfs并维护一个列表，然后开始在列表的开头添加节点，如果遇到已经访问过的节点。 然后你在给定的图中find一个循环。
//this is better solution in java- ` class Package{ private List<Package> dep; private String name; boolean visited; List<Package> getDependencies(){ return this.dep; } String getName(){} public void getBuildOrder(Package p){ p.visited=true; if(p.getDependencies.size()==0) syso(p.getName()); for( Package p1 : p.getDependencies){ if(p1.visited) { syso("cyclic dependency"); return; } getBuildOrder(p1); } } main(){ Package p = new Package(); // this pi having all infor getBuildOrder(p); } } `
如果图表满足这个属性
|e| > |v| - 1
那么该图至less包含一个循环。
