Differences

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

--- courses:cs211:winter2018:journals:shermanc:chapter3 [2018/02/06 05:17] – shermanc
+++ courses:cs211:winter2018:journals:shermanc:chapter3 [2018/02/07 04:26] (current) – [3.6: Directed Acyclic Graphs and Topological Ordering] shermanc
@@ Line 68: / Line 68: @@
 ===== 3.5: Connectivity in Directed Graphs =====
+This section started off by talking about how to represent directed graphs in algorithms, which is by using a version of the adjacency list.  In this, each individual node will have a list for the nodes that it has edges and a list for the nodes of which it has edges from.
+The interesting part here that I have some questions about was how a directed graph-version of BFS computes a path from //s// to //t//, just as the undirected version, but in this version t does not necessarily have a path back to //s//.  How is that possible if we have lists that have edges both to and from?  Unless it means that the "to" edges do not have a path back to //s// from //t//, which would then make sense.
+ DFS also runs naturally on a directed graph and both algorithms keep their respective run times of O(m + n) and O(m).
+If we want to find the paths to //s// instead of from, we can simply run B or DFS on G<sup>//rev//</sup> to get this, as it will run the same algorithm, just from //t// now.
+To find if a directed graph is strongly connected, we can run an algorithm where we start at any node in the graph and run BFS from that node, then run BFS on the same node but in G<sup>//rev//</sup>.  If even one of these algorithms fails, then it is not strongly connected.  But if they are successful, then the nodes are mutually reachable and therefore the graph is strongly connected.
+The last topic in this chapter, __strong components__, were a little fuzzy to me and I could use some extra clarification, which I will seek out.  Overall, this chapter was a little more in depth than the previous few, though.  5/10 for readability and content.
+===== 3.6: Directed Acyclic Graphs and Topological Ordering =====
+This section started off with a bang: an undirected graph with no cycles, it is just a tree.  __**//Boom!//**__  (I think I'm having too much fun with DokuWiki syntax; now back to the fun stuff.)  Despite this, it is possible for a directed graph to have a no cycles but still have a complex structure.  This structure is called a __DAG__, or //directed acyclic graph//.
+A simple way to think about DAGs is as if we have a set of classes the have prerequisites, as was the example in class.  This has to be a DAG, because it just wouldn't make sense if a class that had a prerequisite of a lower-level class was itself a prerequisite of another lower-level class.  To make sure this is true, there is what is called a __topological ordering__, where for every edge (v<sub>//i//</sub>, v<sub>//j//</sub>), //i// < //j//.  Thus, every edge points in the forward or downhill direction and everything before a certain node must already be completed.  This provides us the fact that if we have a graph G that has a topological ordering, then G is a DAG.
+It actually goes to get proven that the converse is indeed true as well, where if G is a DAG, then G has a topological ordering.  This is proven by finding a node //v// (in a DAG) that has no incoming edges.  From this we can follow its path down and see that it has a topological ordering.  The total run time of this algorithm can actually be reduced down to O(m + n), because it runs on //n// elements and selects each //v// and deletes it in constant time by maintaining which nodes have incoming nodes from other nodes still in our list and the number of edges from the nodes in our list.
+This section was a more in-depth (first search; forgive the pun) than preceding sections, as was the last one.  A question I still have that I have meant to pose over this chapter: why is O(m + n) have m listed first?  I know it is equal either way, it just peaks my curiosity.  I give this chapter a 7/10 for personal reasons.