☕ DSA Java Articles

Topics › Graphs › Problems on BFS/DFS

Detect A cycle in Undirected Graph using DFS

Hard TUF ID 2819 SDE

Java source ↗ Edit this article ↗

Problem

You are given an undirected graph with V vertices numbered 0 to V - 1 as an adjacency list: adj.get(u) holds every neighbour of u, so an edge u - v is stored twice. Return true if the graph contains a cycle, meaning a closed route that comes back to its starting vertex without reusing an edge. The graph can have several components. Use depth-first search.

Assume a simple graph (no self-loops, no repeated edges); the pitfalls section covers the other case.

Constraints: 1 ≤ V ≤ 10^5, 0 ≤ E ≤ 10^5.

Example 1

V = 5, edges: 0-1, 1-2, 2-3, 3-4, 4-1
answer = true        // 1 - 2 - 3 - 4 - 1

Example 2

V = 4, edges: 0-1, 1-2, 2-3
answer = false       // a simple path

As with every undirected cycle question, the trap is the reverse copy of each edge. When DFS goes from 0 into 1, vertex 1 immediately sees 0 in its own list, and 0 is visited. That is not a cycle; it is the edge we just used. A correct method must ignore exactly that one step back and nothing else.

Approach 1: Brute force, does each edge have a detour?

Intuition. Pick an edge u - v and pretend it is gone. If v can still be reached from u, the detour together with the edge forms a cycle. If it cannot, the edge is a bridge and lies on no cycle. A graph has a cycle exactly when some edge has a detour. The test is a recursive DFS from u that is forbidden to cross the chosen edge.

Algorithm.

  1. For every pair u < v with v in adj.get(u) (each edge once):
  2. DFS from u, never stepping along u - v in either direction, with a fresh seen array.
  3. If the DFS reaches v, return true.
  4. Otherwise return false after all edges.
static boolean bruteForce(int V, List<List<Integer>> adj) {
    for (int u = 0; u < V; u++) {
        for (int v : adj.get(u)) {
            if (u < v && reach(adj, u, u, v, new boolean[V])) return true;
        }
    }
    return false;
}

/** Recursive DFS from x looking for v, never using the edge u-v. */
static boolean reach(List<List<Integer>> adj, int x, int u, int v, boolean[] seen) {
    if (x == v) return true;
    seen[x] = true;
    for (int y : adj.get(x)) {
        if ((x == u && y == v) || (x == v && y == u)) continue;   // the removed edge
        if (!seen[y] && reach(adj, y, u, v, seen)) return true;
    }
    return false;
}

Complexity. Time O(E · (V + E)), a full search per edge. Space O(V) for seen and the recursion stack.

This repeats almost the same search E times. One DFS over each component carries enough information to answer directly.

Approach 2: Optimal, recursive DFS with the parent passed down

Intuition. In a DFS, the edges along which new vertices are discovered form a DFS tree. Undirected DFS has a special property: every non-tree edge connects a vertex to one of its ancestors (a “back edge”); there are no cross edges between separate branches. That is because DFS fully explores everything reachable from a vertex before returning, so if x and y were adjacent and neither was an ancestor of the other, whichever was visited first would have discovered the other through that edge.

A back edge from x to an ancestor a closes the cycle a -> ... -> x -> a along the tree path. So the rule is: when DFS at x meets an already visited neighbour y, it is a cycle unless y is the parent we just came from. Passing the parent as an argument makes that check trivial.

Algorithm.

  1. For each vertex not yet visited, call dfs(s, -1).
  2. dfs(x, parent): mark x visited; for each neighbour y:
    • if y is unvisited, recurse with dfs(y, x) and propagate a true;
    • else if y != parent, return true (back edge).
  3. Return false if no call found a back edge.
static boolean optimal(int V, List<List<Integer>> adj) {
    boolean[] visited = new boolean[V];
    for (int s = 0; s < V; s++) {
        if (!visited[s] && dfs(adj, s, -1, visited)) return true;
    }
    return false;
}

static boolean dfs(List<List<Integer>> adj, int x, int parent, boolean[] visited) {
    visited[x] = true;
    for (int y : adj.get(x)) {
        if (!visited[y]) {
            if (dfs(adj, y, x, visited)) return true;
        } else if (y != parent) {
            return true;                              // back edge to an ancestor
        }
    }
    return false;
}

Dry run on example 1. The edges were added in the listed order, so adj[1] = [0, 2, 4], adj[2] = [1, 3], adj[3] = [2, 4], adj[4] = [3, 1].

call neighbour visited? parent result
dfs(0, -1) 1 no -1 recurse
dfs(1, 0) 0 yes 0 parent, skip
dfs(1, 0) 2 no 0 recurse
dfs(2, 1) 1 yes 1 parent, skip
dfs(2, 1) 3 no 1 recurse
dfs(3, 2) 2 yes 2 parent, skip
dfs(3, 2) 4 no 2 recurse
dfs(4, 3) 3 yes 3 parent, skip
dfs(4, 3) 1 yes 3 1 is an ancestor, not the parent: true

The tree path 1 -> 2 -> 3 -> 4 plus the back edge 4 - 1 is the cycle.

Complexity. Time O(V + E): each vertex is entered once and each adjacency entry is examined once. Space O(V) for visited and the recursion depth.

Approach 3: Optimal, iterative DFS with an explicit stack

Intuition. Approach 2 can recurse as deep as the longest path in the graph. A path of 10^5 vertices means 10^5 nested calls, which can overflow Java’s default thread stack. The fix is to keep the recursion on a heap-allocated stack. To behave exactly like the recursive version, each vertex on the stack needs to remember how far through its neighbour list it has got; the array next[x] plays the role of the loop variable inside the recursive call.

At every step we look at the top vertex x. If it still has an unexplored neighbour y, we advance next[x] and handle y exactly as before: unvisited means “push it”, which is the recursive call; visited and not the parent means a back edge. If x has no neighbours left, it is finished and we pop it, which is the return from the recursive call.

Algorithm.

  1. For each unvisited vertex s: mark it, set parent[s] = -1, push it.
  2. While the stack is not empty, let x be the top.
    • If next[x] has reached the end of adj.get(x), pop x.
    • Otherwise take y = adj.get(x).get(next[x]++). If y is unvisited, mark it, set parent[y] = x, push it. Else if y != parent[x], return true.
  3. Return false.
static boolean optimalIterative(int V, List<List<Integer>> adj) {
    boolean[] visited = new boolean[V];
    int[] parent = new int[V];
    int[] next = new int[V];                          // next[x] = index of the next neighbour of x to try
    Deque<Integer> stack = new ArrayDeque<>();
    for (int s = 0; s < V; s++) {
        if (visited[s]) continue;
        visited[s] = true;
        parent[s] = -1;
        stack.push(s);
        while (!stack.isEmpty()) {
            int x = stack.peek();
            if (next[x] == adj.get(x).size()) {       // every neighbour handled: x is finished
                stack.pop();
                continue;
            }
            int y = adj.get(x).get(next[x]++);
            if (!visited[y]) {
                visited[y] = true;
                parent[y] = x;
                stack.push(y);                        // go deeper, exactly like the recursive call
            } else if (y != parent[x]) {
                return true;
            }
        }
    }
    return false;
}

Complexity. Time O(V + E), the same visits as the recursive version. Space O(V) for the arrays and the stack, all on the heap. The Java tests run it on a path and on a ring of 100000 vertices.

Edge cases and pitfalls