Differences

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

--- courses:cs211:winter2011:journals:chen:chapter_3 [2011/02/02 05:00] – [3.3 Implementing Graph Traversal Using Queues and Stacks] zhongc
+++ courses:cs211:winter2011:journals:chen:chapter_3 [2011/02/16 12:33] (current) – zhongc
@@ Line 38: / Line 38: @@
 ====== 3.3 Implementing Graph Traversal Using Queues and Stacks ======
-	Two approaches:
+Two approaches:
-	  * Adjacency matrix
+  * Adjacency matrix
-  * 	Adjacency list
+  * Adjacency list
 Tradeoffs: The adjacency matrix representation of a graph requires O (n2) space, while the adjacency list representation requires only O (m + n) space.
+The adjacency list data stxucture is ideal for implementing breadth-first search.P116
+**Finding the Set of All Connected Components**
+We start with an arbitxary node s, and we use BFS to generate its connected component.then find a
+node v (if any) that was not visited by the search from s and iterate, using BFS (or DFS) starting from v to generate its connected component--which, by(3.8), will be disjoint from the component of s. We continue in this way until all nodes have been visited.
+Interesting/Readable: 5 5
+====== 3.4 Testing Bipartiteness: An Application of Breadth-First Search ======
+If there is an odd number cycle, then it is impossible to color them with differennt colors.
+Designing the algo  **Breadth-First Search**
+The idea is to use the BFS to push the layers forward and test for bipartiteness.
+First we assume the graph G is connected, next we pick any node s that belongs to V and color it red. Color all the connected nodes on the next layer to be blue, and the next layer to be red. do this for the whole graph.
+**The node cannnot be connected to any other nodes that are more than one layer away.**
+Interesting/Readable: 5 5
+====== 3.5 Connectivity in Directed Graphs ======
+from undirected graphs to directed graphs
+Representing Directed Graphs: adjcentcy list: two lists in and out edges
+Breadth-first search and depth-first search are almost the same in directed graphs as they are in undirected graphs.
+**Strong Connectivity**:
+lemma:u and v are mutually reachable, and v and iv are mutually reachable then u and iv are mutually reachable.
+Proof on P124.
+Interesting/Readable: 6 6
+====== 3.6 Directed Acyclic Graphs and Topological Ordering ======
+definitions:
+  * If a directed graph has no cycles, we call it--naturally enough--a directed acycIic graph, or a DAG.
+  * analogous to any dependant systems in problem solving
+  * DAGs can be used to encode precedence relations or dependencies in a natural way.
+Problem:
+Goal: Find an algorithm for finding the TO.
+We can represent such an interdependent Set of tasks by introducing a node for each task, and a directed edge (i, j) whenever i must be done before j. The graph must be a DAG.
+Preparation:
+G has a topological ordering, then G is a DAG.
+proof:
+contradiction, spse we have a topological ordering, and also a cycle.
+then see what happens to the max indexed nodes...see p126.
+In every DAG G, there is a node v with no incoming edges.
+proof:
+same idea as above.
+Algo Idea:
+find a node v with no incoming edges
+Order v first
+Delete v from G
+Recursively compute a topological ordering of G-{v}
+and append this order after v.
+Readable/Interesting: 7/7