2

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!

Nicolas
  • 24,509
  • 5
  • 60
  • 66
Hassu
  • 21
  • 1
  • 2
  • 5
    If you know ahead of time that there are 50 nodes, then the complexity is O(1), since it requires only constant time to find all the cycles. TSP is constant-time too. :-) It is only when the size of the graph (or other input) is unbounded that the algorithmic complexity becomes an issue, and that complexity will not be changed as the graph grows larger, because it doesn't depend on the size of the input. The complexity only changes if you change algorithms. – Jeffrey L Whitledge Oct 06 '10 at 15:06
  • Thanks for the answer. Actually I have an algorithm in which a sink node finds few cycles in an undirected graph by computing message paths or node ID's of all the nodes in the graph. For example, in a graph in which 10 cycles of different size are present, it finds only first five of them, So in that case what would be the complexity of the algorithm. – Hassu Oct 06 '10 at 15:28
  • possible duplicate of http://stackoverflow.com/questions/526331/cycles-in-an-undirected-graph – Damian Schenkelman Oct 25 '10 at 00:53

2 Answers2

0

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.

Platinum Azure
  • 45,269
  • 12
  • 110
  • 134
0

A given graph can have exponential number of cycles (in the size of graph). Consider a bipartite graph where vi is connected to wi+1 % n and wi is connected to vi+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.

outis
  • 75,655
  • 22
  • 151
  • 221
user485440
  • 170
  • 5