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.