☕ DSA Java Articles

Topics › Graphs › Problems on BFS/DFS

Cycle Detection in Undirected Graph (bfs)

Hard TUF ID 2817 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an undirected graph with n vertices labelled 0..n-1 and a list of edges. The graph may be disconnected. Return true if it contains a cycle, that is, a closed route that starts and ends at the same vertex, uses at least one edge, and never repeats an edge.

Assume there are no parallel edges (two edges between the same pair of vertices); the pitfalls section explains what changes if there are. A self-loop {u, u} counts as a cycle.

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

Example 1

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

Example 2

n = 5, edges = 0-1, 1-2, 1-3, 3-4
answer = false      // a tree: connected, 4 edges on 5 vertices, no loop

The difficulty is entirely in one detail. In an undirected graph every edge u-v is stored as two arrows, u -> v and v -> u. A naive traversal that reports a cycle whenever it sees an already-visited neighbour would immediately “find” a cycle on every edge, by looking back from v at the vertex u it just came from. The solutions must tell that harmless step back apart from a genuine second route.

Approach 1: Brute force, test every edge

Intuition. An edge u-v lies on a cycle exactly when u and v stay connected after removing that edge: the other route from u to v, plus the edge itself, closes the loop. Conversely, if removing the edge disconnects its ends, no cycle can use it. So the graph has a cycle if and only if some edge passes this test. Each test is a plain reachability BFS on the graph without that edge.

Algorithm.

  1. For each edge {u, v}: if u == v, it is a self-loop, so return true.
  2. Build the adjacency list of all edges except this one.
  3. If v is reachable from u, return true.
  4. After all edges, return false.
static boolean bruteForce(int n, int[][] edges) {
    for (int skip = 0; skip < edges.length; skip++) {
        int u = edges[skip][0], v = edges[skip][1];
        if (u == v) return true;                          // a self-loop is a cycle on its own
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < edges.length; i++) {
            if (i == skip) continue;
            adj.get(edges[i][0]).add(edges[i][1]);
            adj.get(edges[i][1]).add(edges[i][0]);
        }
        if (reachable(adj, u, v)) return true;            // another route plus this edge closes a loop
    }
    return false;
}

static boolean reachable(List<List<Integer>> adj, int from, int to) {
    boolean[] seen = new boolean[adj.size()];
    Deque<Integer> queue = new ArrayDeque<>();
    seen[from] = true;
    queue.add(from);
    while (!queue.isEmpty()) {
        int x = queue.poll();
        if (x == to) return true;
        for (int y : adj.get(x)) {
            if (!seen[y]) {
                seen[y] = true;
                queue.add(y);
            }
        }
    }
    return false;
}

Complexity. Time O(E * (V + E)): for each edge, rebuild the list and run a BFS. Space O(V + E). It is a correct and very direct definition of “edge on a cycle”, but with 10^5 edges it would take on the order of 10^10 steps. The tests run it on a 500-vertex path and ring, where it is still instant.

Approach 2: Optimal, BFS with parent tracking

Intuition. Run a BFS, and for each queued vertex also remember its parent, the vertex it was discovered from. When scanning the neighbours of node:

Why is the last case really a cycle? Every visited vertex hangs from the start through a chain of parent links, so the visited vertices form a tree (the BFS tree). That tree contains exactly the edges used to discover vertices. If node sees a visited next that is not its parent, the edge node-next is not one of those tree edges, and adding any extra edge to a tree closes a loop: the tree path from node to next, plus this edge. Conversely, if the component is a tree, the only visited neighbour a vertex can see is its parent: any child is discovered only through it.

The BFS from one vertex covers only its component, so, as in every whole-graph algorithm, it is wrapped in a loop that starts a new BFS from each unvisited vertex. The cycle may well sit in a component that does not contain vertex 0.

Algorithm.

  1. Build the adjacency list.
  2. For each vertex start not yet visited, run bfsFindsCycle(start); return true as soon as one does.
  3. bfsFindsCycle: mark start, enqueue {start, -1}. Poll {node, parent}; for each neighbour next: if unvisited, mark it and enqueue {next, node}; else if next != parent, return true.
  4. Return false if no BFS found a cycle.
static boolean optimalBfs(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    boolean[] visited = new boolean[n];
    for (int start = 0; start < n; start++) {
        if (visited[start]) continue;                     // every component needs its own BFS
        if (bfsFindsCycle(adj, start, visited)) return true;
    }
    return false;
}

static boolean bfsFindsCycle(List<List<Integer>> adj, int start, boolean[] visited) {
    Deque<int[]> queue = new ArrayDeque<>();              // entries are {vertex, parent}
    visited[start] = true;
    queue.add(new int[]{start, -1});
    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        int node = cur[0], parent = cur[1];
        for (int next : adj.get(node)) {
            if (!visited[next]) {
                visited[next] = true;
                queue.add(new int[]{next, node});
            } else if (next != parent) {
                return true;                              // reached already by a different route
            }
        }
    }
    return false;
}

Dry run on example 1 (adj: 0:[1], 1:[0,2,4], 2:[1,3], 3:[2,4], 4:[3,1]):

polled {node, parent} neighbour checks queue after
{0, -1} 1 new {1,0}
{1, 0} 0 is the parent; 2 new; 4 new {2,1} {4,1}
{2, 1} 1 is the parent; 3 new {4,1} {3,2}
{4, 1} 3 is visited and not the parent return true

Vertex 3 was discovered from 2, and 4 now reaches it directly. The two routes 1-2-3 and 1-4-3 form the cycle 1-2-3-4-1.

Complexity. Time O(V + E): each vertex is enqueued once over all the BFS runs (the visited array is shared), and each adjacency list is scanned once. Space O(V + E) for the adjacency list, plus O(V) for visited and the queue.

The start vertex gets parent -1, a value that can never equal a real vertex. That way its neighbours are never mistaken for “the edge we came from”.

Approach 3: Union-find

Intuition. Add the edges one at a time to a union-find structure. Before adding u-v, ask whether u and v are already in the same set. If they are, there is already a route between them, so this edge closes a cycle. If not, union the two sets. No adjacency list and no traversal are needed, and the edges can be processed in any order.

Algorithm.

  1. parent[i] = i for all vertices.
  2. For each edge {u, v}: if find(u) == find(v), return true; otherwise union them.
  3. Return false.
static boolean unionFind(int n, int[][] edges) {
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    for (int[] e : edges) {
        int a = find(parent, e[0]), b = find(parent, e[1]);
        if (a == b) return true;                          // u and v were already connected
        parent[a] = b;
    }
    return false;
}

static int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

Complexity. Time O(V + E * α(V)), space O(V). A self-loop is caught for free, since find(u) == find(u). This is the same test Kruskal’s algorithm uses to decide whether adding an edge to a growing spanning tree would create a cycle.

Edge cases and pitfalls