= Topological sorting
{wiki}
A <topological sorting> is the task of constructing a <topological order> of a finite <directed graph>, or reporting that a <directed cycle> makes one impossible. <Kahn's algorithm> repeatedly takes a <vertex> with no unfinished prerequisites. This is useful whenever an operation consumes results produced by earlier operations: once a <vertex> is reached in a <topological order>, every prerequisite along a <directed path> has already been processed. https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2008/resources/lec14/[MIT, Lecture 14: job scheduling and topological sorting]{ref}
The reason a choice is always available in a nonempty finite <Directed acyclic graph> is simple. If every <vertex> had an incoming <directed edge>, repeatedly following predecessors would eventually revisit a <vertex>, giving a <directed cycle>. Removing a <vertex> and its incident <directed edges> cannot create a <directed cycle>, so the argument repeats until every <vertex> is listed. This proves existence of a <topological order> and explains why finiteness matters to this procedure.
// Target: combinatorics.bigb
Back to article page
