| 生成有向图中全部简单回路的一种新算法 |
| |
| 引用本文： | 王玉英,陈平,苏旸.生成有向图中全部简单回路的一种新算法[J].陕西师范大学学报,2008,36(4). |
| |
| 作者姓名： | 王玉英 陈平 苏旸 |
| |
| 作者单位： | [1]西安建筑科技大学理学院,陕西西安710055 [2]西安电子科技大学软件工程研究所,陕西西安710071 |
| |
| 基金项目： | 国家自然科学基金资助项目
,
教育部博士点基金资助项目 |
| |
| 摘 要： | 提出了生成有向图中全部简单回路的一种新算法.算法的主要思想是对图中顶点进行缩减,在缩减过程中巧妙地利用字符串标记保存图中原有信息,不断减少图中顶点的数量,最终将图缩为一点,逐步得到全部简单回路.这种缩减过程隐藏在矩阵运算中,在运算中不断简化矩阵,从而降低了运算复杂度,提高运算效率.此算法生成的回路中不包含重复的回路,算法结构清晰,易转化为计算机程序.文中给出了算法的详细证明和实例应用.
|
| 关 键 词： | 有向图 简单有向回路 算法 矩阵运算 |
A new algorithm to find all elementary circuits of a directed graph |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
