Cycle Detection in Directed Graph in DSA C

Mental Model

We want to find if there is a path that starts and ends at the same node following the direction of edges.

Analogy: Imagine a one-way street map where you want to check if you can start driving from a place and come back to it by following the one-way roads without reversing.

Graph nodes with arrows showing direction:

  1 -> 2 -> 3
       ↑    ↓
       5 ← 4

Here arrows show one-way roads between nodes.

Dry Run Walkthrough

Input: Graph with edges: 1->2, 2->3, 3->4, 4->5, 5->2

Goal: Detect if there is a cycle in the directed graph

Step 1: Start DFS from node 1, mark node 1 as visiting

Visiting: [1], Visited: []

Why: We begin exploring from node 1 to find cycles

Step 2: Move to node 2 from node 1, mark node 2 as visiting

Visiting: [1, 2], Visited: []

Why: Follow edge 1->2 to continue search

Step 3: Move to node 3 from node 2, mark node 3 as visiting

Visiting: [1, 2, 3], Visited: []

Why: Follow edge 2->3 to continue search

Step 4: Move to node 4 from node 3, mark node 4 as visiting

Visiting: [1, 2, 3, 4], Visited: []

Why: Follow edge 3->4 to continue search

Step 5: Move to node 5 from node 4, mark node 5 as visiting

Visiting: [1, 2, 3, 4, 5], Visited: []

Why: Follow edge 4->5 to continue search

Step 6: From node 5, try to move to node 2 which is already visiting

Visiting: [1, 2, 3, 4, 5], Visited: []

Why: Finding node 2 in visiting means a cycle exists

Step 7: Cycle detected, stop search

Cycle found involving nodes 2, 3, 4, 5

Why: Cycle means path leads back to a node still in current path

Result:

Cycle found: 2 -> 3 -> 4 -> 5 -> 2

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Graph represented as adjacency list
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* graph[MAX];
int visited[MAX];    // 0 = not visited, 1 = visiting, 2 = visited

// Create new adjacency list node
Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// Add edge from src to dest
void addEdge(int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph[src];
    graph[src] = newNode;
}

// DFS to detect cycle
int dfs(int v) {
    visited[v] = 1; // mark as visiting
    Node* temp = graph[v];
    while (temp != NULL) {
        int adj = temp->vertex;
        if (visited[adj] == 1) {
            // Found a node in current path => cycle
            return 1;
        }
        if (visited[adj] == 0) {
            if (dfs(adj)) {
                return 1;
            }
        }
        temp = temp->next;
    }
    visited[v] = 2; // mark as visited
    return 0;
}

int main() {
    // Initialize graph
    for (int i = 0; i < MAX; i++) {
        graph[i] = NULL;
        visited[i] = 0;
    }

    // Build graph from example
    addEdge(1, 2);
    addEdge(2, 3);
    addEdge(3, 4);
    addEdge(4, 5);
    addEdge(5, 2);

    int cycle_found = 0;
    for (int i = 1; i <= 5; i++) {
        if (visited[i] == 0) {
            if (dfs(i)) {
                cycle_found = 1;
                break;
            }
        }
    }

    if (cycle_found) {
        printf("Cycle found in the graph\n");
    } else {
        printf("No cycle in the graph\n");
    }

    return 0;
}

visited[v] = 1; // mark as visiting

Mark current node as visiting to track current path

if (visited[adj] == 1) { return 1; }

If adjacent node is visiting, cycle detected

if (visited[adj] == 0) { if (dfs(adj)) { return 1; } }

Recursively visit unvisited adjacent nodes

visited[v] = 2; // mark as visited

Mark node as fully visited after exploring all neighbors

if (dfs(i)) { cycle_found = 1; break; }

Start DFS from unvisited nodes to cover all graph parts

Output

Cycle found in the graph

Complexity Analysis

Time: O(V + E) because each node and edge is visited once during DFS

Space: O(V) for recursion stack and visited arrays to track nodes

vs Alternative: Compared to naive cycle detection by checking all paths which is exponential, DFS with visited states is efficient and linear

Edge Cases

Empty graph with no nodes

No cycle detected as there are no edges

DSA C

for (int i = 1; i <= 5; i++) { if (visited[i] == 0) { if (dfs(i)) {

Graph with single node and no edges

No cycle detected because no edges to form cycle

DSA C

for (int i = 1; i <= 5; i++) { if (visited[i] == 0) { if (dfs(i)) {

Graph with multiple disconnected components

DFS runs on each component to detect cycle in any part

DSA C

for (int i = 1; i <= 5; i++) { if (visited[i] == 0) { if (dfs(i)) {

When to Use This Pattern

When you see a problem asking if a directed graph has a loop or cycle, use DFS with visiting states to detect back edges indicating cycles.

Common Mistakes

Mistake: Marking nodes only as visited or not visited without a visiting state
Fix: Use three states: not visited, visiting (in current path), and visited to detect cycles correctly

Mistake: Not checking all disconnected components of the graph
Fix: Run DFS from every unvisited node to cover entire graph

Summary

Detects if a directed graph contains a cycle by tracking nodes in the current path during DFS.

Use when you need to find loops in directed graphs, such as dependency checks or scheduling.

The key insight is to mark nodes as visiting during DFS and detect if you revisit a visiting node, which means a cycle.