Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2011:journals:david:chapter3 [2011/02/15 00:09] – margoliesd | courses:cs211:winter2011:journals:david:chapter3 [2011/02/15 01:12] (current) – [3.6 - Directed Acyclic Graphs and Topological Ordering] margoliesd | ||
|---|---|---|---|
| Line 28: | Line 28: | ||
| ====3.6 - Directed Acyclic Graphs and Topological Ordering==== | ====3.6 - Directed Acyclic Graphs and Topological Ordering==== | ||
| + | |||
| + | A directed graph with no cycles is called a Directed Acyclic Graph. We can use a DAG to represent dependencies or precedence relationships. A topological ordering of a DAG is an ordering of nodes in which each edge points forward along the list. Therefore, the first node must have no edge pointing to it. Some facts about DAG's: if a graph has a topological ordering, then it is a DAG, and if a graph is a DAG, then it must have a topological ordering. The compute the topological ordering of a DAG, we find a node with no incoming edges, delete it from the graph, and add it to the topological ordering. We recursively find nodes with no incoming edges, and add each of those to the topological ordering in the order they were found. We can achieve a running time of O(n+m) for this algorithm if we also keep track of nodes that have not yet been deleted (active nodes). For each node, we keep track of the number of incoming edges that it has from active nodes, and we keep track of all the active nodes that do not share an edge with an active node. This way, we can subtract the number of edges from each node incident to the one deleted, which makes it faster to find the next node with no incoming edges. | ||
| + | |||
| + | Readability: | ||
