whatever732015-03-29 17:36:06
whatever73, 2015-03-29 17:36:06

How to find all cycles in undirected graph by adjacency matrix?

Hello. There is an arbitrary adjacency matrix for an undirected graph.
How to find the number of cycles in this graph?

Answer the question

In order to leave comments, you need to log in

2 answer(s)
kreotech, 2018-02-21

In a normal function definition like this: When running a script, the browser first searches for all the definitions of the functions used. And only then starts the execution of the main script. This allows, among other things, to define all used functions after the main body of the script. You have two definitions of this type in your script. And accordingly the browser uses the last one presented. function f() {return 1;}

Boris Nagaev, 2015-04-02

Traverse the graph in depth . A stack of vertices is a route from the initial vertex to the current vertex, along which we got to it. Get a set of vertices V that you have already visited. For each vertex, remember from which vertex you came to it (dictionary P) during the traversal. If, when traversing, you see an already visited vertex K, which is not included in the current vertex stack, among the neighbors of the vertex, then "unwind" the path from K to the original vertex using information from the dictionary P, this, together with the vertex stack, will give a cycle. And if K is on the stack of vertices, then the loop will be the part of the stack from K to the top of the stack.
Addendum is off topic. There is an elegant algorithm, which for the number n determines whether the vertex is included in a cycle with repetitions of length n. But since the cycle is with repetitions, and the graph is undirected, then cycles of the form ABABA-... will also be taken into account. Apparently, you can think of a way to subtract their number from the resulting number of cycles. So I was going to do it, but then I realized that none of this was needed and the problem was solved by a simple traversal in depth.
UPD . It turned out that my answer was wrong. Correct thoughts are described in a scientific article.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question