0

Possible Duplicate:
Finding all cycles in graph

can anybody give me tutorial,algorithm,... for detect cycles in graph ?

i find several algorithm and implement them but doesn't detect all cycles

strongly_connected_components_algorithm

Community
  • 1
  • 1
SajjadZare
  • 2,487
  • 4
  • 38
  • 68
  • I think question there, although mared as "answered" it is not answered correctly. – CygnusX1 Mar 01 '11 at 21:23
  • @Cygn That is not a reason to allow dups. Just go there and "heat" the question by posting a comment stating that – Dr. belisarius Mar 01 '11 at 22:22
  • There is an implementation to detect all cycles in a graph in the python lib called `networkx`. **It is really simple to use!** I gave a detailed answer in the following post: http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph/33956957#33956957 – fernandosjp Oct 28 '16 at 14:18

3 Answers3

1

From more mathematical point of view:

Input: Graph G=(V,E)

  1. Assume that your graph is not disjoint (there exists a path between every two vertices)

  2. Compute the spanning tree T of the graph (there are easy algorithms to do that)

  3. Let E' be a subset of E, that don't belong to the spanning tree T. For each edge e in E', its addition to the tree creates exactly a single cycle. Let's put all those cycles into set B.

  4. We define a binary cycle space over cycles in your graph. In that space, two cycles can be added. The addition is simply an exclusive sum over the edges.

  5. The set of cycles B is a "cycle basis". Every other cycle in your graph can be formed as a linear combination of the cycles B.

This way you obtain all possible cycles in your graph.

Warning: if your input graph has v vertices and e edges then there are 2^(e - v +1)-1 different cycles! That's quite a lot - you might not want to explicitly write all of them.

CygnusX1
  • 20,968
  • 5
  • 65
  • 109
0

A BFS alg. is also ok. I believe it's easier to implement than DFS, since it keeps the visited / to-visit nodes in a queue. It's easier to check if a certain nodes has already been visited.

Andrei Duma
  • 717
  • 7
  • 10
-2

I think DFS will do your job coz we mark visited node and if we find that node again there is a cycle

ashmish2
  • 2,885
  • 8
  • 40
  • 54
  • This approach is incorrect. Take this example `1 -> 2 2 -> 3 1 -> 3` Now in this case, we do dfs(1). This will inturn will call dfs(2) and mark 2 as visited. This will call dfs(3) and mark 3 as visited. now dfs(3) will again be called from node 1, and since its already visited, you will incorrectly deduce that its a cycle – Purav Shah Apr 03 '12 at 12:16