Differences

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

--- courses:cs211:winter2018:journals:goldm:ch3 [2018/02/06 18:38] – goldm
+++ courses:cs211:winter2018:journals:goldm:ch3 [2018/02/07 03:19] (current) – goldm
@@ Line 12: / Line 12: @@
 This sections open by discussing the need for an algorithm to determine s-t connectivity, which is the problem of determining whether or not there is a path connecting s and t. The book provides an alternate alias for this problem as the Maze-Solving Problem. The section goes on to discuss the high level descriptions of two algorithms meant to solve this problem, breadth first search and depth first search. The next section is meant to implement them. The book describes breadth first search as the simpler of the two algorithms for tackling the problem. It creates layer for each level of connections. By this, I mean you start at one node, which is the first layer, then you add every node connected to the first node by an edge to the second layer. The third layer is constructed from nodes connected by edges to nodes in the second layer, and so on and so forth. It is worth noting that not only does it determine if a path exists, but it also determines the shortest path. By drawing the appropriate edges across the layers, we can draw a breadth-first search tree for the starting node. Given that there can be more edges than needed to build the tree, extra edges not integral to the layer building are presented as dotted lines. These dotted lines can only be between nodes in the same layer or nodes in adjacent layers. If this were not the case, then the nodes should have been in adjacent layers.
