4 - Directed Graphs

Summary

A directed graph is simply an abstraction of a network of one-way roads between a set of cities. When one travels in such a network, one may return to the starting point. In this chapter, we are interested in special networks that exclude the possibility of ever returning to the starting point or to any city we have already visited. We refer to a network as acyclic.

Suppose we are traveling in an acyclic network of one-way roads. By definition, on each trip, we may visit each city at most once. A very natural question that arises is; what is the maximum number of cities we can visit? In this chapter, we present a simple and efficient algorithm that finds the longest sequence of cities we can visit in the special case of acyclic networks of one-way roads.

Acyclic directed graphs are also an abstraction of assembly instructions of an airplane model. The vertices in this case are not cities but assembly tasks (glue two parts together, paint a part, etc.). An edge from task u to task υ is not a one-way road but a dependence indicating that before task v is started, one must complete task u. Given such assembly instructions, we would like to find an ordering of the tasks that obeys the dependencies. A single worker can then assemble the airplane model by completing one task at a time according to this ordering. Such an ordering is a called a topological ordering. We present a simple and efficient algorithm for topological ordering.