Algorithm that returns the path of one cylce in undirected graph

Question

I am trying to construct an algorithm that returns the nodes of a path that make up ONE cycle in an undirected graph (if there is one). What I have so far is performing DFS on the graph until I reach an undiscovered edge leading to a discovered node (at that point I know there is a cycle). But how do I know which path made the cycle. If I use a stack/queue to record my path, how does that help me? Say I start from a node which is not part of the path of a cycle, how would I later know to take it out of the stack/queue?

Any suggestions would be much appreciated.

Answer 1

When you perform the DFS record which is the node you came from when you visited each node. Call this parent for the new node. Now when you reach an edge (u, v) that leads to an already visited node v, walk up the path made by the parents up to u, or up to the source of the DFS (denote this s).

You will always reach one of the two. If you reach s, than perform the same from v and you have your cycle - the path from u to s the path from s to v and the new edge. If you reach v you again have a cycle - the path from u to v and than the new edge.