Differences

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

--- courses:cs211:winter2014:journals:colin:chapter3 [2014/02/02 21:23] – mohnacsc
+++ courses:cs211:winter2014:journals:colin:chapter3 [2014/02/02 23:55] (current) – mohnacsc
@@ Line 60: / Line 60: @@
 The breadth-first and depth-first search algorithms are pretty straight forward and have predictable run times.  However, I was expecting an algorithm that would allow for O(n log n) access time using recursion to skip branches.  This would only be implemented on an ordered tree though.  In our situation using DFS and BFS, the time stays linear (which is acceptable).
+==== 3.4 - Testing Bipartiteness: An application of Breadth-First Search ====
+A bipartite graph is one where the node set V can be partitioned into sets X and Y in such a way that every edge has one end in X and the other end in Y.  If a graph is bipartite, then it cannot contain an odd cycle.
+We can test a graph for bipartiteness by choosing some node s and coloring it red.  The neighbors of s must be colored blue and, in turn, we must make the neighbors of blue nodes red.  We continue this process until we have visited every node, similar to the BFS algorithm.
+Let G be a connected graph.  Let L(1), L(2),… be the layers produced by BFS starting at node s.   Then one of the following must be true:
+  * There is no edge of G joining two nodes of the same layer.  This graph is bipartite.
+  * There is an edge of G joining two nodes of the same layer.  This graph is not bipartite.
+==== 3.5 - Connectivity in Directed Graphs ====
+A directed graph in adjacency list representation has two associated lists for each node: nodes to which it has edges and nodes from which it has edges.  A graph is strongly connected (or mutually agreeable) if, for every two nodes u and v, there is a path from u to v and a path from v to u.  If u and v are mutually reachable, and v and w are mutually reachable, then u and w are mutually reachable.  For any two nodes s and t in a directed graph, their strong components are either identical or disjointed.  It is possible to compute the strong components for all nodes in a total time of O(m+n).
+==== 3.6 - Directed Acyclic Graphs and Topological Ordering ====
+If a directed graph has no cycles it is a directed acyclic graph (DAG).  They can be used to encode precedence relations or dependencies in a natural way.  A topological ordering of graph G is an ordering of its nodes as v(1), v(2), …, v(n) so that for every edge (v(i), v(j), we have i < j.  All edges point forward in the ordering.  If G has a topological ordering, then G is a DAG (and vice versa).
+In every DAG G, there is a node v with no incoming edges.  This is the beginning of our algorithm.  Then, recursively compute the topological ordering of G-{v} and append the order.  The run time of this algorithm is O(n^2).
+=== Discussion ===
+With the expansion of the BFS and DFS applications, there is more of an understanding of how algorithm design follow strict patterns and rules are used to analyze increasingly complex structures.  In previous courses, the tree structure was fairly unexplored but now is seen as a very complex and tricky structure.  I am worried that directed and undirected graphs might become more complicated in future sections but have not had too much trouble with them too far.