Differences
This shows you the differences between two versions of the page.
| courses:cs211:winter2018:journals:holmesr:section_3.6 [2018/02/06 03:25] – created holmesr | courses:cs211:winter2018:journals:holmesr:section_3.6 [2018/02/06 04:52] (current) – holmesr | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Section 3.6 DAGS and Topological Orderings | ====== Section 3.6 DAGS and Topological Orderings | ||
| + | |||
| + | A Directed Acyclic Graph (DAG) is just what it sounds like, a directed graph containing no cycles. These are useful for representing precedence relations and dependencies because they don't contain cycles. A cycle in a dependency relation would mean that one process could not start until another had taken place, which would never happen because none could start first. | ||
| + | |||
| + | These types of graphs have can also be represented by a structure known as a topological ordering, which the book defines as "an ordering of the nodes v< | ||
| + | |||
| + | It is also true that every DAG has a topological ordering, since there must be a node that has no incoming edges due to the fact that there are no cycles in a DAG. Once this node has been removed and removing a node cannot create a cycle, then there is a DAG remaining with all the nodes that were in the previous DAG, except the removed node. This truth can be used to devise an algorithm that runs in O(n< | ||
| + | |||
| + | 1.find the node with no incoming edges | ||
| + | |||
| + | 2.delete this node | ||
| + | |||
| + | 3.recursively compute the topological ordering of the DAG without the removed node and add this after the deleted node. | ||
| + | |||
| + | There is yet a faster, linear-time method to computing the topological ordering of the DAG, but I could not quite grasp what this was. It dealt with active nodes and edges coming from those nodes into the current node. | ||
