Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:anna:chapter_3 [2011/02/04 16:54] – created poblettsa
+++ courses:cs211:winter2011:journals:anna:chapter_3 [2011/02/15 23:02] (current) – poblettsa
@@ Line 43: / Line 43: @@
 It seems to me that algorithms for directed graphs only require slight modifications to the algorithms for undirected graphs.  In some cases, the algorithms are the same; the results just need to be interpreted differently.
+===3.6 Directed Acyclic Graphs and Topological Ordering ===
+If an undirected graph has not cycles, the each of its connected components is a tree.  If a directed graph has this property it is a DAG.  DAG's are useful for representing precedence and dependencies.  A topological ordering of a DAG is and ordering of the nodes such that each node is "less than" the next.  This means that each of the edges points forward.  The goal of this section is to prove that every DAG has a topological ordering, and then that we can find it efficiently.
+The key to finding a topological ordering is to find the first node.  This is easier than it seems because the highest node will be the one with no incoming edges.  From there, you can traverse the outgoing edges to build the topological ordering.  An algorithm to compute a topological ordering is on page 102.  As far as analysis goes, it appears the running time in O(n^2), but it can actually be improved to O(m+n) if we keep track of the nodes that can be deleted at all times, thus spending constant time per edge.  I occasionally get confused by the O(m+n) running times in the book.  They make more sense in class when we can label each step of the algorithm more precisely.