0

I have a question, which algorithm could I use to find a circle in a graph G=(V,E,w). I know there is a solution by running the improved DFS algorithm on G and then run on every edge and check this condition:

Defining edge like: e = (x, y) where x point to y.

if(low[y] <= d[x])
   e is inside a circle

I am not quite sure if this is the solution, someone can help me figure this out?

Thank you !

lennon310
  • 12,503
  • 11
  • 43
  • 61
Jacob
  • 3,598
  • 4
  • 35
  • 56
  • By "circle" do you mean "cycle"? If so then it's even simpler: just record in a table whether you have visited each vertex yet or not. If during DFS you discover an edge (x, y) with y already visited, you have found a cycle. If the graph is not necessarily connected then you will need to perform this for each connected component. – j_random_hacker Aug 12 '14 at 21:45
  • 1
    possible duplicate of [Detecting cycles in a graph using DFS: 2 different approaches and what's the difference](http://stackoverflow.com/questions/19113189/detecting-cycles-in-a-graph-using-dfs-2-different-approaches-and-whats-the-dif) – Herokiller Aug 13 '14 at 02:48

1 Answers1

1

You can simply use the condition you've written.

It is true because if the low[y] value is actually less then or equal to the d[x] value so surely e is an edge on a cycle which accessible from the 'back edge'.

The low[y] value is the d[u] of the minimum d[..] edges that are accessible to y via a back edge.