I
I
inek2021-07-03 21:33:45
Algorithms
inek, 2021-07-03 21:33:45

Is there an efficient algorithm for finding all elementary cycles in an undirected graph?

Hello, I
'm interested in the question:
is there (is it known) now an effective algorithm for finding all elementary (without repeating vertices) cycles in an undirected graph, implemented in any programming languages, including, of course, Hamiltonian ones, if any? An interesting fact is the existence of such an algorithm, the implementation is not required, but with a positive answer, if possible, I ask you to write about what was actually implemented somewhere, and not about what "theoretically can be implemented" and provide a description of the algorithm or a link to a description or source . Also, if known, then indicate the dimension of the problem being solved or that it is solved for the general case (of course, for the variant with finite time).
Thanks to everyone who showed interest!

Answer the question

In order to leave comments, you need to log in

1 answer(s)
W
Wataru, 2021-07-03
@inek18

What do you mean by "efficient"?
The problem is that cycles in a graph of n vertices can be O(n!) (n-factorial): imagine a clique - a graph where there are edges between all pairs of vertices. Any subset of vertices, and even in any order, defines an elementary cycle.
Usually, the word "efficient" means a polynomial algorithm. Such an algorithm obviously does not exist here (because it is necessary to iterate over an exponential number of objects).
Use a depth-first search without remembering the vertices you have traveled. Such an exhaustive search is guaranteed to find all cycles. You can speed it up if you first divide the graph into doubly connected components by bridges and look for cycles inside each component separately.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question