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

摘要：

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

关键词：有向图、简单回路、深度优先遍历

所属期刊栏目：23

分类号：TP311(计算技术、计算机技术)

资助基金：陕西省工业科技攻关项目2017GY-076

在线出版日期：2018-08-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：85-91