WANG Yu-ying1,2 ,CHEN Pin2, SU Yang2
(1 College of Science, Xi′an University of Architecture and Technology, Xi′an 710055, Shaanxi China; 2 Software Engineering Institute, Xidian University, Xi′an 710071, Shaanxi China)
Abstract:
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.
KeyWords:
directed graph； elementary directed circuit； algorithm; matrix operation
