7
$\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!

Improve this question
$\endgroup$
3
  • $\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, 2018 at 11:06
  • 2
    $\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, 2018 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, 2018 at 6:53

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
$\begingroup$

I just had an exam. There is the same question, we being ask to find all vertex that not part of cycle.

The function is like this (In C)

void HasCycle(int hasCycle[], int size, Graph g);

In my function, I use

  1. An array to track visit status(Using hasCycle provided).

Then I will run DFS on the vertex has not being vsisited, and in each DFS search I kept the following

  1. An array to track parent. For example, I visit 3 through edge 5->3, I will put parent[3] = 5.
  2. An array to track backedge. The authentic way should be using a timeStamp, this can be found in CLRS, chapter discuss Graph DFS search. I used color. At begin of loop, I color the vertex and at the end, I decolor the vertex so that it can be visited for multiple times. And by this, each time I have a edge conenct two colored node, means there is a back edge.
  3. A 2-D matrix, that track the status of edge. Idea is once DFS used the edge, it will be marked so won't do DFS again through that edge. In this way DFS can visit same node for several times but can't using same edge. At the end, I want to achieve, node can be visited several times but have to through different edge.

So that in the end. The time complexity will be O(V^2), for each DFS I run, it will versify the cycle in that connected component. And I will only run DFS if I havn't visit that node in previous DFS.

I am unable to proof the correctness of this algorithm. I did pass the autotest in the exam. So if there is some problem you spotted, just point it out.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Did you get a full score on this question of your exam? If you "met a back edge", what exactly will be uppdated? $\endgroup$
    – John L.
    May 9, 2022 at 5:38
  • $\begingroup$ Hey John. I have not yet get mark back yet, but after the test I realize there is a blunder in my code(Unlikely to get full mark). We were using C, and given an array "HasCycle" that all grid initilize as -1 and indicate the vertex in graph(implement by matrix). So each time I counter a back edge, I will use the array that track parent to travel back and fill HasCycle to 1. $\endgroup$
    – David Zhou
    May 9, 2022 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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