Data Structures and Algorithms in C (DSA)

📘 Chapter: Cycle Detection in Graphs

A cycle in a graph is a path that starts and ends at the same vertex, visiting other vertices and edges along the way. Detecting cycles is a fundamental problem in graph theory with numerous practical applications. For instance, in a task dependency graph, a cycle indicates an impossible set of prerequisites. In a network, a cycle might represent redundant paths. Understanding how to find these loops is crucial for validating graph properties and solving complex problems.

🤔 Why Detect Cycles?

• Topological Sort: A graph must be a Directed Acyclic Graph (DAG) to perform a topological sort. Cycle detection is the first step to validate if a topological sort is even possible.
• Deadlock Detection: In operating systems, resource allocation graphs can form cycles, indicating a deadlock.
• Data Validation: Ensuring no circular dependencies in systems like course prerequisites, build systems, or database foreign keys.
• Network Routing: Identifying redundant paths or loops in network configurations.
• Graph Algorithms: Many graph algorithms (e.g., some shortest path variants) rely on the absence of negative cycles.

🔄 Cycle Detection in Undirected Graphs

In an undirected graph, a cycle exists if, during a traversal (like DFS or BFS), we encounter a visited vertex that is not the direct parent of the current vertex in the traversal tree.

Using DFS for Undirected Graphs:

The most common approach for undirected graphs is a modified DFS. We keep track of visited nodes and the parent of the current node in the DFS tree.

1. Maintain a `visited` array (or set) initialized to `false`.
2. For each unvisited vertex `u` in the graph:
   • Start a DFS traversal from `u`, passing its `parent` as an argument (initially -1 or a sentinel value).
3. Inside the DFS function `dfs(u, parent_u)`:
   • Mark `u` as visited.
   • For each neighbor `v` of `u`:
     • If `v` is not visited: Recursively call `dfs(v, u)`. If this call returns `true` (cycle found), propagate `true`.
     • Else if `v` is visited AND `v` is not `parent_u`: A cycle is detected! This means we found a back-edge to an already visited node that isn't our immediate parent. Return `true`.
4. If the DFS completes without finding such a condition, no cycle exists from that component.

// Conceptual C++ for Cycle Detection in Undirected Graph using DFS
bool dfs_undirected_cycle_util(int u, int parent_u,
                               const vector<vector<int>>& adj,
                               vector<bool>& visited) {
    visited[u] = true;

    for (int v : adj[u]) {
        if (!visited[v]) { // If 'v' is not visited, recurse
            if (dfs_undirected_cycle_util(v, u, adj, visited)) {
                return true; // Cycle found in subtree
            }
        }
        // If 'v' is visited AND 'v' is not the parent of 'u'
        // then there is a cycle
        else if (v != parent_u) {
            return true;
        }
    }
    return false; // No cycle found in this path
}

bool detect_cycle_undirected(int V, const vector<vector<int>>& adj) {
    vector<bool> visited(V, false);
    for (int i = 0; i < V; ++i) {
        if (!visited[i]) {
            if (dfs_undirected_cycle_util(i, -1, adj, visited)) {
                return true; // Cycle found in this component
            }
        }
    }
    return false; // No cycle in the entire graph
}
  

Time Complexity: $O(V + E)$ (standard DFS traversal).
Space Complexity: $O(V)$ for the recursion stack and visited array.

➡️ Cycle Detection in Directed Graphs

