CODEWITHSUNDEEP
algorithmgraphcycledepth-first-search
Amnon
Amnon

Reputation: 325

Find all vertices in an undirected graph that belong to any cycle

Is there a way to find all vertices that are a part of a simple cycle in a graph in linear time?

I found a way to do it in O(|V|(|V|+|E|)) time but was wondering if there is a way to do it faster?

Upvotes: 8

Views: 8147

Answers (4)

Craig Gidney
Craig Gidney

Reputation: 18266

What you want to do is remove all of the bridges (i.e. edges that disconnect a component when removed). The Wikipedia article gives two algorithms for finding all of the bridges — Tarjan's algorithm and Schmidt's algorithm — both of which are linear-time.

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.

Upvotes: 12

Amnon
Amnon

Reputation: 325

Ok, I think I have the answer. while processing DFS, for every vertex v calculate low(v) (explained below). then running DFS once again and check for every vertex v:

if low(v) != d(v) (where d(v) is the distance from the DFS tree root)

vertex v is a part of a simple cycle.

*low(v) = min ( d(v),d(u),low(w)) where (v,u) is a back edge and w is a child of v in the DFS tree. calculated in O(|V|+|E|) time.

Upvotes: 0

Aravind
Aravind

Reputation: 3179

I like Bhavya's answer: but it'll help if I elaborate on it.

Usually if you do DFS you have a visited array that holds either visited/not-visited state.

Now have 

int visited[N];//N is the number of nodes/vertices in graph

Let 

visited[i] =-1 if i-th vertex is not yet visited
visited[i] = 0 if i-th vertex is being processed
visited[i] = 1 if processing of i-th vertex is done

This way if you encounter a vertex along dfs with visited value 0, it means you have a cycle.To find vertices on cycle, use a predecessor array to store previous vertex in path.

Upvotes: 0

Bhavya Madan
Bhavya Madan

Reputation: 31

Using DFS (Depth First Search), you can do in O(|V|+|E|) time. while implementing the DFS just keep the record of the vertives you had been tracking with their parent node as soon as you find child node same as parent node(meaning the completion of cycle) you can declare all the nodes from that parent till the last child as the part of some simple cycle.

Comment below if you need more explanation.

Upvotes: 3

Related Questions