约翰逊算法为什么不是多项式呢？

Question

我读到过很多答案，说找到一个有向图中的所有圈是NP完全的，但是约翰逊的算法在O((V+E)(C+1))时间内运行(其中C是图中强连通分量的数量)，我认为这是多项式的，因为E <= V^2和C <= V变成O(V^3)，对吧？

约翰逊算法：http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

Answer 1

根据您链接的PDF，这里的数量C不是指强连接组件的数量，而是指图中简单循环的数量。换句话说，该算法列出了图中的c个简单循环中的每一个，在报告每个循环之前最多花费O(|V| + |E|)时间。由于图中不同简单循环的数量可能呈指数级增长，因此该算法在最坏的情况下将以指数时间运行。

Answer 2

这取决于你的图表。如果你的图是稀疏的，这个算法的阶数是n^2 lgn，如果你的图是密集的，n^3。总的来说，这个算法对于稀疏图是很好的。