= Solution
Run <depth-first search> on <Graph> B with the same lexical convention and put each <vertex> on the front of the output when its search finishes. The finish order is
$$
4,6,7,5,2,1,3,
$$
so the returned <topological order> is
$$
\boxed{3,1,2,5,7,6,4.}
$$
For example, both <edges> from $1$ point to later entries, the <edges> from $5$ point to $4$ and $7$ later in the order, and $3$ precedes $6$. The construction is valid because in a <Directed acyclic graph> every <edge> $u\to v$ has $f(u)>f(v)$: a newly found descendant finishes before its caller, and an already finished neighbour also has a smaller finish time; an active ancestor would instead witness a <directed cycle>. Thus reversing the finish order puts every prerequisite before its successor. The time is $O(|V|+|E|)$.
Back to article page
