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:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, v1, v2):
        self.adjacency_list[v1].append(v2)
        # For undirected graphs, add:
        # self.adjacency_list[v2].append(v1)

                                    

Step 2: Cycle Detection Method

                                        def has_cycle(self):
    visited = {}
    rec_stack = {}

    # Check all vertices (for disconnected graphs)
    for vertex in self.adjacency_list:
        if self.has_cycle_util(vertex, visited, rec_stack):
            return True
    return False
                                    

Step 3: Helper Method for Cycle Detection

                                    def has_cycle_util(self, vertex, visited, rec_stack):
    # If not visited, mark as visited
    if vertex not in visited:
        visited[vertex] = True
        rec_stack[vertex] = True  # Add to recursion stack

        # Check all neighbors
        for neighbor in self.adjacency_list[vertex]:
            # If neighbor not visited and has cycle
            if neighbor not in visited and self.has_cycle_util(neighbor, visited, rec_stack):
                return True
            # If neighbor is in recursion stack, cycle found
            elif neighbor in rec_stack and rec_stack[neighbor]:
                return True
    
    # Remove from recursion stack when backtracking
    rec_stack[vertex] = False
    return False
                                

Cycle Detection for Undirected Graphs

                                    def has_cycle_undirected(self):
    visited = {}
    
    # Helper function
    def has_cycle_util(vertex, parent):
        # Mark current node as visited
        visited[vertex] = True
        
        # Visit all adjacent vertices
        for neighbor in self.adjacency_list[vertex]:
            # If neighbor is not visited, recursively check
            if neighbor not in visited:
                if has_cycle_util(neighbor, vertex):
                    return True
            # If neighbor is visited and not the parent,
            # then there is a cycle
            elif neighbor != parent:
                return True
        return False
    
    # Check all vertices (for disconnected graphs)
    for vertex in self.adjacency_list:
        if vertex not in visited:
            if has_cycle_util(vertex, None):
                return True
    
    return False
                                

Example Usage

                                # Create a directed graph
graph = Graph()

# Add vertices
graph.add_vertex("A")
graph.add_vertex("B")
graph.add_vertex("C")
graph.add_vertex("D")

# Add edges (directed)
graph.add_edge("A", "B")
graph.add_edge("B", "C")
graph.add_edge("C", "A") # Creates a cycle A -> B -> C -> A
graph.add_edge("D", "C")
# Check for cycles
print(graph.has_cycle())  # Output: True

# Visualize the graph structure
print(graph.adjacency_list)
#   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:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, v1, v2, directed=True):
        self.adjacency_list[v1].append(v2)
        if not directed:
            self.adjacency_list[v2].append(v1)
    
    # Implement cycle detection for directed graphs
    def has_cycle_directed(self):
        # Your code here
        pass
    
    # Implement cycle detection for undirected graphs
    def has_cycle_undirected(self):
        # Your code here
        pass

                            

Testing Your Solution

                                # Create a directed graph with a cycle
directed_graph = Graph()
directed_graph.add_vertex('A')
directed_graph.add_vertex('B')
directed_graph.add_vertex('C')
directed_graph.add_vertex('D')
directed_graph.add_edge('A', 'B')
directed_graph.add_edge('B', 'C')
directed_graph.add_edge('C', 'D')
directed_graph.add_edge('D', 'B') # Creates a cycle B → C → D → B
print(directed_graph.has_cycle_directed()) # Should return True

# Create an undirected graph with a cycle
undirected_graph = Graph()
undirected_graph.add_vertex('A')
undirected_graph.add_vertex('B')
undirected_graph.add_vertex('C')
undirected_graph.add_edge('A', 'B', False)
undirected_graph.add_edge('B', 'C', False)
undirected_graph.add_edge('C', 'A', False) # Creates a cycle A — B — C — A
print(undirected_graph.has_cycle_undirected()) # Should return True
                            