From the course: Data Structures in JavaScript: Trees and Graphs
Join today to access over 25,500 courses taught by industry experts.
Cycle-detection implementation
From the course: Data Structures in JavaScript: Trees and Graphs
Cycle-detection implementation
- [Instructor] In the coding part of this lesson, we'll get our hands dirty by implementing cycle detection in JavaScript with topological sort. This will involve modifying your existing DFS-based approach. You'll learn to catch exceptions when a cycle is detected throughout this process. This adds robustness to the solution, but also increases its complexity. Suppose that I add an edge from Class C to Class B, and Class B to Class A. The graph will look something like this above. This means that Class C depends on taking Class A. Class B depends on taking Class C. Class A depends on taking Class B. But then, Class C depends on taking Class A, making a cycle. Let's jump into the implementation. We can copy our topological sort solution from the previous lesson over and we need to refactor this to check for cycles. In our visit function, we need to add an ancestor parameter that is defaulted to an empty set. Remember, we check if the node has been visited. If it hasn't, as usual, we…
Download courses and learn on the go
Watch courses on your mobile device without an internet connection. Download courses using your iOS or Android LinkedIn Learning app.