patternMinor
Graph find all vertices that are part of a cycle
Viewed 0 times
cyclegraphallarepartthatfindvertices
Problem
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!
Thanks for your help!
Solution
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.
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.
Context
StackExchange Computer Science Q#92827, answer score: 3
Revisions (0)
No revisions yet.