Detect Cycle in an undirected Graph

Link - Detect Cycle in an Undirected Graph

Problem Statement

Given an undirected graph with V vertices and E edges, determine whether the graph contains a cycle.

Return true if a cycle is present, otherwise return false.

Examples

Example 1

Input:
V = 5, E = 5
Edges: 
0 -- 1
1 -- 2
2 -- 3
3 -- 4
4 -- 1

Output: true

Explanation:
There is a cycle: 1 -> 2 -> 3 -> 4 -> 1

Example 2

Input:
V = 3, E = 2
Edges:
0 -- 1
1 -- 2

Output: false

Explanation:
No cycle present in the graph.

Constraints

• 1 ≤ V ≤ 10^5

• 0 ≤ E ≤ 10^5

• The graph is undirected

• The graph may be disconnected

Intuition

In an undirected graph, edges are bidirectional. While visiting adjacent nodes during traversal (using DFS or BFS), revisiting the parent node is valid. However, encountering a previously visited node that is not the parent indicates the presence of a cycle.

Key idea:

• If a neighbor is already visited and not the parent, a cycle exists.

Applications

• Detecting loops in network topologies

• Validating whether a graph is a tree

• Deadlock detection in resource-allocation systems

• Checking for circular dependencies in compilers or build systems

Approaches

We explore two traversal-based methods:

1. Breadth-First Search (BFS) with parent tracking

2. Depth-First Search (DFS) with parent tracking

Approach 1: BFS with Parent Tracking

Algorithm

1. Initialize a visited[] array of size V.

2. Traverse every unvisited node (to handle disconnected components).

3. For each unvisited node:

   • Perform BFS using a queue that stores pairs {node, parent}.

   • For every neighbor of the current node:

     • If the neighbor is unvisited: mark it visited and enqueue it.

     • If the neighbor is visited and is not the parent: cycle exists.

Java Code (BFS)

class Solution {
    public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
        boolean[] visited = new boolean[V];

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (bfs(i, adj, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean bfs(int start, ArrayList<ArrayList<Integer>> adj, boolean[] visited) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{start, -1});
        visited[start] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int node = current[0];
            int parent = current[1];

            for (int neighbor : adj.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(new int[]{neighbor, node});
                } else if (neighbor != parent) {
                    return true;
                }
            }
        }
        return false;
    }
}

Dry Run

Adjacency list:

0: [1, 2]
1: [0, 2]
2: [0, 1]

• Start BFS from 0 → mark 0 visited, enqueue (0, -1)

• Visit 1 → enqueue (1, 0)

• Visit 2 → enqueue (2, 0)

• Visit 1 again → neighbor 2 already visited and not parent → cycle detected

Time and Space Complexity

Approach 2: DFS with Parent Tracking

Algorithm

1. Create a visited[] array of size V.

2. For each unvisited node, run dfs(node, parent).

3. In the recursive DFS function:

   • Mark the node as visited.

   • For each neighbor:

     • If not visited → recursive DFS

     • If already visited and not the parent → cycle detected

Java Code (DFS)

class Solution {
    public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
        boolean[] visited = new boolean[V];

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (dfs(i, -1, visited, adj)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int node, int parent, boolean[] visited, ArrayList<ArrayList<Integer>> adj) {
        visited[node] = true;

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                if (dfs(neighbor, node, visited, adj)) {
                    return true;
                }
            } else if (neighbor != parent) {
                return true;
            }
        }

        return false;
    }
}

Dry Run

Graph:

0: [1]
1: [0, 2]
2: [1, 3]
3: [2, 0]

• Start DFS from 0

• Visit 1 → DFS on 2 → DFS on 3

• 3 → neighbor 0 is visited and not parent → cycle detected

Time and Space Complexity

Conclusion

• In undirected graphs, cycles are detected by checking if a visited neighbor is not the parent.

• Both DFS and BFS can be used for cycle detection.

• Parent tracking is crucial to distinguish real cycles from trivial backtracking.