Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| courses:cs211:winter2011:journals:charles:chapter3 [2011/02/14 03:16] – created gouldc | courses:cs211:winter2011:journals:charles:chapter3 [2011/02/18 06:51] (current) – [3.6 Directed Acyclic Graphs and Topological Ordering] gouldc | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | In progress | + | ====== Chapter 3: Graphs ====== |
| + | |||
| + | ===== 3.1 Basic Definitions and Applications ===== | ||
| + | |||
| + | ===== 3.2 Graph Connectivity and Graph Traversal ===== | ||
| + | |||
| + | ===== 3.3 Implementing Graph Traversal Using Queues and Stacks ===== | ||
| + | |||
| + | ===== 3.4 Testing Bipartiteness: | ||
| + | |||
| + | ===== 3.5 Connectivity in Directed Graphs ===== | ||
| + | |||
| + | ===== 3.6 Directed Acyclic Graphs and Topological Ordering ===== | ||
| + | DAGs are directed graphs that do not contain cycles. G is a DAG <=> G has a topological ordering. Despite DAGs having no cycles, they can contain nC2 edges. To find a topological ordering, recursively find nodes with no incoming edges and order them next in the ordering. (Once you order a node, delete it and all of its outgoing edges; this will cause there to be at least one new node that does not have an incoming edge.) Such an algorithm can run in time O(m+n). Topological orderings can be applied to precedence relations. For example, suppose two operations A and B such that A must be done before B. This could be formalised in a DAG by drawing an outgoing edge from A to B (A->B) but not the other way around. The topological ordering of this DAG would be the proper order of operations then? | ||
