implementing Implementing a Topological Sort in C# - Infinite Loop with Cyclic Graphs
I'm testing a new approach and This might be a silly question, but I'm sure I'm missing something obvious here, but I'm working on a topological sort implementation in C# using a directed graph, and I keep running into an infinite loop when processing graphs that contain cycles... I understand that topological sorting is only valid for Directed Acyclic Graphs (DAGs), but I need to ensure my algorithm can detect cycles and handle them gracefully. Here's the code I've written so far: ```csharp using System; using System.Collections.Generic; public class Graph { private readonly int _vertices; private readonly List<int>[] _adjacencyList; public Graph(int vertices) { _vertices = vertices; _adjacencyList = new List<int>[vertices]; for (int i = 0; i < vertices; i++) { _adjacencyList[i] = new List<int>(); } } public void AddEdge(int start, int end) { _adjacencyList[start].Add(end); } public void TopologicalSort() { bool[] visited = new bool[_vertices]; bool[] recursionStack = new bool[_vertices]; Stack<int> stack = new Stack<int>(); for (int i = 0; i < _vertices; i++) { if (!visited[i]) { if (!TopologicalSortUtil(i, visited, recursionStack, stack)) { Console.WriteLine("Graph is cyclic, topological sort not possible."); return; } } } while (stack.Count > 0) { Console.Write(stack.Pop() + " "); } } private bool TopologicalSortUtil(int v, bool[] visited, bool[] recursionStack, Stack<int> stack) { visited[v] = true; recursionStack[v] = true; foreach (int neighbor in _adjacencyList[v]) { if (!visited[neighbor]) { if (!TopologicalSortUtil(neighbor, visited, recursionStack, stack)) { return false; } } else if (recursionStack[neighbor]) { return false; // Cycle detected } } recursionStack[v] = false; stack.Push(v); return true; } } ``` I've created the `TopologicalSort` method which calls a utility function to process each vertex. The `recursionStack` is intended to keep track of vertices currently in the recursion stack to detect cycles. However, I noticed that the program hangs indefinitely when I input a cyclic graph. I tried adding debug statements, but they didn't help clarify where it gets exploring. For example, with the following edges: ```csharp Graph g = new Graph(4); g.AddEdge(0, 1); g.AddEdge(1, 2); g.AddEdge(2, 3); g.AddEdge(3, 1); // This creates a cycle ``` When I run the `TopologicalSort()` method, it just hangs without producing any output. Is there something I'm missing in my cycle detection logic, or is there a better way to implement this algorithm? Any insights would be greatly appreciated! This is part of a larger API I'm building. How would you solve this? How would you solve this? Thanks for any help you can provide!