Java cycle detection using DFS in an undirected graph

Question

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;
 edge[edgeNum]==true; // already explored edge wont' lead to cycle.
 List nodes = getAllNeigbors(n); //visited or unvisited
 boolean isCycle = false;
 for(Node node : nodes){ 
 isCycle = isCycle || isCycled(node, getEdgeNum(n,node)); 
 }
 return isCycle;
}

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

Answer 1

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); 
}