To perform a topological sort on a DAG, one can order the vertices in the reverse order of which DFS-calculated value?
Show answer
Finishing times
In a Directed Acyclic Graph (DAG), if there is an edge from u to v, the finishing time of u will be greater than the finishing time of v. Therefore, listing vertices in decreasing order of finishing times yields a valid topological order.
Also asked as:
- In a Directed Acyclic Graph, a valid topological order can be obtained by sorting vertices in decreasing order of which DFS attribute?