Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2011:journals:charles:chapter3 [2011/02/14 03:25] – gouldc | courses:cs211:winter2011:journals:charles:chapter3 [2011/02/18 06:51] (current) – [3.6 Directed Acyclic Graphs and Topological Ordering] gouldc | ||
|---|---|---|---|
| Line 12: | Line 12: | ||
| ===== 3.6 Directed Acyclic Graphs and Topological Ordering ===== | ===== 3.6 Directed Acyclic Graphs and Topological Ordering ===== | ||
| - | Under construction... | + | 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? |
