检测有向图中循环的最佳算法 [英] 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 strong连通分量算法具有O(|E| + |V|)时间复杂度.

有关其他算法，请参阅维基百科上的强连通分量.

For other algorithms, see Strongly connected components on Wikipedia.

这篇关于检测有向图中循环的最佳算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！