一尘不染

在有向图中检测周期的最佳算法

algorithm

检测有向图内所有周期的最有效算法是什么?

我有一个有向图,表示需要执行的作业计划,作业是一个节点,而依赖项是一个边缘。我需要在此图中检测导致循环依赖性的循环的错误情况。


阅读 146

收藏
2020-07-28

共1个答案

一尘不染

Tarjan的强连接组件算法具有O(|E| + |V|)时间复杂性。

有关其他算法,请参阅Wikipedia上的强连接组件

2020-07-28