生成有向图中全部简单回路的一种新算法

• 作者: 王玉英 苏旸 陈平
• 来源期刊: 陕西师范大学学报（自然科学版）
• 学科: 工学
• 关键词: 有向图 简单有向回路 算法 矩阵运算
• 年，卷（期）: 2008,（4）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 12-15
• 页数: 4页
• 分类号: O157.6|TP311.12
• 字数: 3396字
• 语种: 中文

摘要

提出了生成有向图中全部简单回路的一种新算法.算法的主要思想是对图中顶点进行缩减,在缩减过程中巧妙地利用字符串标记保存图中原有信息,不断减少图中顶点的数量,最终将图缩为一点,逐步得到全部简单回路.这种缩减过程隐藏在矩阵运算中,在运算中不断简化矩阵,从而降低了运算复杂度,提高运算效率.此算法生成的回路中不包含重复的回路,算法结构清晰,易转化为计算机程序.文中给出了算法的详细证明和实例应用.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	苏旸	西安电子科技大学软件工程研究所	8	35	4.0	5.0
2	陈平	西安电子科技大学软件工程研究所	149	1211	17.0	28.0
3	王玉英	西安建筑科技大学理学院	10	56	5.0	7.0