Why Cycle Detection in Directed Graph in DSA C#?

The Big Idea

What if your project plan is stuck in an invisible loop you can't see?

The Scenario

Imagine you are managing tasks where some tasks depend on others to be done first. You try to check manually if there is a loop in these dependencies, like Task A needs Task B, and Task B needs Task A. This manual check becomes confusing and slow as the number of tasks grows.

The Problem

Manually checking for loops in task dependencies is slow and error-prone because you have to remember all the paths and connections. It's easy to miss a cycle or get stuck in an endless loop yourself. This makes planning and scheduling very difficult.

The Solution

Cycle Detection in Directed Graphs uses a smart way to track which tasks are currently being checked and which are already done. It quickly finds if a cycle exists by following the paths and marking tasks. This saves time and avoids mistakes.

Before vs After

✗ Before

bool HasCycle(List<Task> tasks) {
  foreach (var task in tasks) {
    if (CheckCycleManually(task)) return true;
  }
  return false;
}

✓ After

bool HasCycle(Graph graph) {
  bool[] visited = new bool[graph.Size];
  bool[] recursionStack = new bool[graph.Size];
  for (int i = 0; i < graph.Size; i++) {
    if (DetectCycle(i, visited, recursionStack)) return true;
  }
  return false;
}

What It Enables

This concept enables automatic and fast detection of loops in complex task dependencies or workflows, preventing impossible schedules and errors.

Real Life Example

In project management software, cycle detection helps ensure that task dependencies do not create impossible loops, so the project plan can be executed smoothly.

Key Takeaways

Manual cycle checks are slow and unreliable for many tasks.

Cycle detection uses tracking arrays to find loops efficiently.

It helps prevent scheduling errors in task or workflow management.

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