# Detect cycles in graph [duplicate]

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

-

## marked as duplicate by kotlinski, Jeremiah Willcock, marcog, belisarius, bmarguliesMar 2 '11 at 3:05

I think question there, although mared as "answered" it is not answered correctly. –  CygnusX1 Mar 1 '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 –  belisarius Mar 1 '11 at 22:22

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.

-
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 3 '12 at 12:16
The text passage is about detecting cycles in a graph and provides a mathematical algorithm for doing so. It also includes a comment on the potential large number of cycles that can be found.
no_question

the passage does not contain a direct mathematical question that requires a numerical or calculative answer. it provides an algorithm and a warning about the number of cycles, but these are not framed as questions.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Detect cycles in graph [duplicate]

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

-

## marked as duplicate by kotlinski, Jeremiah Willcock, marcog, belisarius, bmarguliesMar 2 '11 at 3:05

I think question there, although mared as "answered" it is not answered correctly. –  CygnusX1 Mar 1 '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 –  belisarius Mar 1 '11 at 22:22

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.

-
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 3 '12 at 12:16
user
The text passage is about detecting cycles in a graph and provides a mathematical algorithm for doing so. It also includes a comment on the potential large number of cycles that can be found.

TYPE: NO_QUESTION

The passage does not contain a direct mathematical question that requires a numerical or calculative answer. It provides an algorithm and a warning about the number of cycles, but these are not framed as questions.