+It goes on to discuss connected components, specifically, the nodes in G found in the breadth-first search tree starting at s are called the connected component of G containing s. Another means of finding the connected component containing s is to start with s in a set, and if an edge is found from an element of the set to something not in the set, add the other node to the set, and do this until no nodes can be added.
+The next means of finding the connected component of s is a depth first search, similar to traversing a maze, you go from s to the first edge, which goes to v. Then you go from v to the node connected by the first edge of v. You keep doing this until you reach a dead end. Then you go back until you reach a node with unexplored edges, then you explore the next edge in the same fashion. You keep doing this until eventually you are back to s and have explored all of its edges. Performing a depth first search leads to a depth first search tree, which typically is very different from a breadth first search tree as it visits nodes in a different order. While a BFS tree is "bushy," a DFS tree is long and spindly. Ultimately, however, the trees will contain the same set of nodes. Upon completing this discussion, the section goes on to talk about the relationships between connected components of a graph. Similar to equivalency classes in abstract algebra, two components must either be completely disjoint or the same.
+This section was really long and tedious, and we have been discussing the material in depth in class already, so this section gets a 2/10.
+===== 3.3: Implementing Graph Traversal Using Queues and Stacks =====
+The previous two sections discuss the theoretical background of graphs and traversing them, but this section begins the dive into actually implementing them practically. The two main methods of representing a graph are adjacency lists and adjacency matrices. The book uses n to discuss the number of vertices and m to discuss the number of edges. Given this, the book calls O(n + m) linear time. If a graph contains n nodes, an adjacency matrix, A, would be nxn. Entry A[u,v] would equal 1 if an edge exists from u to v and 0 otherwise. In undirected graphs, the matrix is symmetric. Obviously, it may be asymmetric in a directed graph. This representation allows us to check for an edge in constant time, but the space complexity is tightly bound by n squared. The matrix representation also inefficiently checks for edges from a node as it must check every adjacent entry in the matrix, which is timely. For these reasons, as well as those in favor of lists, the book uses the adjacency list representation. This representation tracks an array, A, where A[v] returns a linked list of all nodes connected to v. The space complexity of this representation is only O(n + m). Finding if a node is connected to v requires iterating through the list returned by A[v] which is linear with regards to the number of edges of v. According to the book, the adjacency list is ideal for performing BFS. It performs BFS by maintaining an array, Discovered, which has the entry Discovered[v] set to true if v has been discovered already. We use a list L sub i, to track the nodes in each ith layer. These lists can be implemented by stack or queue, it makes no difference. Using this model, the BFS algorithm runs in O(n + m).
+Depth first search's implementation uses a stack to process nodes in the correct order as opposed to a queue. This is done by adding all nodes adjacent to u to the stack, then going to a v and adding all edges adjacent to v, then we do this until we run out of nodes to add, then we start popping nodes off the stack. We use an Explored array which works similarly to the Discovered array for this. Explored[v] is set to true when v's incident edges are scanned. This implementation runs in O(m + n).
+Given the way the implementation for bfs and dfs was constructed, using them to find a graph's connected components is still only O(n + m).
+This section once again was simply recap of previously explained information, so it earns a similar score of 2/10.
+===== 3.4: Testing Bipartiteness: An Application of Breadth-First Search =====
+We begin by remembering that a graph is a bipartite graph if its nodes can be divided into two sets such that every edge connects one node from each set. The book presents the fact that if a graph is bipartite, it cannot contain an odd cycle. For purposes of the analysis of an algorithm to check for bipartiteness, we assume the graph is connected, otherwise we could just perform the algorithm on its connected components. Ultimately, the algorithm we use is simply a BFS tree where we color alternating layers differently. If two nodes are in adjacent layers, they must be colored differently. If two nodes are in the same layer and are connected, there must be an odd cycle so the graph cannot be bipartite. We simply modify BFS to color the nodes, which is done in linear time, but this is just some O(n + m) plus some O(n+m) so, overall, the algorithm is still O(n + m). The rest of the section proves the trivially true statement I gave earlier about odd cycles.
+While this section was still only a review, at least it was way shorter; 4/10.
+===== 3.5: Connectivity in Directed Graphs =====
+This section details the necessary adjustments to the previous logic so that it applies to our directed graphs. In order to represent a directed graph, the book uses a modified adjacency list. Instead of having one list per node, it has two. One which contains the nodes reachable from v and one which contains the nodes that reach v. The breadth-first search for a directed graphs simply adds nodes to layer L(i+1) if there is a directed edge from a node in L(i) to that node. The algorithm still runs in O(n+m). It is worth noting that breadth-first search of s in a directed graphs gives you all nodes such that there is a path from s to t, but there may not be a path from t to s. The implementation of DFS follows the same minor changes as BFS and still runs in linear time.
+A directed graph is strongly connected if there is an edge from any node to any other node in both directions. Two nodes in a directed graph are mutually reachable if there is a path from a to b as well as a path from b to a. It is worth noting that mutual reachability is a transitive property. From these definitions, a strong component of a directed graph is the set of all v such that s and v are mutually reachable. We compute this by performing a BFS of s in G and G reverse and taking the intersection of the two sets. It once again trivially follows that two strong components are either equal or disjoint. Ultimately, as in an undirected graph, we can compute all strong components in O(m + n).
+I found this section slightly more interesting than the previous few; also, it was not too dense, this book often seems exceptionally dense. This section gets a 4.5/10.
+===== 3.6: Directed Acyclic Graphs and Topological Ordering=====
+In the world of undirected graphs, being acyclic makes a graph rather simple and uninteresting. In the world of directed graphs, however, a directed graph without a directed cycle can still manage to be interesting. For starters, this does not outright force the graph to have few edges, it can still have a good number of edges. Directed Acyclic Graphs are commonly referred to as DAGs. DAGs are important; some of their uses include encoding precedence relations and dependencies. This can be useful by computers to organize processes. If there was a cycle, there would be a loop of precedence that would make it impossible to decide what to do in certain situations. A topological ordering of a graph is an ordering of the nodes {v1,v2,v3,v4,...,vn} such that for any edge (vi,vj) it must be true that i<j. Thus, all of the edges point "forward." This can not be done if a directed graph has a cycle. So if a graph has a topological ordering, it is a DAG, and the book goes on to show the converse is true as well. This is partially because of the fact that every directed graph has at least one node with no incoming edges, and one of these nodes serves as v1 as you cannot find an edge to violate the ij relationship. The algorithm for ultimately finding the topological order ends up being O(n squared). Ultimately by more efficiently figuring out which node to delete next from the graph, we can reduce the run time to O(n + m).
+This section while once again, review, covers a fairly interesting topic and did not drag on too long, at least in comparison to 3.2 and 3.3. As such, it gets a 4.6/10.