Cycle Detection in Directed Graph

What id Directed Graph?

A directed graph, also known as a digraph, is a type of graph in which edges have a direction associated with them. In a directed graph, each edge has a specific direction, indicating a one-way relationship or connection between nodes. This is in contrast to an undirected graph, where edges have no direction and represent bidirectional relationships.

What is Back Edge in Graph?

In graph theory, a "back edge" is an edge that connects a node to one of its ancestors in a depth-first search (DFS) traversal of the graph. Back edges are significant because they indicate the presence of a cycle in the graph.

Explanation:

• When performing a depth-first search (DFS) on a graph, we visit nodes and explore their adjacent nodes.
• During this traversal, if we encounter an edge from the current node to a node that is already in the current DFS path (i.e., an ancestor of the current node in the DFS traversal), then this edge is considered a back edge.
• Back edges are crucial in cycle detection algorithms, as they indicate the presence of a cycle in a directed or undirected graph.

JAVA code for cycle detection in Graph

import java.util.*;

public class CycleDetectionDirectedGraph {

    public boolean hasCycle(int numNodes, int[][] prerequisites) {
        List<Integer>[] graph = new ArrayList[numNodes];
        for (int i = 0; i < numNodes; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int[] prerequisite : prerequisites) {
            int node = prerequisite[0];
            int prerequisiteFor = prerequisite[1];
            graph[prerequisiteFor].add(node); // Directed edge
        }

        boolean[] visited = new boolean[numNodes];
                 // tracking the nodes which are visited in current recursive call.
                 boolean[] visiting = new boolean[numNodes];

                for (int i = 0; i < numNodes; i++) {
                      if (!visited[i] && hasCycleDFS(i, graph, visited, visiting)) {
                            return true;
                      }
               }

        return false;
    }

    private boolean hasCycleDFS(int node, List<Integer>[] graph, boolean[] visited, boolean[] visiting) {
        visited[node] = true;
        visiting[node] = true;

        List<Integer> neighbors = graph[node];
        for (int neighbor : neighbors) {
            if (visiting[neighbor]) {
                return true; // Cycle detected
            }
            if (!visited[neighbor] && hasCycleDFS(neighbor, graph, visited, visiting)) {
                return true; // Cycle detected in DFS
            }
        }

        visiting[node] = false;
        return false;
    }

    public static void main(String[] args) {
        CycleDetectionDirectedGraph solution = new CycleDetectionDirectedGraph();
        
        int[][] prerequisites1 = {{1, 0}, {2, 1}, {3, 2}};
        System.out.println(solution.hasCycle(4, prerequisites1)); // Output: false (No cycle)
        
        int[][] prerequisites2 = {{1, 0}, {2, 1}, {3, 2}, {0, 3}};
        System.out.println(solution.hasCycle(4, prerequisites2)); // Output: true (Cycle: 0 -> 1 -> 2 -> 3 -> 0)
    }
}

For more such interesting content . Please book 1:1 session with me so that we can discuss thing at length.