aman_naughty's blog

By aman_naughty, history, 7 months ago, In English,

I want help please don't down-vote.

I want to print the cycle in an undirected graph. I know how to detect cycle in an undirected graph but can't determine how to find the vertices involved in the cycle. Here is the code to find cycle.

code

Can someone please tell me how to modify this so that I can get the vertices in the cycle as well.

I have seen geeksforgeeks article on printing all cycles but I can't understand it. Is there some simpler approach ?

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello! To do that you can use stack. In DFS you can push visited vertex to stack, and if there is a cycle then all elements from the top of stack (until you reach the last vertex) belong to the cycle

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

When you do dfs, you can consider vertices of 3 types; unvisited, visited but in the stack, or visited and finished (we called dfs on all their neighbors and returned already).

If your dfs detects a cycle, then all the cycle vertices are the type that's in the stack (they must have been visited, but they cannot be finished because you will find a cycle before finishing any vertex on it). So, one easy way to find the cycle is to maintain the stack along with a dfs (vector or stack, either global or passed by reference). When you find a visited neighbor, iterate from the back of the stack until you reach that visited node, and put all the vertices you iterated on in some vector, representing the cycle.

»
7 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Sorry. My answer is wrong as I got the wrong definition of a cycle.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In an undirected graph, all nodes in the same connected component are in a cycle.

    I'm not sure that's right. Consider an undirected graph that is a chain/linked list. They are all part of the same connected component, but how is there a cycle?

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are right. I kinda forgot the definition of a cycle — I had the notion of SCCs in my head when thinking of cycles. But cycles require us to find a repeating sequence of nodes. Thanks for correcting me.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this problem can define a cycle in an undirected graph for you.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it