Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
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** | Designing the algo **Breadth-First Search** | ||
The idea is to use the BFS to push the layers forward and test for bipartiteness. | 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.** | + | **The node cannnot be connected to any other nodes that are more than one layer away.** |
| | ||
| | ||
Line 69: | Line 69: | ||
Interesting/ | Interesting/ | ||
+ | |||
+ | |||
+ | ====== 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, | ||
+ | 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/ | ||