Big O complexity of finding cycles in an Undirected graph

Question

Hello!

I need to find the complexity of finding all the cycles in a undirected graph consisting of 50 nodes. Moreover, if the graph grows large, will the complexity be changed and what will be it if the network grows considerably large. In addition, if I find only few cycles then how do I find the complexity of finding few cycles in a graph.

Thanking you in Anticipation!

Answer 1

Using depth-first search and proactive marking of nodes, you can find cycles simply by noticing any time that you run into a marked node in your search.

This is an O(V+E) approach, I believe, where V is the number of vertices or nodes and E is the number of edges or connections.

If you put the nodes in a particular branch on a stack, you can also easily determine the cycle path. Just make sure to pop a node out each time you backtrack.

Answer 2

A given graph can have exponential number of cycles (in the size of graph). Consider a bipartite graph where v_i is connected to w_{i+1 % n} and w_i is connected to v_i+1%n.

So unless you have specific kind of graphs, there is no hope for polynomial time solutions. A solution that runs in exponential time is very easy to build. Consider all permutations of vertices, see if that ordering results in a cycle.

Of course, in practical terms you can come up with solutions that are much faster than that.