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 16:23] – 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 ===== | ||
| - | 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 nodes. 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). | + | 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). |
