Algorithms and Data Structures · Senior · Question 46 of 75
Which algorithm should you use to detect a cycle in module imports at build time?
- 1Union-find over all of the import edges
- ✓Correct answer: DFS with three states, or Kahn's algorithm
- 3Dijkstra's algorithm started from every module
Explanation
Imports form a directed graph; a cycle is a back edge in DFS, or leftover vertices after Kahn's topological sort. Union-find detects cycles only in undirected graphs, so it would report false cycles for diamonds.