Cycle Detection in Directed Graph in DSA C# - Build from Scratch

Cycle Detection in Directed Graph

📖 Scenario: Imagine you are building a task manager app. Each task can depend on other tasks to be done first. You want to make sure there are no circular dependencies, which would make it impossible to finish the tasks.

🎯 Goal: You will create a program to detect if there is a cycle in a directed graph representing task dependencies. This will help prevent impossible task orders.

📋 What You'll Learn

Create a directed graph using a dictionary where keys are task names and values are lists of dependent tasks.

Create a helper dictionary to track the visit state of each task.

Implement a function to detect cycles using Depth-First Search (DFS) with recursion.

Print whether a cycle exists or not.

💡 Why This Matters

🌍 Real World

Detecting cycles in task dependencies helps prevent impossible schedules in project management tools.

💼 Career

Cycle detection is important in software engineering for dependency management, build systems, and detecting infinite loops.

1

Create the Directed Graph

Create a dictionary called graph with these exact entries: "A" points to ["B"], "B" points to ["C"], "C" points to ["A"], and "D" points to an empty list [].

DSA C#

# Your code here

Hint

Use a Dictionary<string, List<string>> to represent the graph. Each key is a task, and the value is a list of tasks it points to.

2

Create the Visit State Dictionary

Create a dictionary called visitState with keys "A", "B", "C", and "D", all set to 0. This will track if a task is unvisited (0), visiting (1), or visited (2).

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            { "A", new List { "B" } },
            { "B", new List { "C" } },
            { "C", new List { "A" } },
            { "D", new List() }
        };

        // Your code here
    }
}

Hint

Use a Dictionary<string, int> to keep track of each task's visit state.

3

Implement Cycle Detection Function

Add a static method called HasCycle that takes string node, Dictionary<string, List<string>> graph, and Dictionary<string, int> visitState. Use DFS to detect cycles: if visitState[node] is 1, return true; if 2, return false; mark 1 before recursion and 2 after. Return true if any neighbor causes a cycle.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            { "A", new List { "B" } },
            { "B", new List { "C" } },
            { "C", new List { "A" } },
            { "D", new List() }
        };

        Dictionary visitState = new Dictionary
        {
            { "A", 0 },
            { "B", 0 },
            { "C", 0 },
            { "D", 0 }
        };

        // Your code here
    }
}

Hint

Use recursion and the visitState dictionary to detect cycles. Mark nodes as visiting (1) when you start, and visited (2) when done.

4

Check and Print if Cycle Exists

Use a foreach loop with variable node over graph.Keys. For each node, if visitState[node] is 0 and HasCycle(node, graph, visitState) returns true, print "Cycle detected" and return. If no cycle found, print "No cycle detected".

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            { "A", new List { "B" } },
            { "B", new List { "C" } },
            { "C", new List { "A" } },
            { "D", new List() }
        };

        Dictionary visitState = new Dictionary
        {
            { "A", 0 },
            { "B", 0 },
            { "C", 0 },
            { "D", 0 }
        };

        static bool HasCycle(string node, Dictionary> graph, Dictionary visitState)
        {
            if (visitState[node] == 1) return true;
            if (visitState[node] == 2) return false;

            visitState[node] = 1;

            foreach (var neighbor in graph[node])
            {
                if (HasCycle(neighbor, graph, visitState))
                    return true;
            }

            visitState[node] = 2;
            return false;
        }

        // Your code here
    }
}

Hint

Check each node if unvisited. If HasCycle returns true, print "Cycle detected" and stop. Otherwise, print "No cycle detected".

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