Differences

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

--- courses:cs211:winter2014:journals:shannon:chapter3 [2014/02/10 18:29] – nollets
+++ courses:cs211:winter2014:journals:shannon:chapter3 [2014/02/10 18:50] (current) – [3.6: Directed Acyclic Graphs and Topological Ordering] nollets
@@ Line 52: / Line 52: @@
 =====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.