Differences

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

--- courses:cs211:winter2014:journals:colin:chapter3 [2014/02/02 20:29] – mohnacsc
+++ courses:cs211:winter2014:journals:colin:chapter3 [2014/02/02 23:55] (current) – mohnacsc
@@ Line 46: / Line 46: @@
 ==== 3.3 - Implementing Graph Traversal Using Queues and Stacks ====
+A graph is represented by adjacency matrix or adjacency list.  To build a graph, sets of nodes and edges are needed.  An adjacency matrix is represented as an n x n matrix (n = set of nodes).  This matrix allows for O(1) time when checking for given edges.  The downside: representation takes O(n^2) space and inefficiency of finding incident edges.
+An adjacency list is better for sparse graphs (graphs with less than n^2 edges).  There is a record for each node v, containing a list of nodes to which v has edges.  The adjacency list uses O(m+n) space (m = set of edges, n = set of nodes).
+Queue is first-in, first-out order.  Elements are placed at the end of the linked list.  Stack is last-in, first-out order.  Elements are placed at the beginning of the linked list.
+The BFS algorithm runs in time O(m+n) if the graph is given by the adjacency list representation.
+The DFS algorithm visits each node using a reverse adjacency list.  It runs in time O(m+n) if the graph is given by the adjacency list representation.
+=== Discussion ===
+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.