Differences

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

--- courses:cs211:winter2011:journals:wendy:chapter3 [2011/02/02 05:49] – shangw
+++ courses:cs211:winter2011:journals:wendy:chapter3 [2011/02/15 07:33] (current) – [Section 5: Directed Acyclic Graphs and Topological Ordering] shangw
@@ Line 60: / Line 60: @@
 ===== Section 5: Connectivity in Directed Graphs =====
+To store the information of a directed graphs we normally need two adj. lists: 1st recording "to which nodes" for each node; 2nd recording "from which nodes" for each node. For two nodes in a directed graph to be connected, they have to be mutually reachable. Running the BFS or DFS of a node s on the "to which" list help us build the trees showing all the nodes that are reachable from s, but not from where one can get to s.
+For a strong connected graph, every two nodes are connected. Running the BFS twice from both "to which" and "from which" direction , together with theorem 3.16, can easily test if a graph is strongly connected. Further more, similar to undirected graphs, for any two nodes s and t in a directed graph, their strong components are either identical or disjoint.
+I thought about how to compute the strong component of directed graph, but not sure if it is right:
+, find a random node s, run BFS twice from both "to which" and "from which" direction, chose the overlap part, denote as the first strong component. Mark every node in the component.
+, 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.