Chapter 3: Graphs

DAGs are directed graphs that do not contain cycles. G is a DAG ⇔ G has a topological ordering. Despite DAGs having no cycles, they can contain nC2 edges. To find a topological ordering, recursively find nodes with no incoming edges and order them next in the ordering. (Once you order a node, delete it and all of its outgoing edges; this will cause there to be at least one new node that does not have an incoming edge.) Such an algorithm can run in time O(m+n). Topological orderings can be applied to precedence relations. For example, suppose two operations A and B such that A must be done before B. This could be formalised in a DAG by drawing an outgoing edge from A to B (A→B) but not the other way around. The topological ordering of this DAG would be the proper order of operations then?