Differences

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

--- courses:cs211:winter2014:journals:shannon:chapter3 [2014/02/10 18:23] – [3.4: Testing Bipartiteness: An Application of Breadth-First Search] nollets
+++ courses:cs211:winter2014:journals:shannon:chapter3 [2014/02/10 18:50] (current) – [3.6: Directed Acyclic Graphs and Topological Ordering] nollets
@@ Line 42: / Line 42: @@
 =====3.5: Connectivity in Directed Graphs=====
-In a directed graph, edges have directions. Directed graphs can be represented by a list of nodes that each have two lists, one with the edges coming into it and another with the edges leaving it. In order to determine what the connected components are we can run either BFS or the DFS in the forwards direction and then in the backwards direction. A graph is strongly connected if for nodes u and v, there is a path from u to v and a path from v to u. Directed graphs also have a transitive property. That is, if u and v are mutually reachable and v and w are mutually reachable, then u and w are mutually reachable. Finally, for any two nodes, their strongly connected components are either disjoint or identical.
+In a directed graph, edges have directions. Directed graphs can be represented by a list of nodes that each have two lists, one with the edges coming into it and another with the edges leaving it. In order to determine what the connected components are we can run either BFS or the DFS in the forwards direction and then in the backwards direction. A graph is strongly connected if for nodes u and v, there is a path from u to v and a path from v to u. Directed graphs also have a transitive property. That is, if u and v are mutually reachable and v and w are mutually reachable, then u and w are mutually reachable. Finally, for any two nodes, their strongly connected components are either disjoint or identical. This means that there cannot be a node t such that u and v are each strongly connected to t but not strongly connected to each other.
 The algorithms to find the strongly connected components run in O(n+m) time.
+I feel like a lot of the concepts in the graph sections are most easily explained by pictures. Such as the idea of a strongly connected component being either identical or disjoint. This is a pretty easy thing to draw out and see, but a little bit confusing to just think of as I was reading. Having the visual component in class is extremely helpful to internalize and understand.
+I would give this section a 8/10. It was easy to understand and a helpful recap of directed graphs. I had gotten used to thinking of graphs as trees rather than graphs and the can be very different!
+=====3.6: Directed Acyclic Graphs and Topological Ordering=====
+A directed graph which contains no cycles is referred to as a directed acyclic graph or a DAG. DAGs are useful to represent dependencies, such as the classes necessary to take in order to be a computer science major (i.e. there are some classes with prerequisites and it would be nice to know what you have to take in order to attend higher level classes) . We can show that a graph G has a topological ordering if and only if it has a topological ordering. A topological ordering is an ordering so the DAG elements in such a way that the edges point "forward". The algorithm to find a topological ordering (text page 102) begins by finding a node that has no incoming edges. This way we know that every edge from this node will be pointing "forward". Then we delete that node and find another node with no incoming edges. We repeat this process until we have added all of the nodes to our ordering. This algorithm runs in O(n+m) time if we are able to efficiently find the nodes with no incoming edges. This is achieved by maintaining a list of active nodes with no incoming edges and the number of edges each active node has going to other nodes. Using this we can reduce runtime from a formerly O(n^2) runtime.
+I was a little confused on the O(n+m) run time. I mentioned this on my test, but I still get a little confused on how we determine whether to add or multiply runtimes.
+I would give this section an 8/10. It was helpful and straightforward. The dependency concept is one I am comfortable and we definitely made a DAG similar to the one I described in the summary in 112.