How to detect cycle using itarative approach

Question

I am trying to learn how to detect cycle. I see many example of using recursion but I want to implement in iterative way. Here is my code

public boolean cycleDetection(int[][] edges, int source ) {
     Map<Integer, List<Integer>> graph = new HashMap();
        for (int[] edge : edges) {
            graph.putIfAbsent(edge[0], new ArrayList());
            graph.get(edge[0]).add(edge[1]);
        }
        Stack<Integer> stack = new Stack();
        Set<Integer> visited = new HashSet();
        
        stack.push(source);
        visited.add(source);
        while(!stack.isEmpty()) {
            int curr = stack.pop();
            visited.add(curr);
            if(graph.containsKey(curr)) {
                for(int i :  graph.get(curr)) {
                    
                    if(visited.contains(i)) {
                        return true;
                    }
                    stack.push(i);
                }
            }
            
        }
    return false;
}

It does not work as expected

    int[][] vertex = { {0 , 1 }, {0,3}, {1,2},{2,1} }; // Has Cycle
    int[][] vertex = { {0 , 1 }, {0,2}, {1,3},{2,3} }; // No Cycle

what logic I am missing here?

Answer 1

The problem is you are also detecting cross edges.

In your example, order of discovery (in example 2) is:

0 -> 1 -> 3 -> 2 -> 3

Now, when you see 3 for the second time - you notice it was already visited - and say there is a cycle. However, this is a cross edge - you found it, but through a different branch, and in fact this is not a cycle.

One solution (with minimal modification of code) - though might not be optimal, is to remove a node from the visited once you've finished exploring it.

Why does it work?

• If there is a cycle - you will discover it because node was not removed from the visited until you rediscovered it. Algorithm will end once you discovered it.
• If there is no cycle - you will exhaust a path, and remove all its nodes from visited. Since there are no cycles, the algorithm will "run out" of options and terminate eventually.

Implementing might be a bit tricky in iterative code version of DFS (as you want to mimic doing it "once you are back from recursion"), but should be possible. Good luck!