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.

Practice

1. What does cycle detection in a directed graph help us find?

easy

A. Whether there is a path that starts and ends at the same node following edge directions

B. The shortest path between two nodes

C. The total number of nodes in the graph

D. The maximum degree of any node

Solution

1. Step 1: Understand cycle in directed graph

   A cycle means a path that starts and ends at the same node following the direction of edges.

2. Step 2: Identify what cycle detection finds

   Cycle detection checks if such a path exists in the graph.

3. Final Answer:

   Whether there is a path that starts and ends at the same node following edge directions -> Option A

4. Quick Check:

   Cycle detection = path starting and ending at same node [OK]

Hint: Cycle means path loops back to start following edges [OK]

Common Mistakes:

• Confusing cycle with shortest path
• Thinking cycle ignores edge directions
• Mixing cycle detection with counting nodes

2. Which of the following is the correct way to declare a visited array for cycle detection in C for a graph with n nodes?

easy

A. int visited = new int[n];

B. int visited[n] = {0};

C. int visited[] = {0};

D. int visited[n];

Solution

1. Step 1: Understand array declaration in C

   In C, to declare an array of size n, use int visited[n]; but it is uninitialized.

2. Step 2: Initialize array to zero

   To initialize all elements to zero, use int visited[n] = {0}; which sets all to zero.

3. Final Answer:

   int visited[n] = {0}; -> Option B

4. Quick Check:

   Array declaration with zero init = int visited[n] = {0}; [OK]

Hint: Use int arr[n] = {0} to initialize all zeros in C [OK]

Common Mistakes:

• Using 'new' keyword which is C++ not C
• Declaring array without size
• Incorrect initialization syntax

3. Consider the following C code snippet for cycle detection in a directed graph using DFS. What will be the output?

void dfs(int node, int visited[], int recStack[], int graph[][3]) {
    visited[node] = 1;
    recStack[node] = 1;
    for (int i = 0; i < 3; i++) {
        int adj = graph[node][i];
        if (adj == -1) continue;
        if (!visited[adj]) dfs(adj, visited, recStack, graph);
        else if (recStack[adj]) printf("Cycle detected\n");
    }
    recStack[node] = 0;
}

int main() {
    int graph[3][3] = {{1, -1, -1}, {2, -1, -1}, {0, -1, -1}};
    int visited[3] = {0}, recStack[3] = {0};
    dfs(0, visited, recStack, graph);
    return 0;
}

medium

A. No output

B. Infinite loop

C. Segmentation fault

D. Cycle detected

Solution

1. Step 1: Analyze graph edges

   Graph edges: 0->1, 1->2, 2->0 form a cycle.

2. Step 2: Trace DFS calls and cycle detection

   DFS visits 0, then 1, then 2. When 2 tries to visit 0 again which is in recursion stack, it prints "Cycle detected".

3. Final Answer:

   Cycle detected -> Option D

4. Quick Check:

   Cycle in graph triggers print "Cycle detected" [OK]

Hint: Cycle prints when node revisited in recursion stack [OK]

Common Mistakes:

• Ignoring recursion stack for cycle detection
• Assuming no output means no cycle
• Confusing visited and recursion stack arrays

4. The following code attempts to detect a cycle in a directed graph but does not work correctly. What is the main error?

void dfs(int node, int visited[], int graph[][3]) {
    visited[node] = 1;
    for (int i = 0; i < 3; i++) {
        int adj = graph[node][i];
        if (adj == -1) continue;
        if (!visited[adj]) dfs(adj, visited, graph);
        else printf("Cycle detected\n");
    }
}

int main() {
    int graph[3][3] = {{1, -1, -1}, {2, -1, -1}, {0, -1, -1}};
    int visited[3] = {0};
    dfs(0, visited, graph);
    return 0;
}

medium

A. Graph adjacency matrix is incorrect

B. Visited array is not initialized

C. Missing recursion stack to track nodes in current path

D. DFS function missing return type

Solution

1. Step 1: Understand cycle detection logic

   Cycle detection in directed graph needs to track nodes in current recursion path using a recursion stack.

2. Step 2: Identify missing recursion stack

   This code only uses visited array, so it cannot distinguish back edges causing cycles from cross edges.

3. Final Answer:

   Missing recursion stack to track nodes in current path -> Option C

4. Quick Check:

   Recursion stack needed for correct cycle detection [OK]

Hint: Use recursion stack to detect back edges in DFS [OK]

Common Mistakes:

• Assuming visited array alone detects cycles
• Ignoring need to track current DFS path
• Confusing undirected and directed cycle detection

5. You have a directed graph represented as adjacency lists:

0: [1]
1: [2]
2: [3, 4]
3: [1]
4: []

Which nodes are part of a cycle detected by DFS cycle detection algorithm?

hard

A. Nodes 1, 2, 3

B. Nodes 0, 1, 4

C. Nodes 0, 2, 4

D. Nodes 3, 4

Solution

1. Step 1: Trace the graph edges

   Edges: 0->1, 1->2, 2->3 and 2->4, 3->1.

2. Step 2: Identify cycle nodes

   Cycle is 1->2->3->1. Nodes 1, 2, 3 form the cycle.

3. Final Answer:

   Nodes 1, 2, 3 -> Option A

4. Quick Check:

   Cycle nodes = 1, 2, 3 [OK]

Hint: Follow edges to find loops including nodes [OK]

Common Mistakes:

• Including nodes not in cycle like 0 or 4
• Missing node 3 in cycle
• Confusing cycle with path