 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/functional-programming-design-and-analysis-of-algorithms/8/d/solution

A topological sort of a Directed acyclic graph is a linear ordering of its vertices in which the tail of every directed edge precedes its head. Along a path

v_{0} \to v_{1} \to \dots \to v_{k}

, this property successively gives

v_{0} < v_{1} < \dots < v_{k}

in that ordering. Thus the vertices of every directed path occur in topological order. The acyclicity condition is necessary, since a directed cycle would force its first vertex to precede itself.

 New to topics? Read the docs here!