Back to Main ACS Page

Guided Project: Detecting Cycles in Graphs

Learn how to implement cycle detection in graphs using depth-first search. Master this essential algorithm used in various real-world applications.

Project Overview

Learning Goals

Understand cycle detection algorithms
Implement DFS-based cycle detection
Handle directed and undirected graphs
Analyze algorithm complexity

Prerequisites

Graph fundamentals
Depth-first search
JavaScript classes
Recursive functions

Real-World Applications

Use Cases

Deadlock detection in operating systems
Dependency resolution in package managers
Circuit design verification
Network topology analysis

Example Scenarios

Deadlock Example:

Process A → Resource 1 → Process B → Resource 2 → Process A (Cycle indicates potential deadlock)

Detecting Cycles in Graphs

Understanding Cycle Detection

A cycle in a graph is a path where the first and last vertices are the same. Cycle detection is a fundamental graph problem with applications in deadlock detection, dependency resolution, and circuit design verification.

For directed graphs, we use a recursive DFS approach with a "recursion stack" to keep track of vertices being processed in the current path. If a vertex is visited again and it's in the recursion stack, we've found a cycle.

For undirected graphs, we use a simpler approach: if we encounter a vertex that has already been visited and it's not the parent of the current vertex, we've found a cycle.

Implementation Steps

Step 1: Graph Setup

                                        class Graph {
    private Map<String, List<String>> adjacencyList = new HashMap<>();

    public void addVertex(String vertex) {
        adjacencyList.putIfAbsent(vertex, new ArrayList<>());
    }

    public void addEdge(String v1, String v2) {
        adjacencyList.get(v1).add(v2);
        // For undirected graphs, add:
        // adjacencyList.get(v2).add(v1);
    }
}
                                    

Step 2: Cycle Detection Method

                                        public boolean hasCycle() {
    Set<String> visited = new HashSet<>();
    Set<String> recStack = new HashSet<>();

    // Check all vertices (for disconnected graphs)
    for (String vertex : adjacencyList.keySet()) {
        if (hasCycleUtil(vertex, visited, recStack)) {
            return true;
        }
    }
    return false;
}
                                    

Step 3: Helper Method for Cycle Detection

                                    private boolean hasCycleUtil(String vertex, Set<String> visited, Set<String> recStack) {
    // If not visited, mark as visited
    if (!visited.contains(vertex)) {
        visited.add(vertex);
        recStack.add(vertex);  // Add to recursion stack

        // Check all neighbors
        for (String neighbor : adjacencyList.get(vertex)) {
            // If neighbor not visited and has cycle
            if (!visited.contains(neighbor) && hasCycleUtil(neighbor, visited, recStack)) {
                return true;
            }
            // If neighbor is in recursion stack, cycle found
            else if (recStack.contains(neighbor)) {
                return true;
            }
        }
    }
    // Remove from recursion stack when backtracking
    recStack.remove(vertex);
    return false;
}
                                

Cycle Detection for Undirected Graphs

                                    public boolean hasCycleUndirected() {
    Set<String> visited = new HashSet<>();

    // Helper function
    class Helper {
        boolean hasCycleUtil(String vertex, String parent) {
            visited.add(vertex);
            for (String neighbor : adjacencyList.get(vertex)) {
                if (!visited.contains(neighbor)) {
                    if (hasCycleUtil(neighbor, vertex)) {
                        return true;
                    }
                } else if (!neighbor.equals(parent)) {
                    return true;
                }
            }
            return false;
        }
    }
    Helper helper = new Helper();
    for (String vertex : adjacencyList.keySet()) {
        if (!visited.contains(vertex)) {
            if (helper.hasCycleUtil(vertex, null)) {
                return true;
            }
        }
    }
    return false;
}
                                

Example Usage

                                // Create a directed graph
Graph graph = new Graph();

// Add vertices
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");

// Add edges (directed)
graph.addEdge("A", "B");
graph.addEdge("B", "C");
graph.addEdge("C", "A");  // Creates a cycle A -> B -> C -> A
graph.addEdge("D", "C");

// Check for cycles
System.out.println(graph.hasCycle());  // Output: true

// Visualize the graph structure
System.out.println(graph.adjacencyList);
/*
{
  A: [B],
  B: [C],
  C: [A],
  D: [C]
}
*/
                            

Practice with LeetCode

Cycle detection is a common interview question and appears in many practical problems. Practice with these LeetCode problems:

Course Schedule - Determine if you can finish all courses (cycle detection in directed graph)
Redundant Connection - Find an edge that can be removed to make a tree (cycle detection in undirected graph)
Find Eventual Safe States - Find all vertices that don't belong to a cycle

Note: Previously, this course referenced the CodeSignal Arcade, which is no longer available. The LeetCode problems above follow the same principles and are an excellent alternative for practicing graph algorithms and preparing for technical interviews.

Practice Challenge: Implement Cycle Detection

Now that you've learned how to detect cycles in graphs, try implementing the algorithm yourself.

Challenge Description

Implement a cycle detection algorithm for both directed and undirected graphs.

Requirements:

Add a method to detect cycles in a directed graph
Add a method to detect cycles in an undirected graph
Return true if a cycle is found, false otherwise
Use the Graph class provided in the guided implementation

Code Starting Point

                                class Graph {
    private Map<String, List<String>> adjacencyList = new HashMap<>();

    public void addVertex(String vertex) {
        adjacencyList.putIfAbsent(vertex, new ArrayList<>());
    }

    public void addEdge(String v1, String v2, boolean directed) {
        adjacencyList.get(v1).add(v2);
        if (!directed) {
            adjacencyList.get(v2).add(v1);
        }
    }
    // Implement cycle detection for directed graphs
    public boolean hasCycleDirected() {
        // Your code here
        return false;
    }
    // Implement cycle detection for undirected graphs
    public boolean hasCycleUndirected() {
        // Your code here
        return false;
    }
}
                            

Testing Your Solution

                                // Create a directed graph with a cycle
Graph directedGraph = new Graph();
directedGraph.addVertex("A");
directedGraph.addVertex("B");
directedGraph.addVertex("C");
directedGraph.addVertex("D");
directedGraph.addEdge("A", "B", true);
directedGraph.addEdge("B", "C", true);
directedGraph.addEdge("C", "D", true);
directedGraph.addEdge("D", "B", true); // Creates a cycle B -> C -> D -> B
System.out.println(directedGraph.hasCycleDirected()); // Should return true

// Create an undirected graph with a cycle
Graph undirectedGraph = new Graph();
undirectedGraph.addVertex("A");
undirectedGraph.addVertex("B");
undirectedGraph.addVertex("C");
undirectedGraph.addEdge("A", "B", false);
undirectedGraph.addEdge("B", "C", false);
undirectedGraph.addEdge("C", "A", false); // Creates a cycle A - B - C - A
System.out.println(undirectedGraph.hasCycleUndirected()); // Should return true
                            