How to determine the length of the shortest cycle in an undirected graph?

Question

Counts

Hello. There is an undirected graph represented as an adjacency matrix. Using depth-first search, you need to find the length of the shortest cycle in it. I studied the bypass in depth, but I, unfortunately, have no idea how to solve just such a problem. I ask for your help. Couldn't google anything good. Implementation is required in C/C++, preferably using the vector library

Answer 1

Well, since a depth-first search is needed, then run a complete enumeration from each vertex and look for ways back to the same vertex.
To do this, you will need to mark the vertices as passed when entering, and unmark them when exiting. In the traversal itself, iterate over all edges and recursively start from vertices not yet traversed. If you see an edge to the first vertex, you have found a cycle, save the current depth in response if it is better than the one found so far.
To speed up, you can: Do not go recursively deeper than the current answer. Mark vertices not just with the visited/not visited mark, but with the depth of the recursive call. Then, if there is an edge to the already bypassed vertex, you have found some cycle with some length (the current depth is the depth of the second vertex + 1). It can immediately be taken as a possible answer. If the graph is connected, then you can only start from one vertex, or you can start from one vertex in each connected component.
But it will still run for exponential complexity.
Another problem - to check if there is any cycle in the graph - is solved by a depth-first search for linear complexity.