求有向与无向图中固定长度L的所有简单环的算法

有向图场景 #

改造Johnson算法适配固定长度 #

Johnson算法原本用于枚举所有简单环，针对固定长度L的需求，可以在遍历过程中加入长度剪枝：

• 遍历每个节点作为起点，维护当前路径的节点集合和已走步数；
• 每扩展一个节点，步数+1，若步数超过L则直接终止当前分支；
• 当步数恰好等于L时，检查当前节点是否有指向起点的边，且路径中无重复节点，符合条件则记录为有效环。

动态规划+状态追踪方案 #

用DP[u][k]记录所有从起点s出发，经过k步到达节点u的简单路径集合：

• 初始化：DP[s][1] = [[s]]（仅包含起点自身的路径）；
• 递推：对每个步数k从2到L，遍历所有节点u，将DP[v][k-1]中所有不包含u的路径末尾添加u，存入DP[u][k]；
• 收集结果：当k=L时，遍历所有DP[u][L]中的路径，若u存在指向s的边，则该路径+s构成一个长度为L的简单环。
  这种方案天然支持增量式输出，每完成一个步数k的计算，就可以同步检查并输出符合条件的环，无需等待全部计算完成。

无向图场景 #

无向图的核心是避免重复环（如A-B-C-A和A-C-B-A视为同一个环），同时禁止路径中出现重复节点：

带起点约束的DFS剪枝 #

• 仅选择编号最小的节点作为环的起点（避免重复枚举）；
• 从起点s出发进行DFS，维护当前路径和已走步数，遍历过程中禁止返回上一个节点（避免来回走）；
• 当步数等于L时，检查当前节点是否与s相邻，且路径中无重复节点，符合则记录环；步数超过L则终止当前分支。

适配无向图的DP方案 #

类似有向图的DP思路，但需额外处理无向边的重复问题：

• DP[u][k]记录从起点s出发，经过k步到达u且不包含前一个节点的简单路径；
• 递推时，仅从DP[v][k-1]中选择不包含u且最后一个节点不是u的路径，添加u后存入DP[u][k]；
• 当k=L时，若u与s相邻，则路径+s构成有效环，且由于起点约束，不会出现重复环。

增量式优化要点 #

• 实时输出：在遍历/递推过程中，一旦找到符合长度L的环，立即记录或输出，无需等待所有分支处理完毕；
• 严格剪枝：路径中出现重复节点、步数超过L时直接终止当前分支，减少无效计算；
• 分批处理：针对大图，可按节点分组处理（如每次处理100个起点），处理完一组就输出结果，避免内存溢出和长时间无响应。

内容的提问来源于stack exchange，提问作者oneWayC