Cycle Detection in Undirected Graph in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of DFS-based Cycle Detection

What is the output of the following Java code that detects a cycle in an undirected graph using DFS?

DSA Java

import java.util.*;

public class GraphCycle {
    private int V;
    private LinkedList<Integer>[] adj;

    public GraphCycle(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    boolean isCyclicUtil(int v, boolean[] visited, int parent) {
        visited[v] = true;
        for (Integer i : adj[v]) {
            if (!visited[i]) {
                if (isCyclicUtil(i, visited, v))
                    return true;
            } else if (i != parent) {
                return true;
            }
        }
        return false;
    }

    boolean isCyclic() {
        boolean[] visited = new boolean[V];
        for (int u = 0; u < V; u++) {
            if (!visited[u]) {
                if (isCyclicUtil(u, visited, -1))
                    return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        GraphCycle g = new GraphCycle(4);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 0);
        System.out.println(g.isCyclic());
    }
}

A false

B Runtime exception

C Compilation error

D true

💡 Hint

Think about whether the graph edges form a closed loop.

The graph has edges forming a cycle: 0-1-2-3-0. The DFS detects this cycle and returns true.

❓ Predict Output

intermediate

Output of BFS-based Cycle Detection

What will be the output of this Java code that uses BFS to detect a cycle in an undirected graph?

DSA Java

import java.util.*;

public class GraphCycleBFS {
    private int V;
    private LinkedList<Integer>[] adj;

    public GraphCycleBFS(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    boolean isCyclic() {
        boolean[] visited = new boolean[V];
        int[] parent = new int[V];
        Arrays.fill(parent, -1);

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                Queue<Integer> queue = new LinkedList<>();
                visited[i] = true;
                queue.add(i);

                while (!queue.isEmpty()) {
                    int u = queue.poll();
                    for (int v : adj[u]) {
                        if (!visited[v]) {
                            visited[v] = true;
                            parent[v] = u;
                            queue.add(v);
                        } else if (parent[u] != v) {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        GraphCycleBFS g = new GraphCycleBFS(3);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        System.out.println(g.isCyclic());
    }
}

A Runtime exception

B true

C false

D Compilation error

💡 Hint

Check if the graph edges form any cycle.

The graph is a simple chain 0-1-2 with no cycles, so the BFS cycle detection returns false.

🔧 Debug

advanced

Identify the bug in cycle detection code

What error will occur when running this Java code for cycle detection in an undirected graph?

DSA Java

import java.util.*;

public class BuggyGraph {
    private int V;
    private LinkedList<Integer>[] adj;

    public BuggyGraph(int v) {
        V = v;
        adj = new LinkedList[V];
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    boolean isCyclicUtil(int v, boolean[] visited, int parent) {
        visited[v] = true;
        for (int i : adj[v]) {
            if (!visited[i]) {
                if (isCyclicUtil(i, visited, v))
                    return true;
            } else if (i != parent) {
                return true;
            }
        }
        return false;
    }

    boolean isCyclic() {
        boolean[] visited = new boolean[V];
        for (int u = 0; u < V; u++) {
            if (!visited[u]) {
                if (isCyclicUtil(u, visited, -1))
                    return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        BuggyGraph g = new BuggyGraph(3);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        System.out.println(g.isCyclic());
    }
}

A Compilation error due to generic array creation

B NullPointerException at runtime

C StackOverflowError due to infinite recursion

D No error, outputs true

💡 Hint

Check how the adjacency list array is initialized.

The adjacency list array is created with LinkedList[V] but Java does not allow generic array creation directly, causing a NullPointerException when accessing adj[i].add().

🧠 Conceptual

advanced

Why is parent tracking needed in cycle detection?

In cycle detection for an undirected graph using DFS, why do we track the parent node of the current node?

A To avoid counting the edge back to the parent as a cycle

B To keep track of the depth of recursion

C To mark nodes as visited

D To store the path of the cycle

💡 Hint

Think about why revisiting the immediate previous node is not a cycle.

In an undirected graph, the edge back to the parent is not a cycle. Tracking parent helps ignore this edge when checking for cycles.

🚀 Application

expert

Detect cycle in a disconnected undirected graph

Given a disconnected undirected graph with 5 vertices and edges: (0-1), (1-2), (3-4), (4-3), what is the output of cycle detection using DFS?

DSA Java

import java.util.*;

public class DisconnectedGraphCycle {
    private int V;
    private LinkedList<Integer>[] adj;

    public DisconnectedGraphCycle(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    boolean isCyclicUtil(int v, boolean[] visited, int parent) {
        visited[v] = true;
        for (Integer i : adj[v]) {
            if (!visited[i]) {
                if (isCyclicUtil(i, visited, v))
                    return true;
            } else if (i != parent) {
                return true;
            }
        }
        return false;
    }

    boolean isCyclic() {
        boolean[] visited = new boolean[V];
        for (int u = 0; u < V; u++) {
            if (!visited[u]) {
                if (isCyclicUtil(u, visited, -1))
                    return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        DisconnectedGraphCycle g = new DisconnectedGraphCycle(5);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(3, 4);
        g.addEdge(4, 3);
        System.out.println(g.isCyclic());
    }
}

A true

B false

C Compilation error

D Runtime exception

💡 Hint

Check if any connected component contains a cycle.

The component with nodes 3 and 4 has edges forming a cycle (3-4 and 4-3). The cycle detection returns true.

Practice

1. What is the main idea behind detecting a cycle in an undirected graph using DFS?

easy

A. If the graph has more edges than nodes, it always has a cycle.

B. If all nodes are visited exactly once, the graph has a cycle.

C. If the graph is disconnected, it contains a cycle.

D. If we visit a node that is already visited and is not the parent, a cycle exists.

Solution

1. Step 1: Understand DFS traversal in undirected graph

   DFS visits nodes and tracks the parent node to avoid false cycle detection.

2. Step 2: Detect cycle condition

   If during DFS, a visited node is found that is not the parent, it means a back edge exists, indicating a cycle.

3. Final Answer:

   If we visit a node that is already visited and is not the parent, a cycle exists. -> Option D

4. Quick Check:

   Cycle detection in undirected graph = check visited node not parent [OK]

Hint: Check visited nodes excluding parent during DFS to find cycles [OK]

Common Mistakes:

• Confusing parent node with visited node
• Assuming disconnected graph always has cycles
• Thinking more edges than nodes always means cycle

2. Which of the following Java method signatures is correct for a DFS function used in cycle detection in an undirected graph?

easy

A. boolean dfs(int node, boolean[] visited, List graph)

B. void dfs(int node, int parent, boolean[] visited, List<Integer> graph)

C. boolean dfs(int node, int parent, boolean[] visited, List graph)

D. int dfs(int node, int parent, boolean[] visited, List graph)

Solution

1. Step 1: Identify parameters needed for DFS cycle detection

   DFS needs current node, parent node, visited array, and adjacency list graph.

2. Step 2: Check return type and parameter types

   Return type boolean indicates if cycle found; graph must be List of Lists for adjacency; parent is needed.

3. Final Answer:

   boolean dfs(int node, int parent, boolean[] visited, List<List<Integer>> graph) -> Option C

4. Quick Check:

   DFS signature with parent and boolean return = boolean dfs(int node, int parent, boolean[] visited, List graph) [OK]

Hint: DFS needs parent node and boolean return for cycle detection [OK]

Common Mistakes:

• Using void return type instead of boolean
• Passing graph as List<Integer> instead of List
• Omitting parent parameter

3. What will be the output of the following Java code snippet detecting cycle in an undirected graph?

import java.util.*;
public class GraphCycle {
    static boolean dfs(int node, int parent, boolean[] visited, List graph) {
        visited[node] = true;
        for (int adj : graph.get(node)) {
            if (!visited[adj]) {
                if (dfs(adj, node, visited, graph)) return true;
            } else if (adj != parent) {
                return true;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        int n = 4;
        List graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        graph.get(0).add(1); graph.get(1).add(0);
        graph.get(1).add(2); graph.get(2).add(1);
        graph.get(2).add(3); graph.get(3).add(2);
        graph.get(3).add(1); graph.get(1).add(3);
        boolean[] visited = new boolean[n];
        boolean hasCycle = false;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                if (dfs(i, -1, visited, graph)) {
                    hasCycle = true;
                    break;
                }
            }
        }
        System.out.println(hasCycle);
    }
}

medium

A. true

B. false

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Analyze graph edges and structure

   Graph edges: 0-1, 1-2, 2-3, 3-1 form a cycle (1-2-3-1).

2. Step 2: Trace DFS cycle detection logic

   DFS finds visited node 1 again from 3 (not parent), so returns true indicating cycle.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Cycle detected in graph = true [OK]

Hint: Look for back edge to visited node not parent to confirm cycle [OK]

Common Mistakes:

• Ignoring the edge 3-1 that closes the cycle
• Assuming no cycle because graph is connected
• Misunderstanding parent check in DFS

4. Identify the bug in the following Java code snippet for cycle detection in an undirected graph:

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

medium

A. Incorrect parent check condition

B. Missing return statement for recursive dfs call result

C. Visited array not updated correctly

D. Graph adjacency list type is wrong

Solution

1. Step 1: Review recursive DFS calls

   Recursive call dfs(adj, node, visited, graph) is made but its boolean result is ignored.

2. Step 2: Understand impact of ignoring return value

   If a cycle is detected deeper, it won't propagate true back, causing false negatives.

3. Final Answer:

   Missing return statement for recursive dfs call result -> Option B

4. Quick Check:

   Return recursive call result to detect cycles correctly [OK]

Hint: Always return recursive DFS call result when checking for cycles [OK]

Common Mistakes:

• Not returning true from recursive calls
• Confusing parent check logic
• Not marking nodes visited before recursion

5. Given an undirected graph represented as adjacency list:

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

Which of the following modifications will correctly detect a cycle in this graph using DFS cycle detection method?

hard

A. Start DFS from node 0 and pass -1 as parent; check visited nodes for back edges.

B. Start DFS from node 4 only; ignore parent parameter in DFS calls.

C. Use BFS instead of DFS without parent tracking to detect cycles.

D. Mark nodes visited after all recursive calls complete.

Solution

1. Step 1: Understand graph structure and cycle presence

   Edges form a cycle: 0-1-3-2-0. Starting DFS from 0 covers all nodes.

2. Step 2: Apply correct DFS cycle detection method

   Starting DFS from 0 with parent -1 and checking visited nodes excluding parent detects cycle correctly.

3. Final Answer:

   Start DFS from node 0 and pass -1 as parent; check visited nodes for back edges. -> Option A

4. Quick Check:

   Proper DFS start and parent check detects cycle [OK]

Hint: Start DFS from any node with parent -1 and track visited nodes [OK]

Common Mistakes:

• Ignoring parent parameter causing false positives
• Starting DFS from leaf node only
• Marking visited nodes too late