Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 9] DIRECTED GRAPHS 217

Fig. 9-16

A fundamental operation on a dagSis to process the vertices one after the other so that the vertexuis always
processed before vertexvwhenever (u, v)is an edge. Such a linear orderingTof the vertices ofS, which may
not be unique, is called atopological sort.
Figure 9-17 shows two topological sorts of the graphSin Fig. 9-16. We have included the edges ofSin
Fig. 9-17 to show that they agree with the direction of the linear ordering.

Fig. 9-17 Two topological sorts

The following is the main theoretical result in this section.

Theorem 9.8: LetSbe a finite directed cycle-free graph. Then there exists a topological sortTof the graphS.

Note that the theorem states only that a topological sort exists. We now give an algorithm which will find a
topological sort. The main idea of the algorithm is that any vertex (node)Nwith zero indegree may be chosen as
the first element in the sortT. The algorithm essentially repeats the following two steps untilSis empty:

(1) Find a vertexNwith zero indegree.

(2) DeleteNand its edges from the graphS.

We use an auxiliary QUEUE to temporarily hold all vertices with zero degree. The algorithm appears in Fig. 9-18.