Difficulty Implementing Topological Sort in Python for Directed Acyclic Graph - Recursion Depth Exceeded
After trying multiple solutions online, I still can't figure this out. I'm following best practices but I'm trying to implement a topological sort algorithm in Python for a directed acyclic graph (DAG), but I'm running into a `RecursionError: maximum recursion depth exceeded in comparison`. I've built my graph using an adjacency list and I'm utilizing depth-first search (DFS) to perform the sort. However, for larger graphs, I keep hitting this behavior. Here’s the code I have so far: ```python class Graph: def __init__(self): self.graph = {} def add_edge(self, u, v): if u not in self.graph: self.graph[u] = [] self.graph[u].append(v) def topological_sort_util(self, v, visited, stack): visited.add(v) for neighbor in self.graph.get(v, []): if neighbor not in visited: self.topological_sort_util(neighbor, visited, stack) stack.append(v) def topological_sort(self): visited = set() stack = [] for node in self.graph: if node not in visited: self.topological_sort_util(node, visited, stack) return stack[::-1] ``` I've tried increasing the recursion limit with `sys.setrecursionlimit(1500)`, but I still encounter issues when the graph has more than about 100 nodes. Is there a more efficient way to handle this, or perhaps an iterative version of the topological sort that doesn't rely on recursion? Also, are there any best practices for managing larger graphs in Python? Any help would be appreciated! I'm coming from a different tech stack and learning Python. What's the correct way to implement this? I'm working on a REST API that needs to handle this. What am I doing wrong?