Differences

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

--- courses:cs211:winter2011:journals:wendy:chapter3 [2011/02/02 06:18] – [Section 5: Connectivity in Directed Graphs] shangw
+++ courses:cs211:winter2011:journals:wendy:chapter3 [2011/02/15 07:33] (current) – [Section 5: Directed Acyclic Graphs and Topological Ordering] shangw
@@ Line 68: / Line 68: @@
 , Find an unmarked graph and do the same thing.
+===== Section 5: Directed Acyclic Graphs and Topological Ordering =====
+ This section first introduces the definition of DAG. Then a very important application of DAG follows the definition: dependencies, that is, in order to complete certain tasks, what are the pre-requisite tasks to be finished first. This application is closely related to the topological ordering of DAG. Also a theorem assures that a graph has a topological ordering if and only if it is a DAG. The only if direction of the proof is more or less easy to see. The if direction can be proved by showing an algorithm that computes out the topological order of DAG. We can basically sum up the algorithm as recursively find a node that has no incoming edges, then place the node in the corresponding position (depending on how many recursive loops has been processed) and deleting its outcoming edges, then continue the recursive algorithm till all nodes are scanned through. The running time is O(m+n).
+DAG and topological ordering has important practical applications. At the same time, it is not hard to conceptually understand them well.
+The readability of the section is 7.