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:01] – [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 42: | Line 42: | ||
* 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. | 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, | ||
+ | |||
+ | Interesting/ | ||
+ | |||
+ | ====== 3.4 Testing Bipartiteness: | ||
+ | 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/ | ||
+ | |||
+ | ====== 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/ | ||
+ | |||
+ | |||
+ | ====== 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/ | ||