Cycle Detection in Directed Graph in DSA C#

Mental Model

We want to find if there is a loop in the graph where you can start at a node and follow edges to come back to the same node.

Analogy: Imagine a maze with one-way paths. If you can walk through the maze and return to where you started by following the arrows, there is a cycle.

Graph nodes with arrows showing direction:
1 -> 2 -> 3
↑         ↓
└─────────

Dry Run Walkthrough

Input: Graph with edges: 1->2, 2->3, 3->1 (cycle exists)

Goal: Detect if the graph contains a cycle

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: Continue exploring neighbors to find cycle

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

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

Why: Keep exploring deeper to detect cycle

Step 4: From node 3, move to node 1 which is already visiting

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

Why: Finding a node currently being visited means a cycle

Step 5: Cycle detected, stop search

Cycle found involving nodes 1, 2, 3

Why: Cycle exists because we returned to a visiting node

Result:

Cycle detected: true

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    private readonly int V;
    private readonly List<int>[] adj;

    public Graph(int vertices) {
        V = vertices;
        adj = new List<int>[V + 1];
        for (int i = 0; i <= V; i++) {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int u, int v) {
        adj[u].Add(v);
    }

    private bool DFS(int node, bool[] visited, bool[] recStack) {
        visited[node] = true; // mark node as visited
        recStack[node] = true; // mark node as in recursion stack

        foreach (int neighbor in adj[node]) {
            if (!visited[neighbor]) {
                if (DFS(neighbor, visited, recStack)) {
                    return true; // cycle found in deeper call
                }
            } else if (recStack[neighbor]) {
                return true; // cycle found due to back edge
            }
        }

        recStack[node] = false; // remove node from recursion stack
        return false; // no cycle found from this node
    }

    public bool HasCycle() {
        bool[] visited = new bool[V + 1];
        bool[] recStack = new bool[V + 1];

        for (int i = 1; i <= V; i++) {
            if (!visited[i]) {
                if (DFS(i, visited, recStack)) {
                    return true; // cycle detected
                }
            }
        }
        return false; // no cycle in graph
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(3);
        g.AddEdge(1, 2);
        g.AddEdge(2, 3);
        g.AddEdge(3, 1);

        Console.WriteLine(g.HasCycle());
    }
}

visited[node] = true; // mark node as visited recStack[node] = true; // mark node as in recursion stack

Mark current node as visited and add to recursion stack to track path

