Best algorithm for detecting cycles in a directed graph
What is the most efficient algorithm for detecting all cycles within a directed graph?
I have a directed graph representing a schedule of jobs that need to be executed, a job being a node and a dependency being an edge. I need to detect the error case of a cycle within this graph leading to cyclic dependencies.
Tarjan's strongly connected components algorithm has O(|E| + |V|) time complexity.
For other algorithms, see Strongly connected components on Wikipedia.
Given that this is a schedule of jobs, I suspect that at some point you are going to sort them into a proposed order of execution.
If that's the case, then a topological sort implementation may in any case detect cycles. UNIX tsort certainly does. I think it is likely that it is therefore more efficient to detect cycles at the same time as tsorting, rather than in a separate step.
So the question might become, "how do I most efficiently tsort", rather than "how do I most efficiently detect loops". To which the answer is probably "use a library", but failing that the following Wikipedia article:
http://en.wikipedia.org/wiki/Topological_sorting
has the pseudo-code for one algorithm, and a brief description of another from Tarjan. Both have O(|V| + |E|) time complexity.
Start with a DFS: a cycle exists if and only if a back-edge is discovered during DFS. This is proved as a result of white-path theorum.
链接地址: http://www.djcxy.com/p/70680.html上一篇: 在Google Appengine数据存储中存储有向图
下一篇: 在有向图中检测周期的最佳算法