Can I use just a simple Set for cycle detection in directed graph?

Question

I have seen quite a lot of algorithms to do cycle detection, such as Tarjan's strongly connected components algorithm answered in Best algorithm for detecting cycles in a directed graph.

I never thought detecting a cycle would be that complicated and I always believed a simple Set can help solve the problem.

So in addition to the usual marker array for recording visited vertices, we can use an additional Set to record all vertices along a path from the source.

The key thing is to remember to remove a vertex from the set after all its next neighbours are done.

A trivial code is like this:

public boolean hasCycle(List<Integer>[] vs) {
  boolean[] marker = new boolean[v.length];
  Set<Integer> tracker = new HashSet<Integer>();

  for(int v = 0;v < vs.length;v++)
    if (explore(v, vs, marker, tracker)) return true;

  return false;
}

private boolean explore(int v, List<Integer>[] vs, boolean[] marker, Set<Integer> tracker) {
  if (tracker.contains(v)) return true;
  else if (!marker[v]) {
    marker[v] = true;
    tracker.add(v); // add current vertex to tracker
    for (int u:vs[v]) if (explore(v, vs, marker, tracker)) return true;
    tracker.remove(v); // remove the vertex from tracker, as it is fully done.
  }
  else return false;
}

Is there any problem about this algorithm?

With help from sasha's answer, actually even the set is not necessary and just an array is enough.

public boolean hasCycle(List<Integer>[] vs) {
  boolean[] marker = new boolean[v.length];
  boolean[] onPath = new boolean[v.length];

  for(int v = 0;v < vs.length;v++)
    if (explore(v, vs, marker, onPath)) return true;

  return false;
}

private boolean explore(int v, List<Integer>[] vs, boolean[] marker, boolean[] onPath) {
  if (onPath[v]) return true;
  else if (!marker[v]) {
    marker[v] = true;
    onPath[v] = true; // add current vertex to the path
    for (int u:vs[v]) if (explore(v, vs, marker, onPath)) return true;
    onPath[v] = false; // remove the vertex from the path, as it is fully done.
  }
  else return false;
}

You're right, simple DFS is enough to detect cycles in a graph, in precisely the way you do it: Check for back-edges. Tarjan's algorithm actually computes something more complicated — Niklas B., Feb 05 '15 at 22:34
Each cycle induces a back-edge in the depth-first tree, which is what you're checking for. Looks good to me, but of course there might be subtle implementation bugs that I overlooked. — Niklas B., Feb 05 '15 at 22:35
Instead of using two arrays, some people prefer to use an array of bytes and use 3 different values to encode the states not visited/on the root path/visited. That would be even more space efficient. — Niklas B., Feb 06 '15 at 11:40
@JacksonTale Well that depends. `boolean` takes 1 byte, so it's kind of a waste because 1 byte can actually store 256 different values, not just 2. Of course if you would use a proper bitvector, 2 bits per node is close to optimal — Niklas B., Feb 06 '15 at 21:15

score 2 · Accepted Answer · answered Feb 05 '15 at 23:05

I am not an expert in java but talking about C++ passing set etc in recursion is not time efficient. Also set takes O(log(n)) in inserting/deleting an element. Your logic looks correct to me. But you can do it more efficiently and easily by keeping two arrays parent[] and visited[]. Basically do a bfs and following is the pseudo code ( visited is initialized to all zeros ) .

   /* There are n nodes from 0 to n-1 */
   visited[0]=1
   parent[0]=0
   flag=0
   queue.push(0)
   while the queue is not empty
       top = queue.front()
       queue.pop()
       for all neighbors x of top
           if not visited[top]
              visited[x]=1
              parent[x]=top
              queue.push(x)
           else if visited[x] is 1 and parent[top] is not x
                flag = 1

   if flag is 1 cycle is there otherwise not

As it may not be necessary that starting from 0 all nodes are visited . So repeat until all nodes are visited. Complexity is O(E+V) slightly better than the complexity of your method O(E+VlogV). But it is simple to write and not recursive.

Hi thanks for the answer. HashSet in Java is O(1) op as it doesn't use a tree. However you are right that set not necessary as a simple array is enough — Jackson Tale, Feb 05 '15 at 23:08
The advantage of using DFS over BFS is that the call stack will contain the nodes of the cycle, which is not the case for BFS. — Niklas B., Feb 06 '15 at 11:39

Can I use just a simple Set for cycle detection in directed graph?

1 Answers1