Detect Cycle in a Directed Graph

The below code shows the implementation of the Detect Cycle in a Directed Graph.

internal class Detect_Cycle_in_a_Directed_Graph
{
    Dictionary<int, List<int>> keyValuePairs = new Dictionary<int, List<int>>();
    bool explored = false;

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

    public bool IsCyclic()
    {
        bool[] visited = new bool[keyValuePairs.Count];
        for (int i = 0; i < keyValuePairs.Count; i++)
        {
            if (!visited[i])
            {
                IsCyclicUtil(i, keyValuePairs, visited);
                if (explored)
                    return true;
            }
        }
        return false;
    }

    void IsCyclicUtil(int src, Dictionary<int, List<int>> keyValuePairs, bool[] visited)
    {
        visited[src] = true;
        foreach (var value in keyValuePairs[src])
        {
            if (visited[value])
            {
                explored = true;
                return;
            }
            IsCyclicUtil(value, keyValuePairs, visited);
        }
    }
}

• keyValuePairs: A Dictionary<int, List<int>> that represents the adjacency list of the graph. Each key in the dictionary is a node in the graph, and its value is a list of nodes that are adjacent to it.
• explored: A bool flag that indicates whether a cycle has been detected in the graph.
• AddEdge(int v, int w): A public method that adds an edge from node v to node w in the graph. It does this by adding w to the list of adjacent nodes for v in the keyValuePairs dictionary. If v is not already a key in the dictionary, it adds a new key-value pair with key v and value new List<int>().

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

• IsCyclic(): A public method that returns a bool indicating whether the graph contains a cycle. It does this by calling the private method IsCyclicUtil for each unvisited node in the graph. If any call to IsCyclicUtil sets the explored flag to true, it immediately returns true. Otherwise, it returns false.

  public bool IsCyclic()
  {
      bool[] visited = new bool[keyValuePairs.Count];
      for (int i = 0; i < keyValuePairs.Count; i++)
      {
          if (!visited[i])
          {
              IsCyclicUtil(i, keyValuePairs, visited);
              if (explored)
                  return true;
          }
      }
      return false;
  }
  

• IsCyclicUtil(int src, Dictionary<int, List<int>> keyValuePairs, bool[] visited): A private method that performs a Depth-First Search (DFS) on the graph starting from node src. It marks src as visited and then for each adjacent node, it checks if it’s already visited. If it is, then there is a cycle and it sets the explored flag to true. If not, it recursively calls itself with the adjacent node as the new source node.

  void IsCyclicUtil(int src, Dictionary<int, List<int>> keyValuePairs, bool[] visited)
  {
      visited[src] = true;
      foreach (var value in keyValuePairs[src])
      {
          if (visited[value])
          {
              explored = true;
              return;
          }
          IsCyclicUtil(value, keyValuePairs, visited);
      }
  }
  

Time complexity:  O(V + E).

Space Complexity: O(V + E)