一种计算有向图中所有简单回路的高效算法

摘要

给出一种计算有向图所有简单回路的新算法,以降低计算时间复杂度.采用深度优先遍历策略,遍历时借助堆栈来保存遍历起点到当前遍历位置的简单路径,遇到访问过的顶点,则计算该顶点与堆栈中简单路径直接构成的简单回路,或者计算该顶点与已找到的简单回路间接形成的简单回路,经过一次遍历计算出有向图中所有的简单回路.性能分析和实验结果表明,所给算法和Johnson算法相比时间复杂度和计算时间明显降低,可高效计算出有向图中所有的简单回路.