I want to know which algorithm find all cycles in a **undirected graph**. For directed graph we have 'Johnson’s algorithm **but what about undirected graph** Or you can share your approach to do this. I search it on *stackoverflow* but I didn’t find anything.

Please Help me out.

2 Likes

This answer is from Quora :

Use dfs to find cycles in a graph as it saves memory.

Maintain the dfs stack that stores the “under processing nodes (gray color)” in the stack and -

just keep track when a visited node is tried to be accessed by a new node.

. Get the node which was already visited but was tried to be accessed.

. Find the position in stack.(as the stack has visited nodes)

right from this position move up till top of the stack , you will get the cycle in cyclic order.

You may miss some sub cycles (cycles inside cycle) but you will never miss any disjoint cycle.

(So you have a solution in case the graph has disjoint cycles).

1 Like