If an undirected graph has no edges, then it has an extremely simple structure: each of its connected components is a tree. It is akso possible for a directed graph to have no (directed) cycles and still have a very rich structure. If a directed graph has no cycles, we call it a directed acyclic graph(DAG). The Problem. DAGs can be applied to solving dependency networks that are acyclic. Thus DAGs can be used to encode precedence relations or dependencies in a natural way. Suppose we need to perform a set of tasks that have dependencies among them stipulating, for certain pairs i and j, such as prerequisite requirements stating that certain courses must be taken before others. We can use a node for each task, and a directed edge whenever there are two tasks such that one should be done before the other. If the precedence relation is at all to be meaningful, the result should be a DAG. If it contained a cycle C, then there is no way to solve the entire problem since we do not know which task to accomplish first. It is crucial to seek a valid order in which tasks could be performed, so that all dependencies are respected. This kind of order in a DAG is called a topological ordering. We say a topological ordering of G is an ordering of its nodes as v1,v2,….,vn so that for every edge indeed goes from a low-indexed node to a higher-indexed node. We can prove that G has no cycles by viewing its topological ordering. Proof on Page 101. Does every DAG have a topological ordering, if so, how do we find one efficiently?

Designing and Analyzing the Algorithm. The key to this algorithm lies in finding a way to get started: which node do we put at the beginning of the topological ordering? We start with node v that does not have any incoming edges, because this is the definition of such an ordering. Thus in every DAG G, there is a node v with no incoming edges. Proof is on page 102. The inductive proof contains the following algorithm to compute a topological ordering of G.

Computing a topological ordering of G.
Find a node v with no incoming edges
Delete node v from G
Recursively compute a topological ordering of G-{v}
   and append this order after v

This involves identifying a node v with no incoming edges , and deleting it from G, which takes at most O(n^2) time. If G is very dense, containing Θ(n^2) edges, then it is linear in the size of the input. What if the number of edges m is much less than n^2? In such a case a running time of O(m+n) could be a significant improvement. We can achieve a running time of O(m+n) using the same high-level algorithm –iteratively deleting nodes with no incoming edges. We have to be more efficient in finding these nodes as follows. Declare a node to be “active” if it has not yet been deleted by the algorithm, and maintain the following: 1). For each node w, the number of incoming edges that w has from active nodes; and 2). The set S of all active nodes with no incoming edges from other active nodes.

This section was okay, with a few delays. I would give it an 8/10.