Kahn's Algorithm for Detecting Cycles in Directed Graphs

Below is the implementation of Kahn's algorithm to detect cycles in a directed graph.

 internal class KahnsAlgorithm
 {

     Dictionary<int, List<int>> keyValuePairs = new Dictionary<int, List<int>>();
     int V;
     public KahnsAlgorithm(int v)
     {
         V = v;
         for (int i = 0; i < V; i++)
         {
             keyValuePairs[i] = new List<int>();
         }
     }

    public void AddEdge(int s, int d)
     {
         keyValuePairs[s] = keyValuePairs.TryGetValue(s, out List<int> edges) ? edges : new List<int>();
         keyValuePairs[s].Add(d);
     }

    public bool IsCyclic()
     {
         int[] inDegree = new int[V];

         Queue<int> queue = new Queue<int>();
         int visited = 0;

         foreach (var item in  keyValuePairs.SelectMany(items => items.Value))
         {
                 inDegree[item]++;
         }

         for(int i = 0; i < V; i++) {
             if (inDegree[i] == 0)
               queue.Enqueue(i); 
         }

         while(queue.Count > 0)
         {
             int u = queue.Dequeue();
             visited++;

             foreach(var item in keyValuePairs[u])
             {
                 inDegree[item]--;

                 if (inDegree[item] == 0)
                     queue.Enqueue(item); 
             }
         }
         return visited != V;
     }

 }

This code snippet defines an internal class named KahnsAlgorithm which represents a directed graph and provides methods to add edges to the graph and check if the graph contains a cycle.

The class has two fields

• keyValuePairs: A Dictionary<int, List<int>> that stores the adjacency list representation of the graph. Each key in the dictionary represents a vertex in the graph, and its associated value is a list of vertices that are adjacent to it.
• V: An int that stores the number of vertices in the graph.

internal class KahnsAlgorithm
{
    Dictionary<int, List<int>> keyValuePairs = new Dictionary<int, List<int>>();
    int V;
    public KahnsAlgorithm(int v)
    {
        V = v;
        for (int i = 0; i < V; i++)
        {
            keyValuePairs[i] = new List<int>();
        }
    }

The class has a constructor that takes an int parameter v representing the number of vertices in the graph. The constructor initializes the V field with the value of v and creates an entry in the keyValuePairs dictionary for each vertex in the graph.

public void AddEdge(int s, int d)
{
    keyValuePairs[s] = keyValuePairs.TryGetValue(s, out List<int> edges) ? edges : new List<int>();
    keyValuePairs[s].Add(d);
}

This method takes two int parameters, s, and d, representing the source and destination vertices of an edge, respectively. The method adds an edge from vertex s to vertex d in the graph by adding d to the list of adjacent vertices for vertex s in the keyValuePairs dictionary. If vertex s is not already present in the dictionary, a new entry is added with key s and value as a new list containing vertex d.

public bool IsCyclic()
{
    int[] inDegree = new int[V];

    Queue<int> queue = new Queue<int>();
    int visited = 0;

    foreach (var item in  keyValuePairs.SelectMany(items => items.Value))
    {
            inDegree[item]++;
    }

    for(int i = 0; i < V; i++) {
        if (inDegree[i] == 0)
          queue.Enqueue(i); 
    }

    while(queue.Count > 0)
    {
        int u = queue.Dequeue();
        visited++;

        foreach(var item in keyValuePairs[u])
        {
            inDegree[item]--;

            if (inDegree[item] == 0)
                queue.Enqueue(item); 
        }
    }
    return visited != V;
}

This method returns a bool indicating whether or not the graph contains a cycle. The method uses Kahn’s algorithm to perform topological sorting on the graph and detect if it contains a cycle. The algorithm works by repeatedly removing vertices with in-degree 0 from the graph until either all vertices have been removed (in which case the graph is acyclic) or there are no more vertices with in-degree 0 (in which case the graph contains a cycle).

• Time Complexity: O(V + E)
• Space Complexity: O(V)