Differences

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

--- courses:cs211:winter2012:journals:virginia:chapter3 [2012/01/30 01:38] – [Section 2: Graph Connectivity and Traversal] lovellv
+++ courses:cs211:winter2012:journals:virginia:chapter3 [2012/02/16 03:06] (current) – lovellv
@@ Line 5: / Line 5: @@
 ===== Section 1: Basic Definitions and Applications =====
-A //graph// consists of a collection of nodes (V) and edges (E).  //Directed graphs// have "one-way" edges to indicate asymmetric relationships while //undirected graphs// have "two-way" edges to indicate symmetric relationships.  Some examples of graphs include transportation, communication, information and social networks.
+A **graph** consists of a collection of nodes (V) and edges (E).  **Directed graphs** have "one-way" edges to indicate asymmetric relationships while **undirected graphs** have "two-way" edges to indicate symmetric relationships.  Some examples of graphs include transportation, communication, information and social networks.
-A //path// in a graph is a sequence of nodes where each consecutive pair is connected by an edge.  A path is //simple// if all the vertices are distinct.  A path is a //cycle// if the first and last node are the same.  We say a graph is //connected// if there is a path from one node to every other.  The //distance// from one node to another is the length of the shortest path between them, measured in number of edges.
+A **path** in a graph is a sequence of nodes where each consecutive pair is connected by an edge.  A path is **simple** if all the vertices are distinct.  A path is a **cycle** if the first and last node are the same.  We say a graph is **connected** if there is a path from one node to every other.  The **distance** from one node to another is the length of the shortest path between them, measured in number of edges.
-A graph is a //tree// if it is connected and does not contain a cycle.  Trees represent hierarchies.
+A graph is a **tree** if it is connected and does not contain a cycle.  Trees represent hierarchies.
 Theorem: Any two of the following imply the third (i) G is connected, (ii) G does not contain a cycle, (iii) G has n-1 edges
@@ Line 27: / Line 27: @@
 ===== Section 3: Graph Traversal using Queues and Stacks =====
+Now we need to implement graphs, DFS and BFS.  Graphs can be implemented as an adjacency matrix or an adjacency list.  The adjacency matrix representation requires O(n^2) space while the adjacency list representation requires only O(m+n) space.
+We can use stacks and queues to help implement BFS and DFS.  Queues support first in first out access.  Stacks support last in first out access.  For BFS, we can manage each list of the nodes on a layer as either a stack or a queue.  BFS runs in O(m+n) time.  In DFS, we need to use a stack to process the nodes since we will need to backtrack.  DFS also runs in O(m+n) time.
+Readability: 8
 ===== Section 4: Testing Bipartiteness: An Application of BFS =====
+We can use BFS to test whether a graph is bipartite.  Recall, a graph is bipartite if you can color its nodes red and blue so every edge has one red end and one blue end.
+To see if a graph is bipartite, we will pick a node to start and color it red.  Then, we will color all of its neighboring nodes (layer 1) blue and all those node's neighbors (layer 2) red, etc.  This is exactly like BFS, except with an extra color array.
+Note that if there is no edge of G joining two nodes in the same layer, then G is bipartite.  If there is an edge of edge of G joining two nodes of the same layer, G contains an odd length cycle and is not bipartite.
+Readability: 8
 ===== Section 5: Connectivity in Directed Graphs =====
+In this section, we begin to consider directed graphs.  We represent directed graphs with two adjacency lists - one of the nodes //to// which s has edges and one of the nodes //from// which it has edges.
+BFS and DFS are almost the same as in undirected graphs.  Both discover the set of nodes reachable from s, but in directed graphs, it is not guaranteed that we can get back to s from these nodes.  If there is a path from s to t and from t to s, then we say s and t are **mutually reachable**.  We say a directed graph is **strongly connected** if every pair of nodes are mutually reachable.
+The **strong component** containing s in a directed graph is the set of all v such that s and v are mutually reachable.  The strong component is similar to the connected component for an undirected graph.  Like the connected component, strong components are either identical or disjoint.
+Readability: 8
+===== Section 6: Directed Acyclic Graphs and Topological Orderings =====
+A special type of directed graph that contains no cycles is a **directed acyclic graph** (DAG).  DAGs can be used to represent precedence relations or dependencies.  One natural problem relating to DAGs is how to create a **topological ordering** (an ordering in which all edges point forward) from a DAG.  This is the equivalent to finding the order in which we may do tasks which depend on each other.  It is easy to see if a graph has a topological ordering, it is a DAG, but it is not obvious every DAG has a topological ordering.
+In fact, every DAG does have a topological ordering. We can find it by finding a node with no incoming edges, ordering it next in our topological ordering, deleting it from our graph, and repeating until we have added every node.  This algorithm has O(m+n) run time. (p 103)
+Readability: 8