3
$\begingroup$

I was wondering how I can find all the vertices in a graph that are part of a cycle. To determine this for one vertex, I could just start a DFS from that vertex, but this seems unefficient to me when I want to know for all vertices.

Thanks for your help!

$\endgroup$
  • $\begingroup$ Finding all vertices in a graph that are part of a cycle is the same as finding all elementary cycles in a graph. This is an NP-Hard problem. A standard way of detecting cycles in a directed graph is Tarjan's algorithm. $\endgroup$ – Sagnik Jun 7 '18 at 11:06
  • 1
    $\begingroup$ @Sagnik Finding all the vertices that are on cycles is absolutely not NP-complete, unless P$\,=\,$NP. The asker gives the obvious polynomial-time algorithm. $\endgroup$ – David Richerby Jun 7 '18 at 11:23
  • $\begingroup$ @DavidRicherby it seems that I interpreted the question a bit differently than what was intended. OP asked how he could find all vertices in a graph that are part of a cycle. I thought he meant to find all vertices on all cycles of the graph. To do that you would need to find the cycles first and only then you can move onto finding the vertices. $\endgroup$ – Sagnik Jun 8 '18 at 6:53
3
$\begingroup$

There is a duplicate question in StackOverflow. I quote the highest voted answer from Craig Gidney here.

What you want to do is remove all of the Bridges (i.e. edges that disconnect a component when removed). The Wikipedia article gives a linear time algorithm for finding all of the bridges.

Once all the bridges are gone, each node is either isolated (has degree 0) or is part of a cycle. Throw out the lonely nodes, and what's left is the nodes you want.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.