Back to Welcome 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 {
    constructor() {
        this.adjacencyList = {};
    }

    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) {
            this.adjacencyList[vertex] = [];
        }
    }

    addEdge(v1, v2) {
        this.adjacencyList[v1].push(v2);
        // For undirected graphs, add:
        // this.adjacencyList[v2].push(v1);
    }
}
                                    

Step 2: Cycle Detection Method

                                        hasCycle() {
    const visited = {};
    const recStack = {};

    // Check all vertices (for disconnected graphs)
    for (let vertex in this.adjacencyList) {
        if (this.hasCycleUtil(vertex, visited, recStack)) {
            return true;
        }
    }
    return false;
}
                                    

Step 3: Helper Method for Cycle Detection

                                    hasCycleUtil(vertex, visited, recStack) {
    // If not visited, mark as visited
    if (!visited[vertex]) {
        visited[vertex] = true;
        recStack[vertex] = true;  // Add to recursion stack

        // Check all neighbors
        for (let neighbor of this.adjacencyList[vertex]) {
            // If neighbor not visited and has cycle
            if (!visited[neighbor] && 
                this.hasCycleUtil(neighbor, visited, recStack)) {
                return true;
            } 
            // If neighbor is in recursion stack, cycle found
            else if (recStack[neighbor]) {
                return true;
            }
        }
    }
    
    // Remove from recursion stack when backtracking
    recStack[vertex] = false;
    return false;
}
                                

Cycle Detection for Undirected Graphs

                                    hasCycleUndirected() {
    const visited = {};
    
    // Helper function
    const hasCycleUtil = (vertex, parent) => {
        // Mark current node as visited
        visited[vertex] = true;
        
        // Visit all adjacent vertices
        for (let neighbor of this.adjacencyList[vertex]) {
            // If neighbor is not visited, recursively check
            if (!visited[neighbor]) {
                if (hasCycleUtil(neighbor, vertex)) {
                    return true;
                }
            } 
            // If neighbor is visited and not the parent,
            // then there is a cycle
            else if (neighbor !== parent) {
                return true;
            }
        }
        return false;
    };
    
    // Check all vertices (for disconnected graphs)
    for (let vertex in this.adjacencyList) {
        if (!visited[vertex]) {
            if (hasCycleUtil(vertex, null)) {
                return true;
            }
        }
    }
    
    return false;
}
                                

Example Usage

                                // Create a directed graph
const 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
console.log(graph.hasCycle());  // Output: true

// Visualize the graph structure
console.log(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 {
    constructor() {
        this.adjacencyList = {};
    }

    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) {
            this.adjacencyList[vertex] = [];
        }
    }

    addEdge(v1, v2, directed = true) {
        this.adjacencyList[v1].push(v2);
        if (!directed) {
            this.adjacencyList[v2].push(v1);
        }
    }
    
    // Implement cycle detection for directed graphs
    hasCycleDirected() {
        // Your code here
    }
    
    // Implement cycle detection for undirected graphs
    hasCycleUndirected() {
        // Your code here
    }
}
                            

Testing Your Solution

                                // Create a directed graph with a cycle
const directedGraph = new Graph();
directedGraph.addVertex('A');
directedGraph.addVertex('B');
directedGraph.addVertex('C');
directedGraph.addVertex('D');
directedGraph.addEdge('A', 'B');
directedGraph.addEdge('B', 'C');
directedGraph.addEdge('C', 'D');
directedGraph.addEdge('D', 'B'); // Creates a cycle B → C → D → B
console.log(directedGraph.hasCycleDirected()); // Should return true

// Create an undirected graph with a cycle
const 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
console.log(undirectedGraph.hasCycleUndirected()); // Should return true
                            