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.
1 Like
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).