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

A new algorithm to find all elementary circuits of a directed graph

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

A new algorithm for creating all elementary circuits of a direct graph is proposed. The main idea of this algorithm is to remove vertices from the graph one by one and to find elementary circuits. When the graph is shrunk to a point, all elementary circuits are found. During this process, the related matrices are simplified gradually and some strings are used to save the information about the original graph, which makes the algorithm complexity reduce and increases its efficiency. All elementary circuits obtained are not reduplicate. It is convenient to transform this algorithm to computer program. The proof of this algorithm and its application are given.