# Java cycle detection using DFS in an undirected graph

I am doing interview studies and can't find a simple DFS for a cycle-finding algorithm. I want someone to tell me if my DFS algorithm works and how it can be improved.

Where can you get a typical DFS cycle finding algorthm for Java? I assume you have to "mark" the nodes and edges in order to find a cycle? Can you simplify / improve it? e.g. A-->B-->A , shouldn't be a cycle!

boolean isCycled(Node root){
return isCycled(root, -1);
}

boolean isCycled(Node n, int edgeNum){
//base case
if(n==null) return false;

//base case: if an unexplored edge that lead to a node that is visited.
if(edgeNum>=0){//make sure it is not the first node
if(n.visted==true && edge[edgeNum]!=true ) {
return true; //found cycle
}
}

n.visited=true;

List nodes = getAllNeigbors(n); //visited or unvisited

boolean isCycle = false;

for(Node node : nodes){
isCycle = isCycle || isCycled(node, getEdgeNum(n,node));
}

return isCycle;
}

• Why would A -> B -> A not be a cycle? Can different nodes have the same name? If so, how do you distinguish nodes? – tobias_k Jul 18 '13 at 7:44
• edge[edgeNum]==true; compilation error. I think it's a copy-paste typo. – Anirban Nag 'tintinmj' Nov 28 '13 at 10:54

There are a couple of suggestions I have here.

The first is a major performance one... you have the code:

boolean isCycle = false;
for(Node node : nodes){
isCycle = isCycle || isCycled(node, getEdgeNum(n,node));
}
return isCycle;


This should be 'short-circuited' for true conditions, and should simply be:

for(Node node : nodes){
if (isCycled(node, getEdgeNum(n,node))) {
return true;
}
}
return false;


There is no need to continue to walk the entire tree and find every cycle after yu have found one already!

The second item is more minor, and just something I would 'try'....

Instead of using the edge management, and visited tate on the nodes, I would consider using an IdentityHashMap to track what has been seen or not. Treat it like a 'stack' using put() and remove() like push and pop. That way yon can do something like:

//base case: if an unexplored edge that lead to a node that is visited.
// if(edgeNum>=0){//make sure it is not the first node
if(seenmap.contains(node)) {
return true; //found cycle
}
// }

for(Node node : nodes){
seenmap.put(node, null);
isCycle = isCycle || isCycled(node, getEdgeNum(n,node));
seenmap.remove(node);
}


If your comment about the A-->B-->A not being a cycle means that if a node points back to where it came from , it's not a cycle, then I recommend passing in the 'source' when you walk the graph... for example:

boolean isCycled(Node n, Node from, int edgeNum){


and then, your logic will look like:

for(Node node : nodes){
if (node == from) {
// this is a point-back to where we just came from in the graph)
return false;
}
seenmap.put(node, null);
isCycle = isCycle || isCycled(node, n, getEdgeNum(n,node));
seenmap.remove(node);
}