我有一个有向图，我的问题是枚举该图的所有最小（不能构造为其他循环的联合的循环）有向循环。这与 Tarjan 算法的输出不同。例如，对于这个维基百科页面上的有向图，我想将 c <-> d 和 d <-> h 作为两个独立的有向循环。
我不知道这个问题是否是多项式的。我浏览了一篇论文“枚举最小 Dicuts 和强连通子图”，似乎得出的结论是这个问题是增量多项式（我不知道它是什么意思），但我无法为这篇文章提取算法。我也不确定最小强连接组件是否等同于我定义的最小循环。
有人知道这个问题的答案吗？
提前致谢！！！
如果我们正在寻找最短路径周期，这似乎很容易。
继续，直到不再有节点。
当您处理完所有节点（顶点）后，您就可以找到最小的周期……但是有一个技巧。
如果仅使用初始集合中的节点表示循环，则可以将其保持“原样”。但是您必须将“大节点”转换为路径（循环之间的公共边），并且每个大节点都可能被几个这样的路径替换（对于级别 1 的大节点至少有 2 个，即不包含大节点本身）。找到的循环以这样一种方式构造，即您可以选择任何路径并仍然获得最小循环集（没有循环可以与其他两个循环结合），但有几个可能的这样的集合。在大节点中选择路径时，您可以添加约束以始终采用最短路径，但仍然可以存在相同长度的路径。所以这个问题的解决方案显然不够独特。
使用这种简单的方法，复杂度将是 O(V.(E+V))，其中 V 是顶点数，E 是边数。O(E+V) 首先来自广度，最坏的情况是你必须执行 BFS V 次。因此它肯定是更好的多项式。我相信我所描述的在平均情况下确实是 O(log(V).(E+V))，但我还没有证明它（如果它是真的）。
也许独立循环的枚举会有所帮助？
我会尝试以下。
4.1。将图 (G) 中的每个顶点 v 变成 2（v1 和 v2），将每个顶点放在二分图 (G2) 的不同部分。
4.2. 对于 G 中的每条边 e(v,u)，添加一条从 G2 的第 1 部分到第 2 部分的边 - e(v1,u2)。
4.3. 在 G2 中找到一个最大配对。它是 G2 边的子集。
5 该子集对应于 G 中的一组最大（完整）独立循环。
我们正在寻找所有简单的周期，而不仅仅是最短或最便宜的周期。（如果简单是正确的术语——我的意思是不自相交的循环。）
这是一个应该完成工作的广度优先算法：
给节点编号。在每个节点上放置一个推销员并开始操作：如果推销员可以选择采取哪条边，他会复制自己并采取所有可能的方式。当他到达一个节点时，如果它的编号小于他开始的那个他就死了，如果是他在记录那个循环之前访问过的那个他就死了。从列表中删除冗余循环。
我不确定它的复杂性，但它看起来像 O(EV^2)。
编辑：
现在我想起来了，您可能可以从编号最小的节点上的一名推销员开始达到 O(EV)。当他的所有后代都死了时，从尚未访问的最低编号节点上的推销员重新开始。重复直到所有节点都被访问过。
这可能为时已晚，但无论如何......这个问题没有多项式解决方案，原因很简单：（di）图中可能有指数级的最小循环。
考虑n/2大小为 2 的集合，并循环排列它们：A_1, ..., A_{n/2}，并使用约定A_{n/2+1}=A_1。当且仅当它们位于一组连续索引中时，在两个顶点之间放置一条边（因此按照上述约定， inA_{n/2}中的元素也链接到 中的元素）。A_1如果您对有向图而不是简单图感兴趣，请引导边使其始终指向位于具有较大索引的集合中的顶点，或者在 和 的情况下A_{n/2}，A_1它从顶点指向 中的A_{n/2}顶点A_1。
2^{n/2}显然，在这个长度图中存在最小循环n/2，因为所有大小子集n/2都恰好包含一个顶点，A_i就是这样一个循环。如果你想用一个算法把它们全部列出来，那么这个算法必须至少有2^{n/2}几步。