Graph cycle detection is a fundamental problem in computer science, particularly in the domain of graph theory. It involves determining whether a cycle exists within a given graph. Cycles can be detected in both directed and undirected graphs, and various algorithms are used depending on the graph type.

Example 1: Cycle Detection in Undirected Graph using DFS

Approach:

In an undirected graph, a cycle can be detected using Depth First Search (DFS). If we encounter a visited vertex that is not the parent of the current vertex, a cycle exists.


import java.util.*;

class Graph {
    private int V;
    private LinkedList adj[];

    Graph(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;
        Integer i;
        for (Integer adjacent : adj[v]) {
            if (!visited[adjacent]) {
                if (isCyclicUtil(adjacent, visited, v))
                    return true;
            } else if (adjacent != 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[]) {
        Graph g1 = new Graph(5);
        g1.addEdge(0, 1);
        g1.addEdge(1, 2);
        g1.addEdge(2, 3);
        g1.addEdge(3, 4);
        g1.addEdge(4, 1);
        System.out.println("Graph contains cycle: " + g1.isCyclic());
    }
}

Console Output:

Graph contains cycle: true

Example 2: Cycle Detection in Directed Graph using DFS

Approach:

In directed graphs, cycles can be detected using DFS by tracking the recursion stack. If a vertex is encountered that is already in the recursion stack, a cycle is present.


import java.util.*;

class DirectedGraph {
    private int V;
    private LinkedList adj[];

    DirectedGraph(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);
    }

    boolean isCyclicUtil(int v, boolean visited[], boolean recStack[]) {
        if (recStack[v])
            return true;
        if (visited[v])
            return false;

        visited[v] = true;
        recStack[v] = true;
        for (Integer neighbour : adj[v]) {
            if (isCyclicUtil(neighbour, visited, recStack))
                return true;
        }
        recStack[v] = false;
        return false;
    }

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

    public static void main(String args[]) {
        DirectedGraph g = new DirectedGraph(4);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 1);
        System.out.println("Graph contains cycle: " + g.isCyclic());
    }
}

Console Output:

Graph contains cycle: true

Example 3: Cycle Detection using Union-Find

Approach:

The Union-Find algorithm can be used to detect cycles in an undirected graph. It involves checking if two vertices belong to the same subset. If they do, a cycle exists.


import java.util.*;

class GraphUnionFind {
    private int V, E;
    private Edge edge[];

    class Edge {
        int src, dest;
    }

    GraphUnionFind(int v, int e) {
        V = v;
        E = e;
        edge = new Edge[e];
        for (int i = 0; i < e; ++i)
            edge[i] = new Edge();
    }

    int find(int parent[], int i) {
        if (parent[i] == -1)
            return i;
        return find(parent, parent[i]);
    }

    void union(int parent[], int x, int y) {
        int xset = find(parent, x);
        int yset = find(parent, y);
        parent[xset] = yset;
    }

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

        for (int i = 0; i < E; ++i) {
            int x = find(parent, edge[i].src);
            int y = find(parent, edge[i].dest);

            if (x == y)
                return true;

            union(parent, x, y);
        }
        return false;
    }

    public static void main(String[] args) {
        int V = 3, E = 3;
        GraphUnionFind graph = new GraphUnionFind(V, E);
        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;
        graph.edge[1].src = 1;
        graph.edge[1].dest = 2;
        graph.edge[2].src = 0;
        graph.edge[2].dest = 2;

        System.out.println("Graph contains cycle: " + graph.isCycle());
    }
}

Console Output:

Graph contains cycle: true

Example 4: Cycle Detection in Directed Graph using Kahn's Algorithm

Approach:

Kahn's algorithm is a topological sorting algorithm that can be used to detect cycles in a directed graph. If the number of vertices in the topological sort is less than the total number of vertices, a cycle exists.


import java.util.*;

class GraphKahns {
    private int V;
    private LinkedList adj[];

    GraphKahns(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);
    }

    boolean isCyclic() {
        int indegree[] = new int[V];
        for (int i = 0; i < V; i++) {
            for (int node : adj[i]) {
                indegree[node]++;
            }
        }

        Queue queue = new LinkedList<>();
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0)
                queue.add(i);
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int node : adj[u]) {
                if (--indegree[node] == 0)
                    queue.add(node);
            }
            count++;
        }

        return count != V;
    }

    public static void main(String args[]) {
        GraphKahns g = new GraphKahns(4);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 1);
        System.out.println("Graph contains cycle: " + g.isCyclic());
    }
}

Console Output:

Graph contains cycle: true

Example 5: Cycle Detection using BFS in Undirected Graph

Approach:

Breadth First Search (BFS) can also be used to detect cycles in an undirected graph. If a vertex is reached that has already been visited and is not the immediate parent, a cycle exists.


import java.util.*;

class GraphBFS {
    private int V;
    private LinkedList adj[];

    GraphBFS(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];
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (isCyclicUtil(i, visited, -1))
                    return true;
            }
        }
        return false;
    }

    boolean isCyclicUtil(int v, boolean visited[], int parent) {
        Queue queue = new LinkedList<>();
        visited[v] = true;
        queue.add(v);

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

    public static void main(String args[]) {
        GraphBFS g = new GraphBFS(5);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
        g.addEdge(4, 1);
        System.out.println("Graph contains cycle: " + g.isCyclic());
    }
}

Console Output:

Graph contains cycle: true