Algorithms and Data Structures · Middle · Question 32 of 75
How does Kahn's algorithm compute a topological order?
- 1Sort the vertices by name and check the edges
- ✓Correct answer: Repeatedly remove a vertex that has no incoming edges
- 3Run DFS and output vertices in the order they are first seen
Explanation
Keep in-degrees and a queue of vertices with in-degree 0. If the queue empties before all vertices are output, the graph has a cycle. The DFS version outputs vertices in reverse order of finishing, not of discovery.