Differences

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

--- courses:cs211:winter2011:journals:wendy:chapter3 [2011/02/02 03:20] – shangw
+++ courses:cs211:winter2011:journals:wendy:chapter3 [2011/02/15 07:33] (current) – [Section 5: Directed Acyclic Graphs and Topological Ordering] shangw
@@ Line 34: / Line 34: @@
 ===== Section 3: Implementing Graph Traversal Using Queues and Stacks =====
+This section starts with introducing and comparing the adjacency matrix and the adjacency list. The big trade off of the adjacency matrix is the amount of space it takes O(n^2), but when the graph is far away from complete, it becomes a waste of space. In addition to that, many algorithms that require to go over all the edges will take at O(n^2) time. However, if implementing with the adjacency list, the space it takes is only O(n+m), so is the running time of those algorithm. Therefore, the book uses adjacency list to implement graphs.
+Note: from now on, refer O(m+n) as the linear time for graph.
+Next the section introduces queue (fifo) and stack (filo), which are important tools to implement algorithm in which orders are important.
+Implementing BFS: It is basically the same as we talked about in class. However, the text suggested that instead of using a list of list (where it does not matter with a queue or stack), we can use a single queue and enqueue the nodes, which is what I thought where we were heading to in class. The implementation takes O(m+n) time.
+Implementing DFS: The book introduces an algorithm to implement DFS using a stack. It does the same thing as mentioned in previous section, except that instead of choosing the first one of each layer, we select the last one, because the nature of a stack-which is essentially the same idea. The running time of the algorithm is O(m+n).
+Lastly, an application of DFS or BFS algorithm is exemplified: finding the set of all connected components. And its running time, a constant times the running time of DFS or BFS-still O(m+n).
+Readability: 8
+===== Section 4: Testing Bipartiteness: an Application of BFS =====
+The section first states the Bipartiteness problem, which is essentially equivalent to the 2-colorable problem (if all nodes in a graph G can be colored in two colors with no two nodes 1 distance away from each other sharing the same color).
+Then an algorithm makes use of the BFS is presented, as shown in lecture. The running time of the algorithm is the running time of BFS, O(m+n) plus the running time of checking the edges and nodes O(m+n), which ends up with, still, O(m+n).
+Also, thanks to the algorithm, we can prove that a graph G is bipartite if and only if it does not contain an odd cycle. The only if direction is quite straight forward. The if direction is not hard either if seeing through the algorithm. If there is an odd cycle, then the cycle has to contain two nodes from the same layer (otherwise the cycle would be even), then there is an edge with the two end nodes sharing the same color, contradiction with it is 2-colorable.
+Question: at a math conference, a grad student tried to show me how to prove the 4-colorable problem, but I failed following him :p so I am curious about how to prove any graph can be colored by 4 colors.
+Readability: 8
+===== 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.