deepak2015's blog

Graph
By deepak2015, 10 years ago, In English

How to find length of cycle in undirected graph?

1 -------2-------3 

|       |

     |       |

     4-------5

Here nodes 2,3,4 and 5 form cycle, so length of cycle is 4. Plz provide an algorithm to find length of cycle. I am unable to reach a solution for it.

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

which cycle the minimum cycle the maximum cycle which of them (the second is np because hamiltonian cycle is np)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I want length of just a cycle being formed. Like in above eg 2,3,4 and 5 form cycle. 1 does not form part of cycle. However, diagram is not clear but I suppose u would guess it. So plz help in finding length of the cycle.

    → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

If you need a length of any of the cycles you can use DFS. You can also use BFS but in my opinion with DFS its easier and faster to write. If you are not familiar with BFS and DFS look at:

http://en.wikipedia.org/wiki/Breadth-first_search http://en.wikipedia.org/wiki/Depth-first_search

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How can one find length of cycle using DFS. We can check if there is a cycle or not usinfg DFS but not the entire length like in above eg. Plz elaborate how can one find length of cycle using DFS. A proper code would be helpful.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ok.

      I wrote a code about how to find those cycles. (link). My idea is simply to maintain a "used" array where I save the length from the "start" to the current vertex "u". If there is an adj. vertex "v" such that it is ancestor of "u" then there is a cycle and its length is the length to "u-v".

      → Reply