How to efficiently implement a Topological Sort for a Directed Acyclic Graph in TypeScript with cycle detection?
I'm collaborating on a project where I'm working on a TypeScript project that requires me to perform a topological sort on a directed acyclic graph (DAG). While I understand the basic algorithm using depth-first search (DFS), I've been struggling with efficiently detecting cycles in the graph. Specifically, I'm unsure how to modify my DFS implementation to ensure that cycles are detected without incurring too much overhead. I've implemented the following code to perform the topological sort: ```typescript class Graph { private adjList: Map<number, number[]>; private visited: Set<number>; private tempMark: Set<number>; private result: number[]; constructor() { this.adjList = new Map(); this.visited = new Set(); this.tempMark = new Set(); this.result = []; } addEdge(from: number, to: number) { if (!this.adjList.has(from)) { this.adjList.set(from, []); } this.adjList.get(from)!.push(to); } topologicalSort() { for (let node of this.adjList.keys()) { if (!this.visited.has(node)) { if (this.dfs(node)) { return null; // Cycle detected } } } return this.result.reverse(); // Return in topologically sorted order } private dfs(node: number): boolean { this.tempMark.add(node); this.visited.add(node); for (let neighbor of this.adjList.get(node) || []) { if (this.tempMark.has(neighbor)) { return true; // Cycle detected } if (!this.visited.has(neighbor)) { if (this.dfs(neighbor)) { return true; // Cycle detected } } } this.tempMark.delete(node); this.result.push(node); return false; } } ``` I'm working with performance optimization with larger graphs, and sometimes I'm getting incorrect results where the cycle detection doesn't seem to work as intended. For instance, when I create a graph like this: ```typescript const graph = new Graph(); graph.addEdge(1, 2); graph.addEdge(2, 3); graph.addEdge(3, 1); // This creates a cycle ``` When I run `graph.topologicalSort()`, it returns `null` as expected, but I feel like the cycle detection is not as efficient as it could be. I suspect the recursive depth-first search might be leading to stack overflow errors in extreme cases or not handling some edge cases correctly. Could anyone provide insights on how to improve the cycle detection mechanism or suggest a more efficient way to implement the topological sort in TypeScript? I appreciate any insights!