The first solution to Example 1l.6 searched through all possible rankings. Another approach is to attempt the construction of the required ranking. To this end consider a ranking, obj1, obj2, . . . , objn, of the n objects that is a topological sort with respect to a given diagram. What can be said about obj1, the highest-ranked object? Clearly there must be no objects that are constrained by the diagram to appear higher in the ranking than obj1. Otherwise, those constraints would be violated, and the ranking would not be a topological sort. In terms of the diagram, this means that no arrows must point to obj1. We describe this by saying that obj1 must have no predecessors.
Now suppose the node corresponding to obj1 is erased, as well as all the arrows emanating from obj1. As noted earlier, this results in a new diagram that represents a new partial order on the remaining n - 1 objects. Consider the ranking of these n - 1 objects obtained by taking the original topological sort of the n objects and removing obj1. That is, consider obj2, obj3, . . . , objn. It must be a topological sort of the remaining n - 1 objects in the new diagram with respect to the new partial order. This is because any constraint in the new diagram that is violated by this ranking would have been violated in the original ranking of the n objects. Note that if any topological sort of the remaining n - 1 objects were taken with respect to the new partial order, and obj1 were placed in front of it, the ranking of n objects thus obtained would be a topological sort with respect to the original partial order. Placing obj1 first in this ranking cannot violate any of the original constraints because they did not require that any object precede obj1.
We have just discovered how to construct a topological sort:
A construction-based algorithm:
While S is not empty
1. Select any object with no predecessors.
2. Place it in the next position of the output ranking.
3. Remove that object from S, and
4. Remove its arrows from the partial order.
The output ranking produced will always be a topological sort.
11.3.2 An Initial Implementation
11.3.3 A Better Implementation