**__3.6: Directed Acyclic Graphs and Topological Ordering__**

If an undirected graph has no cycles, then it has an extremely simple structure: each of its connected components is a tree.  But it is possible for a directed graph to have no directed cycles and still have a very rich structure.  If a directed graph has no cycles, it is a //directed acyclic graph//, or a //DAG// for short.

Many kinds of dependency networks are DAGs.  DAGs can be used to encode precedence relations or dependencies in a natural way.  

In a topological ordering, nodes are ordered as v(1), v(2),....v(n) so that for every edge (v(i), v(j)), we have i< j.  All edges point "forward."  Also, if G has a topological ordering, then G is a DAG. Its contrapositive is also true; if g is a DAG, then G has a topological ordering.

**Designing and Analyzing an Algorithm**

In every DAG G, there is a node v with no incoming edges.  

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

This algorithm runs at O(n^2).  

This section describes DAGs and topological orderings.  Some nice diagrams on p.103. 9/10.