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. | It seems to me that algorithms for directed graphs only require slight modifications to the algorithms for undirected graphs. | ||
+ | |||
+ | |||
+ | ===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. | ||
+ | |||
+ | 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. |