In a directed graph, a cycle occurs if, during a DFS traversal, we encounter a visited vertex that is currently in the "recursion stack" (i.e., it's an ancestor of the current node in the DFS tree and has not yet finished processing all its descendants).

Using DFS for Directed Graphs:

This approach uses two arrays (or sets) to keep track of visited nodes:

• `visited[]`: Marks nodes that have been visited at least once.
• `recursionStack[]`: Marks nodes that are currently in the recursion stack (i.e., part of the current DFS path).

1. Initialize `visited[]` and `recursionStack[]` to `false`.
2. For each unvisited vertex `u` in the graph:
   • Start a DFS traversal from `u`.
3. Inside the DFS function `dfs(u)`:
   • Mark `u` as `visited[u] = true` and `recursionStack[u] = true`.
   • For each neighbor `v` of `u`:
     • If `v` is not visited: Recursively call `dfs(v)`. If this call returns `true` (cycle found), propagate `true`.
     • Else if `recursionStack[v]` is `true`: A cycle is detected! This means we found a back-edge to an ancestor in the current path. Return `true`.
   • After processing all neighbors, set `recursionStack[u] = false` (remove from current path). Return `false` (no cycle found from this node).

// Conceptual C++ for Cycle Detection in Directed Graph using DFS
bool dfs_directed_cycle_util(int u,
                             const vector<vector<int>>& adj,
                             vector<bool>& visited,
                             vector<bool>& recursionStack) {
    visited[u] = true;
    recursionStack[u] = true;

    for (int v : adj[u]) {
        if (!visited[v]) { // If 'v' is not visited, recurse
            if (dfs_directed_cycle_util(v, adj, visited, recursionStack)) {
                return true; // Cycle found in subtree
            }
        }
        // If 'v' is visited AND 'v' is in recursionStack, then a cycle exists
        else if (recursionStack[v]) {
            return true;
        }
    }
    recursionStack[u] = false; // Remove 'u' from recursion stack
    return false; // No cycle found from this path
}

bool detect_cycle_directed(int V, const vector<vector<int>>& adj) {
    vector<bool> visited(V, false);
    vector<bool> recursionStack(V, false); // To detect back-edges

    for (int i = 0; i < V; ++i) {
        if (!visited[i]) {
            if (dfs_directed_cycle_util(i, adj, visited, recursionStack)) {
                return true; // Cycle found in this component
            }
        }
    }
    return false; // No cycle in the entire graph
}
  

Time Complexity: $O(V + E)$ (standard DFS traversal).
Space Complexity: $O(V)$ for the recursion stack and visited arrays.

Using Kahn's Algorithm (BFS-based) for Directed Graphs:

As discussed in the Topological Sort chapter, Kahn's algorithm inherently detects cycles. If the number of vertices processed (added to the topological order) is less than the total number of vertices in the graph, it means a cycle exists.

// Conceptual C++ for Cycle Detection in Directed Graph using Kahn's Algorithm
bool detect_cycle_kahn(int V, const vector<vector<int>>& adj) {
    vector<int> in_degree(V, 0);
    for (int i = 0; i < V; ++i) {
        for (int neighbor : adj[i]) {
            in_degree[neighbor]++;
        }
    }

    queue<int> q;
    for (int i = 0; i < V; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    int count_visited_nodes = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        count_visited_nodes++;

        for (int v : adj[u]) {
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }
    }

    return (count_visited_nodes != V); // If not all nodes visited, a cycle exists
}
  

Time Complexity: $O(V + E)$.
Space Complexity: $O(V)$.

📌 Real-Life Example (UdaanPath)

Cycle detection is a crucial validation step in many systems, especially those dealing with dependencies:

• Course Prerequisite Validation: The most direct application. If a curriculum has Course A requiring B, B requiring C, and C requiring A, this is an impossible cycle. UdaanPath's course management system would use cycle detection to prevent such invalid course structures from being created, ensuring students can actually complete their degrees/certifications.
• Task Management & Project Planning: For a project management feature where users define tasks and their dependencies, cycle detection ensures that no task depends on itself directly or indirectly. This prevents infinite loops in project plans.
• Build System Dependencies: In a software development environment, if different code modules depend on each other for compilation, a cycle in the dependency graph would cause a build failure. Cycle detection helps maintain a healthy build system.
• Database Integrity (Foreign Keys): While databases handle this internally, conceptually, if you have complex foreign key relationships, a cycle could indicate a problem if not handled correctly (e.g., circular deletion dependencies).
• Circular References in Content: If content pieces can link to each other, detecting cycles could prevent users from getting stuck in an infinite loop of linked articles or tutorials.

✅ Summary: Breaking the Loop

• A cycle is a path in a graph that starts and ends at the same vertex.
• Undirected Graphs: Cycles are detected using DFS by checking for back-edges to visited nodes that are not the immediate parent.
• Directed Graphs: Cycles are detected using DFS by checking for back-edges to nodes currently in the recursion stack. Alternatively, Kahn's algorithm (topological sort) can detect cycles if not all nodes can be processed.
• All methods typically have $O(V + E)$ time complexity and $O(V)$ space complexity.
• Cycle detection is vital for validating dependencies, ensuring data integrity, and enabling algorithms that require Directed Acyclic Graphs (DAGs).

📤 Coming Next: Bridges and Articulation Points

Continuing our deep dive into graph connectivity, our next chapter will uncover critical structural elements: Bridges and Articulation Points (or Cut Vertices). These are single points of failure in a graph – edges or vertices whose removal would increase the number of connected components. Understanding them is vital for designing robust networks and identifying vulnerabilities.