if (!visited[neighbor]) { if (DFS(neighbor, visited, recStack)) { return true; // cycle found in deeper call } } else if (recStack[neighbor]) { return true; // cycle found due to back edge }

If neighbor not visited, explore it; if neighbor is in recursion stack, cycle detected

recStack[node] = false; // remove node from recursion stack

Remove node from recursion stack after exploring all neighbors

for (int i = 1; i <= V; i++) { if (!visited[i]) { if (DFS(i, visited, recStack)) { return true; // cycle detected } } }

Check all nodes to cover disconnected graph parts

Output

True

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

vs Alternative: Compared to using Kahn's algorithm (topological sort), DFS is simpler to implement but both have similar time complexity

Edge Cases

Empty graph (no nodes)

No cycle detected because graph is empty

DSA C#

for (int i = 1; i <= V; i++) { if (!visited[i]) { ... } }

Graph with single node and no edges

No cycle detected because no edges to form cycle

DSA C#

for (int i = 1; i <= V; i++) { if (!visited[i]) { ... } }

Graph with multiple disconnected components

Cycle detection runs on each component independently

DSA C#

for (int i = 1; i <= V; i++) { if (!visited[i]) { ... } }

When to Use This Pattern

When you see a problem asking if a directed graph has loops or cycles, use DFS with recursion stack tracking to detect cycles efficiently.

Common Mistakes

Mistake: Not using a recursion stack to track nodes currently in the path, causing false negatives.
Fix: Use a separate recursion stack array to mark nodes in the current DFS path.

Mistake: Marking nodes as visited only after full DFS call, missing cycles.
Fix: Mark nodes as visited and in recursion stack immediately when DFS visits them.

Summary

Detects if a directed graph contains a cycle by DFS traversal with recursion stack tracking.

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

The key insight is that revisiting a node currently in the recursion stack means a cycle exists.

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 vertex following edge directions

B. The shortest path between two vertices

C. The total number of vertices in the graph

D. The maximum degree of any vertex

Solution

1. Step 1: Understand cycle in directed graph

   A cycle means a path that starts and ends at the same vertex 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 vertex following edge directions -> Option A

4. Quick Check:

   Cycle detection = finding directed cycles [OK]

Hint: Cycle means path loops back following edge directions [OK]

Common Mistakes:

• Confusing cycle with shortest path
• Ignoring edge directions
• Thinking cycle means any repeated vertex

2. Which C# data structure is commonly used to keep track of nodes currently in the recursion stack during DFS for cycle detection?

easy

A. Queue

B. Stack or boolean array to mark recursion stack

C. Dictionary

D. LinkedList

Solution

1. Step 1: Recall DFS cycle detection method

   During DFS, we track nodes in the current recursion path to detect back edges.

2. Step 2: Identify data structure used

   This is done using a stack or a boolean array marking nodes in the recursion stack.

3. Final Answer:

   Stack or boolean array to mark recursion stack -> Option B

4. Quick Check:

   Recursion stack tracking = Stack/boolean array [OK]

Hint: Use stack or boolean array to track recursion path [OK]

Common Mistakes:

• Using queue which is FIFO, not suitable for recursion stack
• Confusing dictionary with recursion tracking
• Not marking nodes currently in recursion

3. What will be the output of the following C# code snippet detecting cycle in a directed graph?

var graph = new Dictionary<int, List<int>> {
  {1, new List<int>{2}},
  {2, new List<int>{3}},
  {3, new List<int>{1}}
};
bool HasCycle(int node, HashSet<int> visited, HashSet<int> recStack) {
  if (!visited.Contains(node)) {
    visited.Add(node);
    recStack.Add(node);
    foreach (var neighbor in graph[node]) {
      if (!visited.Contains(neighbor) && HasCycle(neighbor, visited, recStack))
        return true;
      else if (recStack.Contains(neighbor))
        return true;
    }
  }
  recStack.Remove(node);
  return false;
}

var visited = new HashSet<int>();
var recStack = new HashSet<int>();
Console.WriteLine(HasCycle(1, visited, recStack));

medium

A. False

B. Compilation error

C. Runtime exception

D. True

Solution

1. Step 1: Analyze graph edges

   The graph has edges 1->2, 2->3, and 3->1 forming a cycle.

2. Step 2: Trace DFS cycle detection

   Starting at node 1, recursion visits 2, then 3, then back to 1 which is in recursion stack, so cycle detected.

3. Final Answer:

   True -> Option D

4. Quick Check:

   Cycle exists in graph = True [OK]

Hint: Cycle if recursion stack revisits a node [OK]

Common Mistakes:

• Ignoring recursion stack check
• Assuming no cycle because graph looks simple
• Confusing visited set with recursion stack

4. Identify the bug in this C# DFS cycle detection code snippet:

bool HasCycle(int node, HashSet<int> visited, HashSet<int> recStack) {
  visited.Add(node);
  foreach (var neighbor in graph[node]) {
    if (!visited.Contains(neighbor) && HasCycle(neighbor, visited, recStack))
      return true;
    else if (recStack.Contains(neighbor))
      return true;
  }
  recStack.Remove(node);
  return false;
}

medium

A. Missing removing node from visited after recursion

B. Incorrect use of HashSet instead of List

C. Missing adding node to recStack before recursion

D. No bug, code is correct

Solution

1. Step 1: Check recursion stack usage

   Node must be added to recStack before exploring neighbors to detect back edges.

2. Step 2: Identify missing step

   Code adds node to visited but never adds to recStack before recursion, so cycle detection fails.

3. Final Answer:

   Missing adding node to recStack before recursion -> Option C

4. Quick Check:

   recStack update missing = bug [OK]

Hint: Always add node to recursion stack before DFS call [OK]

Common Mistakes:

• Forgetting to add node to recursion stack
• Removing node from visited incorrectly
• Confusing visited and recursion stack roles

5. Given a directed graph represented as adjacency list:

var graph = new Dictionary<int, List<int>> {
  {1, new List<int>{2, 3}},
  {2, new List<int>{4}},
  {3, new List<int>{4}},
  {4, new List<int>{5}},
  {5, new List<int>{3}}
};

Which nodes form a cycle in this graph?

hard

A. Nodes 3, 4, 5

B. Nodes 1, 2, 4

C. Nodes 2, 3, 5

D. No cycle exists

Solution

1. Step 1: Trace edges to find cycle

   Edges: 3->4, 4->5, 5->3 form a cycle among nodes 3, 4, 5.

2. Step 2: Confirm cycle presence

   Starting at 3, path 3->4->5->3 loops back, confirming cycle.

3. Final Answer:

   Nodes 3, 4, 5 -> Option A

4. Quick Check:

   Cycle nodes = 3,4,5 [OK]

Hint: Follow edges to see if path loops back to start [OK]

Common Mistakes:

• Ignoring edge 5->3 that closes cycle
• Assuming no cycle because 1 and 2 are acyclic
• Confusing cycle nodes with all connected nodes