Topics › Graphs › Problems on BFS/DFS

Detect A cycle in Undirected Graph using BFS

Hard TUF ID 2818 SDE

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an undirected graph with V vertices numbered 0 to V - 1 as an adjacency list: adj.get(u) lists every neighbour of u, so each edge u - v appears twice, as v in u’s list and as u in v’s list. Return true if the graph contains a cycle, that is, a closed route that returns to its starting vertex without reusing an edge (in a simple graph such a route needs at least three vertices). The graph may be disconnected. Solve it with breadth-first search.

Assume the graph is simple: no self-loops and no repeated edges. The pitfalls section says what changes when that is not true.

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 = 5, edges: 0-1, 1-2, 1-3, 3-4
answer = false       // a tree: 5 vertices, 4 edges, connected

The core difficulty is that the adjacency list stores every edge in both directions. A traversal that shouts “cycle” whenever it meets an already visited vertex would fire on every edge: after stepping 0 -> 1, vertex 1 sees 0 in its own list, and 0 is visited. Every solution below has to tell that harmless look backwards apart from a genuine second route.

Approach 1: Brute force, remove each edge and test reachability

Intuition. An edge u - v lies on a cycle exactly when u and v are still connected after that edge is deleted. If there is another route from u to v, that route plus the edge closes a loop. If deleting the edge disconnects them, no cycle can pass through it. So the graph has a cycle if and only if at least one edge passes this test, and each test is a plain BFS that refuses to walk along the deleted edge.

Algorithm.

1. For every vertex u and every neighbour v with u < v (so each undirected edge is tried once):
2. Run a BFS from u that skips the edge u - v in both directions.
3. If the BFS reaches v, return true.
4. If no edge passes, return false.

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 && reachableWithout(V, adj, u, v)) return true;
        }
    }
    return false;
}

/** BFS from u to v that is not allowed to walk along the edge u-v itself. */
static boolean reachableWithout(int V, List<List<Integer>> adj, int u, int v) {
    boolean[] seen = new boolean[V];
    Deque<Integer> queue = new ArrayDeque<>();
    seen[u] = true;
    queue.add(u);
    while (!queue.isEmpty()) {
        int x = queue.poll();
        for (int y : adj.get(x)) {
            if ((x == u && y == v) || (x == v && y == u)) continue;   // the removed edge
            if (y == v) return true;
            if (!seen[y]) {
                seen[y] = true;
                queue.add(y);
            }
        }
    }
    return false;
}

Complexity. Time O(E · (V + E)): one full BFS for each of the E edges. Space O(V) for the seen array and queue of a single BFS.

With 10^5 edges this is around 10^10 operations, far too slow. The waste is obvious: every BFS rediscovers the same structure. One BFS per component should be enough.

Approach 2: Optimal, BFS with parent tracking

Intuition. Run an ordinary BFS but remember, for each vertex, the vertex it was discovered from (its parent). Every vertex is discovered exactly once, so the edges parent[x] - x form a spanning tree of each component, the BFS tree. A tree has no cycles, so any cycle must use at least one edge that is not a tree edge.

Now look at what happens when BFS dequeues x and scans a neighbour y:

• y unvisited: this is a new tree edge. Mark y, set parent[y] = x, enqueue it.
• y visited and y == parent[x]: this is the tree edge we arrived along, seen from the other end. Ignore it.
• y visited and y != parent[x]: the edge x - y is not a tree edge. Both endpoints are already in the tree, so the tree path between them plus this edge is a cycle. Return true.

Every non-tree edge is caught this way. When its first endpoint x is dequeued, the other endpoint y must already be visited (otherwise x would have discovered it and made the edge a tree edge), and y is not x’s parent because the edge is not a tree edge. So the method reports a cycle if and only if one exists.

Algorithm.

1. For each vertex start not yet visited (each new component): mark it, set its parent to -1, enqueue it.
2. While the queue is not empty, dequeue x and scan its neighbours y with the three cases above.
3. If every component finishes without a hit, return false.

