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

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

StackExchange Code Review Q#27776, answer score: 2