Differences

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

--- courses:cs211:winter2011:journals:chen:chapter_3 [2011/02/02 05:15] – [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 54: / Line 54: @@
 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.
+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.**
+**The node cannnot be connected to any other nodes that are more than one layer away.**
@@ Line 69: / Line 69: @@
 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