static boolean optimal(int V, List<List<Integer>> adj) {
    boolean[] visited = new boolean[V];
    int[] parent = new int[V];
    for (int start = 0; start < V; start++) {
        if (visited[start]) continue;                 // new component
        visited[start] = true;
        parent[start] = -1;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            int x = queue.poll();
            for (int y : adj.get(x)) {
                if (!visited[y]) {
                    visited[y] = true;
                    parent[y] = x;
                    queue.add(y);
                } else if (y != parent[x]) {
                    return true;                      // reached y a second way
                }
            }
        }
    }
    return false;
}

Dry run on example 1. With the edges inserted in the order listed, adj[1] = [0, 2, 4] and adj[4] = [3, 1].

Vertex 3 was reached through 1 -> 2 -> 3, and now 4 (reached through 1 -> 4) sees it too. Those two routes plus edge 3 - 4 form the cycle 1 - 2 - 3 - 4 - 1.

Complexity. Time O(V + E): each vertex is enqueued once and each adjacency entry is scanned once. Space O(V) for visited, parent and the queue.

Approach 3: Optimal alternative, count edges per component

Intuition. A different way to use the same single BFS: a connected graph on k vertices needs at least k - 1 edges, and it has exactly k - 1 precisely when it is a tree. One more edge than that always creates a cycle. So BFS each component, count its vertices k and add up the lengths of their adjacency lists. Because every edge is stored twice, half that sum is the number of edges. The component has a cycle if and only if edges > k - 1.

This avoids the parent bookkeeping entirely, which makes it hard to get wrong. It also gives a useful identity to remember: in a forest (no cycles at all) with c components, E = V - c.

Algorithm.

1. For each unvisited vertex, BFS its component, counting vertices and summing degrees.
2. If degreeSum / 2 > vertices - 1, return true.
3. Return false after the last component.

static boolean edgeCount(int V, List<List<Integer>> adj) {
    boolean[] visited = new boolean[V];
    for (int start = 0; start < V; start++) {
        if (visited[start]) continue;
        long vertices = 0, degreeSum = 0;
        visited[start] = true;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            int x = queue.poll();
            vertices++;
            degreeSum += adj.get(x).size();
            for (int y : adj.get(x)) {
                if (!visited[y]) {
                    visited[y] = true;
                    queue.add(y);
                }
            }
        }
        if (degreeSum / 2 > vertices - 1) return true; // every edge is counted from both ends
    }
    return false;
}

Complexity. Time O(V + E), the same single sweep. Space O(V).

Edge cases and pitfalls

• Disconnected graphs. A BFS from vertex 0 alone misses cycles in other components. Both optimal methods start a new BFS from every vertex that is still unvisited; the tests include a graph whose only cycle lives in the last component.
• Mark on enqueue, not on dequeue. If a vertex is marked only when it leaves the queue, it can be enqueued twice by two different neighbours, and its parent gets overwritten. Marking at discovery gives each vertex exactly one parent.
• The parent check is per vertex. Compare y with parent[x], not with “the previous vertex dequeued”. In BFS, consecutive dequeues are usually unrelated.
• Self-loops. With a self-loop u - u, vertex u sees itself as a visited neighbour that is not its parent, so Approach 2 correctly reports a cycle.
• Parallel edges. Two separate edges between u and v form a cycle in a multigraph, but Approach 2 ignores both because u is v’s parent. Track the parent edge index instead of the parent vertex if that matters. Approach 3 counts both edges and catches it.
• Isolated vertices. A vertex with no neighbours is its own component with k = 1 and 0 edges, which is a tree.

Related problems

• Detect A cycle in Undirected Graph using DFS solves the same task with depth-first search.
• Cycle Detection in Undirected Graph (bfs) is the same idea with the graph given as an edge list.
• Graph Valid Tree asks for “connected and no cycle”, which is exactly the edge-count test on one component.
• Detect A cycle in a Directed Graph using BFS shows why the parent trick fails for directed graphs and what replaces it.