Cycle Detection

Problem Statement

Write a Java program that extends an undirected graph implementation to detect if the graph contains a cycle using Depth-First Search (DFS). A cycle exists if there is a path that starts and ends at the same vertex, passing through at least one other vertex. The program should reuse the adjacency list representation and test cycle detection with cyclic and acyclic graphs, including edge cases like empty graphs and single-vertex graphs. You can visualize this as exploring a network of roads to check if you can loop back to a starting city without retracing steps, ensuring no dead ends create a false cycle.

Input:

• An undirected graph represented by an adjacency list, with vertices as integers (0 to n-1).
• The number of vertices n and a list of edges (pairs of vertices). Output: A boolean indicating whether the graph contains a cycle, and a string representation of the graph’s adjacency list for clarity. Constraints:
• The number of vertices n is between 0 and 10^5.
• Edges are pairs of integers [u, v] where 0 ≤ u, v < n.
• The graph is undirected (edge [u, v] implies [v, u]). Example:
• Input: n = 4, edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
• Output: Has Cycle = true, "Adjacency List: {0=[1, 3], 1=[0, 2], 2=[1, 3], 3=[2, 0]}"
• Explanation: The graph has a cycle (0→1→2→3→0).
• Input: n = 4, edges = [[0, 1], [1, 2], [2, 3]]
• Output: Has Cycle = false, "Adjacency List: {0=[1], 1=[0, 2], 2=[1, 3], 3=[2]}"
• Explanation: The graph is a tree (acyclic).
• Input: n = 0, edges = []
• Output: Has Cycle = false, "Adjacency List: {}"
• Explanation: An empty graph has no cycles.

Pseudocode

FUNCTION createGraph(n, edges)
    CREATE adjList as new HashMap
    FOR i from 0 to n-1
        SET adjList[i] to empty list
    ENDFOR
    FOR each edge [u, v] in edges
        ADD v to adjList[u]
        ADD u to adjList[v]
    ENDFOR
    RETURN adjList
ENDFUNCTION

FUNCTION hasCycle(adjList, n)
    IF n is 0 THEN
        RETURN false
    ENDIF
    CREATE visited as boolean array of size n, initialized to false
    FUNCTION dfs(vertex, parent)
        SET visited[vertex] to true
        FOR each neighbor in adjList[vertex]
            IF NOT visited[neighbor] THEN
                IF dfs(neighbor, vertex) THEN
                    RETURN true
                ENDIF
            ELSE IF neighbor is not parent THEN
                RETURN true
            ENDIF
        ENDFOR
        RETURN false
    ENDFUNCTION
    FOR i from 0 to n-1
        IF NOT visited[i] THEN
            IF dfs(i, -1) THEN
                RETURN true
            ENDIF
        ENDIF
    ENDFOR
    RETURN false
ENDFUNCTION

FUNCTION toString(adjList)
    CREATE result as new StringBuilder
    APPEND "Adjacency List: {" to result
    FOR each vertex in adjList
        APPEND vertex and "=" and adjList[vertex] to result
        IF vertex is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "}" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of (n, edges) pairs
    FOR each testCase in testCases
        PRINT test case details
        SET adjList to createGraph(testCase.n, testCase.edges)
        CALL hasCycle(adjList, testCase.n)
        PRINT cycle result and graph using toString
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Reuse createGraph: a. Create a HashMap adjList mapping vertices to lists of neighbors. b. Initialize empty lists for vertices 0 to n-1. c. Add edges bidirectionally (u→v, v→u).
2. Define hasCycle: a. If n = 0, return false (empty graph has no cycles). b. Use DFS with a parent parameter to avoid false cycles:
   • Mark vertex as visited.
   • For each neighbor, if unvisited, recurse; if visited and not parent, cycle found. c. Run DFS from each unvisited vertex to handle disconnected components. d. Return true if a cycle is found, false otherwise.
3. Define toString: a. Convert adjacency list to a string, e.g., "{0=[1, 3], 1=[0, 2], ...}".
4. In main, test with: a. A cyclic graph. b. An acyclic graph (tree). c. An empty graph (n = 0). d. A single-vertex graph.

Java Implementation

import java.util.*;

