Cycle Detection in Graphs

Cycle detection is the process of determining whether a graph contains a cycle - a path that starts and ends at the same vertex. Detecting cycles is a fundamental graph problem and is critical in areas such as dependency resolution, deadlock detection, scheduling, and graph validation.

The approach to cycle detection depends on whether the graph is undirected or directed.

What Is a Cycle?

A cycle exists if you can start at a vertex, follow a sequence of edges, and return to the same vertex without retracing edges.

Example:

A --- B
|     |
D --- C

This graph contains a cycle: A → B → C → D → A.

Why Cycle Detection Matters

Cycle detection is used to:

• Detect circular dependencies (build systems, package managers)
• Identify deadlocks
• Validate trees (trees must be acyclic)
• Check correctness of directed acyclic graphs (DAGs)

Cycle Detection in Undirected Graphs

Key Idea

In an undirected graph, a cycle exists if:

• During DFS, we visit an already visited node
• That node is not the parent of the current node

Algorithm (Undirected Graph)

1. Start DFS from each unvisited vertex
2. Track the parent of each vertex
3. If a visited neighbor is encountered that is not the parent → cycle found

Rust Implementation (Undirected Graph)

use std::collections::{HashMap, HashSet};

type Graph = HashMap<i32, Vec<i32>>;

pub fn has_cycle_undirected(graph: &Graph) -> bool {
    let mut visited = HashSet::new();

    for &node in graph.keys() {
        if !visited.contains(&node) {
            if dfs(graph, node, -1, &mut visited) {
                return true;
            }
        }
    }

    false
}

fn dfs(
    graph: &Graph,
    node: i32,
    parent: i32,
    visited: &mut HashSet<i32>,
) -> bool {
    visited.insert(node);

    if let Some(neighbors) = graph.get(&node) {
        for &neighbor in neighbors {
            if !visited.contains(&neighbor) {
                if dfs(graph, neighbor, node, visited) {
                    return true;
                }
            } else if neighbor != parent {
                return true;
            }
        }
    }

    false
}

Example Usage (Undirected)

fn main() {
    let mut graph: Graph = HashMap::new();

    graph.insert(1, vec![2, 3]);
    graph.insert(2, vec![1, 3]);
    graph.insert(3, vec![1, 2]);

    println!("Has cycle? {}", has_cycle_undirected(&graph));
}

Output:

Has cycle? true

Cycle Detection in Directed Graphs

Cycle detection in directed graphs is different because edge direction matters.

Key Idea

A cycle exists if, during DFS, we encounter a node that is:

• Already in the current recursion stack

Algorithm (Directed Graph)

1. Track visited vertices
2. Track vertices in the recursion stack
3. If DFS reaches a vertex already in the stack → cycle found

Rust Implementation (Directed Graph)

use std::collections::{HashMap, HashSet};

type Graph = HashMap<i32, Vec<i32>>;

pub fn has_cycle_directed(graph: &Graph) -> bool {
    let mut visited = HashSet::new();
    let mut stack = HashSet::new();

    for &node in graph.keys() {
        if !visited.contains(&node) {
            if dfs(graph, node, &mut visited, &mut stack) {
                return true;
            }
        }
    }

    false
}

fn dfs(
    graph: &Graph,
    node: i32,
    visited: &mut HashSet<i32>,
    stack: &mut HashSet<i32>,
) -> bool {
    visited.insert(node);
    stack.insert(node);

    if let Some(neighbors) = graph.get(&node) {
        for &neighbor in neighbors {
            if !visited.contains(&neighbor) {
                if dfs(graph, neighbor, visited, stack) {
                    return true;
                }
            } else if stack.contains(&neighbor) {
                return true;
            }
        }
    }

    stack.remove(&node);
    false
}

Example Usage (Directed)

fn main() {
    let mut graph: Graph = HashMap::new();

    graph.insert(1, vec![2]);
    graph.insert(2, vec![3]);
    graph.insert(3, vec![1]); // cycle

    println!("Has cycle? {}", has_cycle_directed(&graph));
}

Output:

Has cycle? true

Time and Space Complexity

Time Complexity

Space Complexity

Summary

• Cycle detection strategy depends on graph type
• Undirected graphs use parent tracking
• Directed graphs use a recursion stack
• DFS is the most common approach

Playground Links

Rust - Cycle Detection (Undirected)

Rust - Cycle Detection (Directed)