枚举有向图的所有最小有向循环

我有一个有向图，我的问题是枚举所有minimal（不能被构造为其他循环的并集的循环）该图的有向循环。这与 Tarjan 算法的输出不同。例如，对于有向图这个维基百科页面 http://en.wikipedia.org/wiki/Strongly_connected_component，我想将 c d 和 d h 作为两个独立的有向循环。

我不知道这个问题是否是多项式。我读了一篇论文“枚举最小二切和强连通子图”，似乎得出的结论是这个问题是增量多项式（我不知道它意味着什么），但我无法为本文提取算法。我也不确定最小强连通分量是否相当于我定义的最小循环。

有人知道这个问题的答案吗？

提前致谢！！！

如果我们正在寻找最短的路径周期，这似乎很容易。

• 只需做一个广度优先搜索 http://en.wikipedia.org/wiki/Breadth-first_search在所有节点上搜索从节点到自身的最短路径。
• 如果找不到路径，可以删除这个没有循环的节点
• if you find a path, you have found one of your minimal cycles (as we looked for shortest path, we can ensure this cycle can't be the union of two shorter cycles).
  • 将其中的所有节点折叠到一个大的新节点中，并根据需要调整边缘。

• 继续下去，直到不再有节点为止。

• 当你处理完所有节点（顶点）后，你就得到了你正在寻找的最小周期......但是有一个技巧。

如果仅使用初始集中的节点来表达循环，则可以将其保持“原样”。但是你必须将“大节点”转换为路径（循环之间的公共边），并且每个大节点都可以被多个这样的路径替换（对于级别1的大节点至少有2个，即不包含大节点本身）。找到的循环的构造方式使得您可以选择任何路径，并且仍然获得最小的循环集（没有循环可以完成其他两个循环的并集），但是有几个可能的这样的集合。您可以添加约束以在大节点中选择路径时始终采用最短路径，但仍然可以存在相同长度的路径。所以这个问题的解显然不够唯一。

使用这种简单的方法，复杂度将为 O(V.(E+V))，其中 V 是顶点数，E 是边数。 O(E+V) 来自广度优先，最坏的情况是你必须执行 V 次 BFS。因此它绝对是更好的多项式。我相信我所描述的在平均情况下确实是 O(log(V).(E+V)) ，但我还没有证明它（如果它是真的）。