public class CycleDetection {
    // Creates adjacency list representation of the graph
    private Map<Integer, List<Integer>> createGraph(int n, int[][] edges) {
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        for (int i = 0; i < n; i++) {
            adjList.put(i, new ArrayList<>());
        }
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            adjList.get(u).add(v);
            adjList.get(v).add(u); // Undirected graph
        }
        return adjList;
    }

    // Checks if the graph contains a cycle using DFS
    public boolean hasCycle(Map<Integer, List<Integer>> adjList, int n) {
        if (n == 0) {
            return false;
        }
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                if (dfs(i, -1, adjList, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int vertex, int parent, Map<Integer, List<Integer>> adjList, boolean[] visited) {
        visited[vertex] = true;
        for (int neighbor : adjList.get(vertex)) {
            if (!visited[neighbor]) {
                if (dfs(neighbor, vertex, adjList, visited)) {
                    return true;
                }
            } else if (neighbor != parent) {
                return true; // Cycle found
            }
        }
        return false;
    }

    // Converts graph to string (adjacency list)
    public String toString(Map<Integer, List<Integer>> adjList) {
        StringBuilder result = new StringBuilder("Adjacency List: {");
        List<Integer> vertices = new ArrayList<>(adjList.keySet());
        Collections.sort(vertices); // For consistent output
        for (int i = 0; i < vertices.size(); i++) {
            int vertex = vertices.get(i);
            result.append(vertex).append("=").append(adjList.get(vertex));
            if (i < vertices.size() - 1) {
                result.append(", ");
            }
        }
        result.append("}");
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        int n;
        int[][] edges;

        TestCase(int n, int[][] edges) {
            this.n = n;
            this.edges = edges;
        }
    }

    // Main method to test cycle detection
    public static void main(String[] args) {
        CycleDetection cycleDetector = new CycleDetection();

        // Test cases
        TestCase[] testCases = {
            // Cyclic graph: 0-1-2-3-0
            new TestCase(4, new int[][]{{0, 1}, {1, 2}, {2, 3}, {3, 0}}),
            // Acyclic graph (tree): 0-1-2-3
            new TestCase(4, new int[][]{{0, 1}, {1, 2}, {2, 3}}),
            // Empty graph
            new TestCase(0, new int[][]{}),
            // Single vertex
            new TestCase(1, new int[][]{})
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Vertices: " + testCases[i].n);
            System.out.println("Edges: " + Arrays.deepToString(testCases[i].edges));
            Map<Integer, List<Integer>> adjList = cycleDetector.createGraph(testCases[i].n, testCases[i].edges);
            boolean hasCycle = cycleDetector.hasCycle(adjList, testCases[i].n);
            System.out.println("Has Cycle: " + hasCycle);
            System.out.println(cycleDetector.toString(adjList) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Vertices: 4
Edges: [[0, 1], [1, 2], [2, 3], [3, 0]]
Has Cycle: true
Adjacency List: {0=[1, 3], 1=[0, 2], 2=[1, 3], 3=[2, 0]}

Test case 2:
Vertices: 4
Edges: [[0, 1], [1, 2], [2, 3]]
Has Cycle: false
Adjacency List: {0=[1], 1=[0, 2], 2=[1, 3], 3=[2]}

Test case 3:
Vertices: 0
Edges: []
Has Cycle: false
Adjacency List: {}

Test case 4:
Vertices: 1
Edges: []
Has Cycle: false
Adjacency List: {0=[]}

Explanation:

• Test case 1: Graph has a cycle (0→1→2→3→0), so returns true.
• Test case 2: Graph is a tree (acyclic), so returns false.
• Test case 3: Empty graph has no cycles, returns false.
• Test case 4: Single vertex has no cycles, returns false.

How It Works

• createGraph: Builds an adjacency list using a HashMap, adding undirected edges (u→v, v→u).
• hasCycle:
  • Returns false for n = 0 (empty graph).
  • Runs DFS from each unvisited vertex to handle disconnected components.
  • In DFS, marks vertex as visited, checks neighbors:
    • If neighbor is unvisited, recurse.
    • If neighbor is visited and not the parent, a cycle is found.
  • Returns true if a cycle is detected, false otherwise.
• dfs: Tracks parent to avoid false cycles in undirected graphs.
• toString: Formats adjacency list as a string, sorting vertices for consistency.
• Example Trace (Test case 1):
  • DFS from 0: Visit 0, explore 1 (parent=0), explore 2 (parent=1), explore 3 (parent=2).
  • At 3, neighbor 0 is visited and not parent (2), cycle found.
• Main Method: Tests cyclic graph, acyclic graph, empty graph, and single vertex.

Complexity Analysis Table

Note:

• n is the number of vertices, e is the number of edges.
• Time complexity: O(n + e) for createGraph (initialize lists and add edges); O(n + e) for hasCycle (DFS visits each vertex and edge once); O(n log n + e) for toString (sorting vertices).
• Space complexity: O(n + e) for createGraph and toString (adjacency list); O(n) for hasCycle (visited array and recursion stack).
• Worst case: O(n + e) time and space for dense graphs.

✅ Tip: Use DFS with a parent parameter to detect cycles in undirected graphs, ensuring visited neighbors that aren’t parents indicate a cycle. Start DFS from each unvisited vertex to handle disconnected components.

⚠ Warning: In undirected graphs, avoid false cycle detection by checking the parent vertex. Handle edge cases like empty graphs or single vertices to ensure correct results.