4
\$\begingroup\$

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

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);         
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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