Detect cycle in an undirected graph using DFS

user_7141320 0
Viewed 324

I am trying to detect cycle in an undirected graph. I am using DFS to detect the same. For any node, I will visit through all connected nodes. If the child node is already visited and its not parent of current node, We have a cycle in graph.

I wrote below code :

public boolean isCyclicUtil(int current, boolean[] visited, int parent, ArrayList<ArrayList<Integer>> adj) {
    visited[current] = true;
    Iterator<Integer> it = adj.get(current).iterator();

    while (it.hasNext()) {
        int nextNode = it.next();
        if (!visited[nextNode]) {
            return isCyclicUtil(nextNode, visited, current, adj);
        } else {
            if (nextNode != parent)
                return true;
        }
    }
    return false;
}

public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
    boolean[] visited = new boolean[V];
    for (int i = 0; i < V; i++) {
        if (!visited[i] && isCyclicUtil(i, visited, -1, adj)) {
            return true;
        }
    }
    return false;
}

It is failing for certain test cases. I am not able to figure out what is wrong with the code. Please help me understand bug in my code.

breadth-first-search depth-first-search graph algorithm java
1 Answers

Instead of visiting all adjacent vertices, you stop exploring them after visiting the first adjacent vertex that has not been visited yet because of the return statement:

if (!visited[nextNode]) {
    return isCyclicUtil(nextNode, visited, current, adj);
}

Your search space from a single isCyclicUtil execution essentially becomes a path, and some vertices will not be visited. They will of course be visited in some later iteration within isCycle function, but it might be a good exercise to understand why some cycles might not be detected this way.

Fixing is easy - you want to return only if you have actually found a cycle.

user_125011370
Related