Detect Cycle

Cycle in Undirected Graph

1. Implementation

public static boolean hasCycle(int[][] edges, int n) {
        List<List<Integer>> adjList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            adjList.get(edge[0]).add(edge[1]);
            adjList.get(edge[1]).add(edge[0]);
        }

        boolean[] visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                if (detectCycle(i, -1, visited, adjList)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean detectCycle(int curVertex, int parent, boolean[] visited, List<List<Integer>> adjList) {
        visited[curVertex] = true;

        for (int nextVertex : adjList.get(curVertex)) {
            if (!visited[nextVertex]) {
                if (detectCycle(nextVertex, curVertex, visited, adjList)) {
                    return true;
                }
            }
            // If an adjacent is visited and not parent of current vertex, then there is a cycle.
            else if (nextVertex != parent) {
                return true;
            }
        }
        return false;
    }

2. Time Complexity

Time: O(V + E)

Space: O(V + E)

Cycle in Directed Graph

1. Detect Cycle with Coloring

public enum Color {WHITE, GRAY, BLACK};

    public static boolean hasCycle(int[][] edges, int n) {
        List<List<Integer>> adjList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            adjList.get(edge[0]).add(edge[1]);
        }

        Color[] colors = new Color[n];
        Arrays.fill(colors, Color.WHITE);

        for (int i = 0; i < n; i++) {
            // vertex with White means this vertex is not visited yet
            if (colors[i] == Color.WHITE) {
                if (dfs(i, colors, adjList)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean dfs(int curVertex, Color[] colors, List<List<Integer>> adjList) {
        // vertex with Gray means it is in the process of DFS
        colors[curVertex] = Color.GRAY;

        for (int nextVertex : adjList.get(curVertex)) {
            if (colors[nextVertex] == Color.GRAY) {
                return true;
            }

            if (colors[nextVertex] == Color.WHITE && dfs(nextVertex, colors, adjList)) {
                return true;
            }
        }
        // vertex with Black means it is done for DFS
        colors[curVertex] = Color.BLACK;
        return false;
    }

2. Time Complexity

Time: O(V + E)

Space: O(V + E)