How do you detect a cycle in a directed graph using TypeScript?
To detect a cycle in a directed graph, you can use DFS and mark nodes with different states (unvisited, visiting, visited) to track back edges that form cycles.
Cycle detection in directed graphs is a common problem, especially in tasks like dependency resolution, task scheduling, and compiler design. One efficient way to detect cycles is to use Depth-First Search (DFS) and mark each node with one of three states: unvisited, visiting (currently in the DFS recursion stack), and visited. During DFS traversal, if you encounter a node that is in the 'visiting' state, it means a back edge has been found, indicating the presence of a cycle. This is because the node is still in the process of being explored, and revisiting it means you have found a path back to an ancestor, creating a cycle. In TypeScript, the graph can be represented as an adjacency list, and you can implement DFS with a stack or recursion to track the state of each node. An alternative approach is to use Kahn’s algorithm, a topological sorting technique that works for Directed Acyclic Graphs (DAGs) and can identify cycles by detecting if all vertices were processed. Cycle detection is crucial in many fields, such as project management, where circular dependencies in tasks can cause delays, or in software engineering, where cyclic dependencies between modules can lead to complex bugs.