Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

(I asked the same question in stackoverflow, but thought that this website might be the another good place to ask this.)

I want an algorithm that gives one instance of a cycle in a directed graph if there is any. Can anyone show me a direction maybe in pseudo-code?

I implemented Kahn's (1962) algorithm in Ruby that detects if a graph has a cycle, but I want to know not only whether it has a cycle, but also one possible instance of such cycle.

example_graph = [[1, 2], [2, 3], [3, 4], [3, 5], [3, 6], [6, 2]]

Kahn's algorithm

def cyclic?(graph)
  ## The set of edges that has not been examined
  graph = graph.dup
  n, m = graph.transpose
  ## The set of nodes that are the supremum in the graph
  sup = (n - m).uniq
  while sup_old = sup.pop do
    sup_old ={|n, _| n == sup_old}
    graph -= sup_old
    sup_old.each {|_, ssup| sup.push(ssup) unless graph.any?{|_, n| n == ssup}}

The above algorithm tells whether a graph has a cycle:

cyclic?(example_graph) #=> true

but I want not only that but an example of a cycle like this:

#=> [[2, 3], [3, 6], [6, 2]]

If I were to output the variable graph of the above code at the end of examination, it will give:

#=> [[2, 3], [3, 4], [3, 5], [3, 6], [6, 2]]

which includes the cycle I want, but it also includes extra edges that are irrelevant to the cycle.

share|cite|improve this question
up vote 2 down vote accepted

Use Tarjan's algorithm to look for strongly connected components. When you find a component with more than one node in it, it will be defined by one or more edges in the depth-first tree; such a back edge together with a path from one end to another in the depth-first tree is a cycle.

share|cite|improve this answer
Thanks. This seems to be the best way to do it. – sawa Mar 16 '12 at 1:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.