====== 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: An Application of Breadth-First Search =====

===== 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?