作者:舒新峰; 马青吉有向图简单回路深度优先遍历
摘要:给出一种计算有向图所有简单回路的新算法,以降低计算时间复杂度。采用深度优先遍历策略,遍历时借助堆栈来保存遍历起点到当前遍历位置的简单路径,遇到访问过的顶点,则计算该顶点与堆栈中简单路径直接构成的简单回路,或者计算该顶点与已找到的简单回路间接形成的简单回路,经过一次遍历计算出有向图中所有的简单回路。性能分析和实验结果表明,所给算法和Johnson算法相比时间复杂度和计算时间明显降低,可高效计算出有向图中所有的简单回路。
注:因版权方要求,不能公开全文,如需全文,请咨询杂志社