Graphs are an integral part of computer science, used in various applications from social networking to route planning. One of the common problems associated with graphs is cycle detection. Detecting a cycle can have significant implications, such as identifying deadlocks in resource allocation, understanding dependencies in tasks, or validating the correctness of a directed graph. In this blog post, we’ll delve into the techniques for detecting cycles in both directed and undirected graphs using Java.

---

Understanding Graphs

Before we dive into the methods of cycle detection, let’s briefly review what graphs are. A graph consists of vertices (nodes) connected by edges (links). Depending on the directionality of edges, graphs can be classified into directed graphs (where edges have a direction) and undirected graphs (where edges do not have a direction).

Directed Graph Example

    A → B → C
    ↑       |
    |_______ |

Undirected Graph Example

    A
   / \
  B - C

---

Cycle Detection in Directed Graphs

To detect cycles in a directed graph, we can utilize the Depth-First Search (DFS) algorithm. The main idea is to maintain a recursion stack during the DFS traversal. If we encounter a node that is already in the stack, we conclude there’s a cycle.

Steps

1. Create a visited array to mark visited nodes.
2. Create a recStack array to keep track of nodes in the current path.
3. Perform DFS on each node. If we revisit a node currently in the recursion stack, it indicates a cycle.

Java Implementation

import java.util.*;

public class Graph {
    private int vertices; // number of vertices
    private List<List<Integer>> adjList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adjList.get(u).add(v);
    }

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

        visited[v] = true;
        recStack[v] = true;

        for (int neighbor : adjList.get(v)) {
            if (cycleUtil(neighbor, visited, recStack)) {
                return true;
            }
        }
        
        recStack[v] = false;
        return false;
    }

    public boolean hasCycle() {
        boolean[] visited = new boolean[vertices];
        boolean[] recStack = new boolean[vertices];
        
        for (int i = 0; i < vertices; i++) {
            if (cycleUtil(i, visited, recStack)) {
                return true;
            }
        }
        return false;
    }

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

In this example, the graph contains a cycle due to edges 0 → 1 → 2 → 0.

---

Cycle Detection in Undirected Graphs

For undirected graphs, we can again apply a modified DFS approach. The key difference is that when we traverse the graph, we have to check if we revisit the parent node, as it doesn't constitute a cycle.

Steps

1. Create a visited array.
2. Perform DFS while keeping track of the parent node.
3. If a visited node is found that isn’t the parent, a cycle exists.

Java Implementation

import java.util.*;

public class UndirectedGraph {
    private int vertices; // number of vertices
    private List<List<Integer>> adjList;

    public UndirectedGraph(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adjList.get(u).add(v);
        adjList.get(v).add(u); // Undirected graph: add edge both ways
    }

    private boolean cycleUtil(int v, boolean[] visited, int parent) {
        visited[v] = true;

        for (int neighbor : adjList.get(v)) {
            if (!visited[neighbor]) {
                if (cycleUtil(neighbor, visited, v)) {
                    return true;
                }
            } else if (neighbor != parent) {
                return true; // Cycle detected
            }
        }
        return false;
    }

    public boolean hasCycle() {
        boolean[] visited = new boolean[vertices];

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

    public static void main(String[] args) {
        UndirectedGraph graph = new UndirectedGraph(4);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0); // Creates a cycle
        graph.addEdge(3, 2);

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

Here, we see a cycle due to the edges between 0, 1, and 2 leading back to 0.

---

By understanding these algorithms, software engineers can address practical problems involving graph structures effectively. From detecting deadlocks in concurrent processing to ensuring tree traversal correctness, cycle detection is a critical skill to develop while navigating the realm of data structures and algorithms.