Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C#

Solution: Detect a Cycle in a Graph

Explore how to detect cycles in a graph by implementing a recursive DFS approach in C#. Understand the use of recursion stacks and visited nodes to identify cycles and analyze the solution's time complexity, helping you master graph algorithms for coding interviews.

We'll cover the following...

Solution

DetectCycle
Graph.cs
class Program
{
    /// <summary>
    /// Detects a cycle in a given graph.
    /// </summary>
    /// <param name="graph">The graph.</param>
    /// <returns>True if there is a cycle in the given graph, otherwise False.</returns>
    public static bool DetectCycle(Graph graph)
    {
        // visited list to keep track of the nodes that have been visited since the beginning of the algorithm
        bool[] visited = new bool[graph.V];
        // stack keeps track of the nodes which are part of the current recursive call
        bool[] myStack = new bool[graph.V];
        for (int node = 0; node < graph.V; node++)
        {
            // DFS 
            if (DetectCycleRecursive(graph, node, visited, myStack))
            {
                return true;
            }
        }
        return false;
    }
    /// <summary>
    /// Detects a cycle in a given graph.
    /// </summary>
    /// <param name="graph">The graph.</param>
    /// <param name="node">A source vertex.</param>
    /// <param name="visited">A list to track visited nodes.</param>
    /// <param name="stack">A helper stack.</param>
    /// <returns>True if there is a cycle in the given graph, otherwise False.</returns>
    static bool DetectCycleRecursive(Graph graph, int node, bool[] visited, bool[] myStack)
    {
        // Node was already in recursion stack. Cycle found.
        if (myStack[node])
        {
            return true;
        }
        // It has been visited before this recursion
        if (visited[node])
        {
            return false;
        }
        // Mark current node as visited and
        // add to recursion stack
        visited[node] = true;
        myStack[node] = true;
        AdjNode head = graph.graph[node];
        while (head != null)
        {
            // Pick adjacent node and call it recursively
            int adjacent = head.Vertex;
            // If the node is visited again in the same recursion => Cycle found
            if (DetectCycleRecursive(graph, adjacent, visited, myStack))
            {
                return true;
            }
            head = head.Next;
        }
        // remove the node from the recursive call
        myStack[node] = false;
        return false;
    }
    // Main program to test the above code
    public static void Main(string[] args)
    {
        Graph g1 = new Graph(4);
        g1.AddEdge(0, 1);
        g1.AddEdge(1, 2);
        g1.AddEdge(1, 3);
        g1.AddEdge(3, 0);
        Graph g2 = new Graph(3);
        g2.AddEdge(0, 1);
        g2.AddEdge(1, 2);
        Console.WriteLine(DetectCycle(g1)); // Output: True
        Console.WriteLine(DetectCycle(g2)); // Output: False
    }
}
...