Priority in Scheduling 401INPUT: A directed acyclic graph D(V, E)
OUTPUT: An ordering of the vertices so that if D contains a
directed path from v to w, then v < wInitialize the I V I positions Visited [1.. IV I] to FALSE
Stack = 0
for each v e V do
if (Visited [v] = FALSE) then
TopSort(v)
print the elements in Stack from top to bottomTopSort(v) /* The recursive procedure */
Visited [v] = TRUE
for each vertex w at the head of an edge (v, w) leaving v do
if (Visited [w] = FALSE) then
TopSort(w)
Add v to the top of Stack6.172 Correctness of Topological Sort Algorithm
We will use induction on the number of vertices that are topologically sorted to prove that
this algorithm is correct.
Theorem 2. The output of the Topological Sort algorithm is correct.
Proof. Let no = 1 and 7- = {n e N : the output of Topological Sort algorithm is correct
for every dag on n vertices}.
(Base step) The base case is no = 1. For a dag with one vertex, the algorithm is correct,
since the single vertex is printed.(Inductive step) Choose n such that n > no, and suppose that for all dags with k vertices
where 1 < k < n that k e T. Now, let D be a dag with n vertices. Since the vertices are
initially marked FALSE, call TopSort(l) to start at vertex 1. The procedure is just a depth
first search with the added feature that the vertex passed to TopSort is put on a first-in-
last-out list, called a stack, before TopSort is exited. Any vertex that can be reached from
vertex 1 by a directed path will be visited before TopSort(1) is completed and, hence, will
be put on the list before 1 is put on the stack. Thus, I will be closer to the top of the stack
than vertices reachable from 1 by directed paths. These vertices reachable from 1 in D
and appearing below 1 on the stack are just the vertices that represent processes that must
be executed after 1. Therefore, when TopSort(1) is completed, all the vertices that can be
reached from 1 will be on the list below 1. After completing the call to TopSort(1), there
will be at most n - 1 vertices marked FALSE.