NUHMAN.com

Cyclic and Acyclic Graphs in Java

In graph theory, determining whether a graph is cyclic or acyclic is crucial in many algorithms like topological sorting, deadlock detection, and more.

📘 Definitions

• Cyclic Graph: A graph that contains at least one cycle.
• Acyclic Graph: A graph with no cycles (e.g., trees or DAGs – Directed Acyclic Graphs).

1️⃣ Cycle Detection in an Undirected Graph

You can detect cycles using DFS. A cycle exists if you revisit an already visited node that isn't the parent.

Implementation

java

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adjList = new HashMap<>();

    public void addEdge(int source, int target) {
        adjList.putIfAbsent(source, new ArrayList<>());
        adjList.putIfAbsent(target, new ArrayList<>());
        adjList.get(source).add(target);
        adjList.get(target).add(source);
    }

    public boolean isCyclicUndirected() {
        Set<Integer> visited = new HashSet<>();
        for (int vertex : adjList.keySet()) {
            if (!visited.contains(vertex)) {
                if (dfsUndirected(vertex, visited, -1)) return true;
            }
        }
        return false;
    }

    private boolean dfsUndirected(int vertex, Set<Integer> visited, int parent) {
        visited.add(vertex);
        for (int neighbor : adjList.get(vertex)) {
            if (!visited.contains(neighbor)) {
                if (dfsUndirected(neighbor, visited, vertex)) return true;
            } else if (neighbor != parent) {
                return true; // Back edge
            }
        }
        return false;
    }
}

2️⃣ Cycle Detection in a Directed Graph

Use DFS with a recursion stack. If a node is revisited while still in the stack, it's a cycle.

Implementation

java

import java.util.*;

class DirectedGraph {
    private Map<Integer, List<Integer>> adjList = new HashMap<>();

    public void addEdge(int source, int target) {
        adjList.putIfAbsent(source, new ArrayList<>());
        adjList.putIfAbsent(target, new ArrayList<>());
        adjList.get(source).add(target);
    }

    public boolean isCyclicDirected() {
        Set<Integer> visited = new HashSet<>();
        Set<Integer> recStack = new HashSet<>();

        for (int vertex : adjList.keySet()) {
            if (dfsDirected(vertex, visited, recStack)) return true;
        }
        return false;
    }

    private boolean dfsDirected(int vertex, Set<Integer> visited, Set<Integer> recStack) {
        if (recStack.contains(vertex)) return true; // Cycle detected
        if (visited.contains(vertex)) return false;

        visited.add(vertex);
        recStack.add(vertex);

        for (int neighbor : adjList.get(vertex)) {
            if (dfsDirected(neighbor, visited, recStack)) return true;
        }

        recStack.remove(vertex);
        return false;
    }
}

🧪 Usage Examples

Undirected Graph

java

public class UndirectedGraphExample {
    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0); // Cycle here

        if (graph.isCyclicUndirected()) {
            System.out.println("The graph is cyclic.");
        } else {
            System.out.println("The graph is acyclic.");
        }
    }
}

Directed Graph

java

public class DirectedGraphExample {
    public static void main(String[] args) {
        DirectedGraph graph = new DirectedGraph();
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0); // Cycle here

        if (graph.isCyclicDirected()) {
            System.out.println("The graph is cyclic.");
        } else {
            System.out.println("The graph is acyclic.");
        }
    }
}

✅ Key Takeaways

• Undirected Graph: Use DFS with parent tracking to detect back edges.
• Directed Graph: Use DFS with a recursion stack to detect cycles.
• Acyclic Graphs: Essential for topological sorting, DAG algorithms, and dependency resolution.