This is an old revision of the document!
Table of Contents
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. A graph is a DAG ⇔ G has a topological ordering. Despite DAGs having no cycles, they can contain nC2 nodes.
