CODEWITHSUNDEEP
graphcycle
calccrypto
calccrypto

Reputation: 8991

How to check if an edge is in some cycle?

I have a hw problem that asks for an algorithm that detects if there is any cycle in any undirected graph that contains any given edge 'E'. The algorithm should run in O(N) linear time.

The problem I have is that I don't know where to start. I have some simple sample graphs but I dont know where to go from there.

Any hints?

Upvotes: 16

Views: 24247

Answers (5)

Japneet Singh
Japneet Singh

Reputation: 11

Run DFS on G and do the following. Consider the first time the edge e is traversed.

There are two cases:

  1. e is a backedge. In this case e is obviously part of a cycle, and the cycle can be printed.
  2. e = (a, b) is a tree edge (direction of traversal is u to v). Now start a second phase of the algorithm. For every back-edge (w, x) found in DFS, check if w is a descendant of v and x is an ancestor of u. If so, we have found a cycle including the edge e.

Upvotes: 0

urashima9616
urashima9616

Reputation: 181

Take out that edge (u,v) from G. 1. Run BFS to see if v is still reachable from u. 2. if yes, then the original graph has a cycle containing e. otherwise there is not.

Upvotes: 18

Moustafa Saleh
Moustafa Saleh

Reputation: 1

For the edge (u,v):

1- perform a depth first search starting from u, determine if v is found and a back edge exist along the path to v.

2- perform a depth first search from v, if u is found and back edge exist to u, then there's a cycle that includes both u and v.

In other words,

1- perform a DFS starting from u, check if back edge exist and v is not finished yet.

2- perform a DFS starting from v, check if back edge exist and u is not finished yet if both conditions are true, then edge(u,v) belong to a cycle.

Upvotes: 0

roartechs
roartechs

Reputation: 1355

Do a depth first search adding nodes to a list as you go, and removing them from the list as you return.

The list represents your current path of traversal.

If you come across a node that is already in your list, then there is a loop/cycle.

Upvotes: 3

James
James

Reputation: 9278

You start with the edge 'e'. From it you should get the two vertices it connects. From them you get other edges and other vertices, and other edges and other vertices, and... You'll need a way to figure out if a vertex has already been 'visited' by your algorithm. If it has then there's a cycle that 'e' is part of.

Upvotes: 1

Related Questions